vishal_sahu's blog

Same Color — Help!
By vishal_sahu, history, 17 months ago, In English

Given a weighted tree consisting of N vertices and N-1 edges. In a single operation, you can select an edge and increase or decrease its weight by 1. You are given Q queries and a query consisting of two vertices U and V, determine the minimum number of operations to be performed such that the weight of each edge of the path from vertex U to vertex V becomes the same.

With constraint up to 10^5;

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
17 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I don't have any approach simpler than it, which requires persistant segment tree.

We know that, when we have two (multi)sets $$$S, T$$$, which both maintained by segment tree(every position stand for one value), and we want $$$T - S$$$, we can just use the "subtraction" of two segment trees.

Then look at the problem, think how to get the (multi)set of a path $$$(u, v)$$$.

  • Firstly, find their lca, calling it $$$w$$$.
  • Then, $$$S_u + S_v - 2 \times S_w$$$ is what we want, similar to prefix sum trick for tree. $$$S_x$$$ stands for the set of path $$$(1, x)$$$, and $$$S_1, S_2, \cdots , S_n$$$ can be prepared before queries through DFS + persistant segment tree in $$$O(n\log U)$$$ time($$$U$$$ equals to maximal weight of edges).

Now the problem has been simplified as: find minimal cost, as the original problem said, of a set $$$S$$$.

It's clear that we optimally choose the medium($$$m$$$) of $$$S$$$ as target, and each $$$x\in S$$$ contributes $$$|m-x|$$$. Finding medium and calculating $$$\sum_{x\in [l, r]} x$$$ are things we need to do, and both of them can be done by a segment tree.

Complexity: $$$O((n+q) \log U)$$$.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've never heard about persistant segment tree, can you explain how it works and what it can do?

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      sry for late reply...

      "Persistent" means, when we modify on segment tree $$$T$$$ and get a new tree $$$T'$$$, $$$T$$$ is still accessible. For example, if you want to change a position, a path of length $$$O(\log n)$$$ can be found, we will copy a new path instead of simply changing it. Then the original tree is not modified actually.

      In this problem, we apply "insert a number $$$x$$$ into the set" operation, which is to find the path of position $$$x$$$ and get all the nodes on the path added $$$x$$$. Each node maintains $$$\sum_{x\in [l, r]} x$$$. But the previous version is still needed, so just get it persistent.

      To understand 'subtraction', think about two nodes $$$x, y$$$ respectively on two trees $$$T_1, T_2$$$, representing a same number range $$$[l, r]$$$. $$$x-y$$$ exactly equals to the maintained value of node representing $$$[l, r]$$$ on tree $$$T_1-T_2$$$.

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it -14 Vote: I do not like it

        I asked about persistant segment trees, not about persistent.

        → Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

First, figure out how to do this with an array. It can be proven that it's optimal to set all numbers to the median(any in the case of 2). Let $$$M$$$ = median. To find $$$M$$$, you need a DS that can get the xth number. You'd also need the following to get the answer: The sum of all numbers <= $$$M$$$ and count of all numbers <= $$$M$$$. (We can get the same values of greater than $$$M$$$ by subtracting from total sum/count). All of this can be done with things like fenwick/segtree/treap etc. Using these 4 values, you can get the answer with math. Now, how to solve for tree case? Some standard ways to solve it:

  1. Persistent segtree bash (using persistence to store the sum & count from the root to each node, then using the fact that sum/count from u->v = root->u + root->v — 2*root->lca(u,v).$$$O((N+Q)log C)$$$. Can be sped up to $$$O((N+Q)logN)$$$ with discretization offline.

  2. Mo's algorithm on tree (using Euler tour to convert the tree queries to line query + LCA, then using Mo's to answer the queries) $$$O((N+Q)\sqrt{N}logN)$$$ <- This complexity is quite slow XD. Can be sped up to $$$O((N+Q)\sqrt{N})$$$ probably

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Notice that we have $$$O(N\sqrt N)$$$ modifications but only $$$O(Q)$$$ queries. So don't use log DS but apply square root decomposition to strike a balance(discretization needed).

    $$$O(\sqrt N)$$$ to query and $$$O(1)$$$ to modify. Total complexity is $$$O((N+Q)\sqrt N)$$$.

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem link?

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    asked in today's leetcode contest weekly contest 361

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you can select an edge and increase or decrease its weight by 1. If you are talking about today's leetcode contest question 4 then you read the question wrong. You can change the weight of edge to any value rather than increasing or decreasing it by 1.

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        it will be done by same method bro it is almost similar though :)

        → Reply
        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Kind of but the constraints are also important. 1<=n<=1e4 and 1<=w<=26 where n is number of nodes and w is weight of edges, which allows for simpler approaches to work also and doesn't require ds like segment tree or such. Also the answer would be different if the operation is increase or decrease by 1 rather than change it to any value.

          → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It is a OA question of Hackerearth Contest by Globalization partners and the contest is ended and there were also additional constraints on weight , weights can be upto 26 only so my approach was just to store all the weight values(coming in the path from that node to root ) for every node then we can apply binary lifting for finding lca of two nodes and take the union of both like for 3 and 2 and suppose lca of both 3 and 2 is 4 and then we will take union of these two arrays and subtracting the array of 4 and simply we can brute force for the answer as the chosen weights can be upto (1 to 26)

→ Reply