halin.george's blog

Codeforces Round #381 Editorial
By halin.george, history, 7 years ago, In Russian
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +48
  • Vote: I do not like it

Comments Comments (35)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Could someone please look at my code for 739B? I was getting WA on pretest 15 and am not sure why...

I store the 2^k ancestors and the distance to them in bparent[][] and bdist[][]. I then binary search for each node that controls the node that I am on and store the start and end segments in event[]. The function solve() dfs's through the tree, keeping track of how many nodes each node controls.

Thanks!

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D, how do we store the ancestors of all nodes in O(n)?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    You only store the (2^k)th ancestors of a node -> O(n*log n)

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the approach for the problem 'Alyona and Tree'

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    This is the binary search method that may not be the easiest, I recommend checking out zawini54's comment too!

    A few observations could be made:

    1. dist(v, u) = dist(root, u) - dist(root, v)
    2. for any vertex v, and its ancestors a1, a2, ..., ai,
      a1 being the furtherest ancestor (root of the tree) and ai the closest (immediate parent vertex),
      we can see that dist(root, a1) < dist(root, a2) < ... < dist(root, ai) < dist(root, v), a sorted sequence that is binary searchable.
    3. for each vertex v, we want to find the number of vertices u it controls, i.e.:
      dist(v, u) ≤ value(u) dist(root, u) - dist(root, v) ≤ value(u) dist(root, u) - value(u) ≤ dist(root, v)
    4. with #2 and #3 in mind, let's try to think of this problem in another way: for each vertex u, which vertices v could control u?
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ok, for each vertex u, I can find how many ancestor controls it, but how do I use this information to find out the reverse?

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

        this can be maintained using segment tree on the path from root to current vertex

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

      Let u is controlled by x vertices. Then the immediate x parents of u could control this vertex u.

      But a simple approach in getting the answer requires O(n^2) which would fail on the time limit. Can you suggest a better approach?

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

        Consider the array, A = [6, 1, 6, 9, 3]

        We can compute an array of differences between the neighbouring two elements, a difference array, D = [6,  - 5, 5, 3,  - 6],

        Note how we can reconstruct the array A from its difference array D,

        A[0] = D[0]
        A[1] = D[0] + D[1]
        A[2] = D[0] + D[1] + D[2]
        A[3] = D[0] + D[1] + D[2] + D[3]
        A[4] = D[0] + D[1] + D[2] + D[3] + D[4]

        If we can somehow first construct a difference "array" D for this problem, then we can reconstruct the answer "array" A from it.

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

          Sorry, I still do not get it. How do you get this difference array?

          → Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Actually there's another solution that doesn't use binary lifting, but the merging sets technique. I think it's easier, because at first I thought of doing something with binary lifting but wasn't able to come up with anything. Check it out: 22490570

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Nice approach, btw are you making reference to the technique disscused at this post?

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

    I considered merging set approach during contest, but couldn't find a way to count the number of elements <= d in O(logn) using std::set, now I know it's unnecesary for this problem after reading you code.
    However, if the condition change to that v controls u if dist(v, u) <= a(v) (instead of a(u)), it seems we must have a way to count the number of elements <= d in O(logn) using merging set approach, and std::set doesn't satisfy this.

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

      Actually, I don't think my approach works with the harder version of the problem, since it relies on that fact that d(v) is monotonically increasing as you go down the tree. I think there should be a solution involving segment tree and coordinate compression, but I haven't thought about it that much. Please feel free to correct me on anything.

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

      But Ordered Statistics Tree does. Can't we use it instead of sets?

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

    An explanation please?

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

    Hi,your approach looks amazing, I just learned binary lifting through this problem and now you propose another way of doing the problem... Where did you learn this technique from, I want to learn this too,is there some blog post associated with it , or some source where I can learn the merging set technique,because I cant understand your solution , can you also explain it just a little..?

    Thanks a ton!

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

      Article on the merging sets technique

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

      For anyone looking for a binary lifting solution: here it is

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

        Explanation to the binary lifting solution:

        The base idea can be seen here. We just don't use the binary search over the ancestors of a node.

        We create the parent's DP, that is required to do binary lifting. I saw this video to understand binary lifting. You create an 2D matrix with dims: DP[N][HEIGHT], where DP[i][j] represents the parent of $$$i^{th}$$$ node at height $$$2^j$$$ from $$$i$$$.

        DP[i][0] is simply the direct parent of the node, already given in the question. For the others, use this:

        f(j,1,21) f(i,0,n) parDP[i][j] = parDP[parDP[i][j-1]][j-1] ;

        Where j is the height, and i is the node. If you're confused, watch the video.

        Now, we remove the binary search part, and instead do the search using the parent DP matrix we created.

        This can be done using:

        int s = node ;
    for(int d=20;d>=0;d--)
    {
        if(dist[node]-dist[parDP[s][d]]<=a[node])
        {
            s = parDP[s][d] ;
        }
    }

        This is what I stole from yaksha. Thenks. What does it mean tho?

        It finds the farthermost parent of s, that satisfies the condition. Let's name it $$$\phi$$$. But we're iterating through the powers of 2. That is, it is possible that a parent at an height of $$$2^j$$$ from $$$s$$$, might satisfy the condition, but we didn't see $$$2^{j+1}-2^{j}$$$ elements between the two parents.

        So, we'll have to iterate through the parents of $$$\phi$$$. But do we have to start again? No. We know that $$$2^{j+1}$$$th parent didn't satisfy, whereas $$$2^j$$$ did. So, we have a gap of $$$2^{j+1}-2^j = 2^j$$$ elements. So, we look into the $$$j^{th}$$$ parent of $$$\phi$$$ this time. This gap closes as we progress towards d=0.

        Everything else is pretty much the same.

        Here is my submission, made from multiple code stealing activities.

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

    Beautiful solution!

    This question just keeps on giving :>

    So explanation on the DSU on tree method to solve this problem (Alyona And Tree):

    There's a basic HLD (heavy light decomposition) concept of light child and heavy child in a tree for each node.So, consider you have a node $$$N$$$, which has $$$\alpha$$$ children, $$$C_1,C_2,C_3,...,C_{\alpha}$$$. Now, the child, which has the maximum size of it's subtree, is the one which is called the big child or the heavy child. Every other child is called a light child.

    How is this concept useful?

    So, for a node, consider, you need to perform some query that needs information from the whole tree, then in that case, if you do a brute force operation, then you'll get a $$$O(n^2)$$$ time complexity. What we can do here, is store the information of the big child while the traversal is done, and for the rest of the children, we do whatever we did in the brute force method.

    How does that help us?

    Basically we're not going into the big child, but are going into the light children. Consider this, if $$$x=tree[lightchild].size()$$$ and $$$y=tree[bigchild].size()$$$. So, $$$y > x$$$, obviously. So, if I merge the subtree of the lightchild into the subtree of the bigChild, then it's size: $$$y+x > x+x = 2\times x$$$. That is, each merge operation will, at least, double the size of the bigchild subtree. So, we can do this doubling operation only until the total number of elements ($$$=n$$$) is reached. That is, $$$log(n)$$$ times.

    And since we have $$$n$$$ nodes in total, the total time complexity is $$$O(n log n)$$$.

    You can learn more about DSU on graphs, here and here.

    Steps for the algorithm:

    1. For a node, find the bigChild.

    2. DFS through the lightChilds, and do not remember their results

    3. DFS through the bigChild, and remember it's result

    4. Add the result of the current node, if possible.

    5. Add the values of the subtrees of the lightChilds.

    6. At this point, we have the result for the node

    7. Remove the values of the lightChilds if the current node is a light child, else do not delete them

    This is the procedure, I understood from the tutorial.

    Now let's try to analyze szawinis' solution. Here we are not keeping results in some variable array or something, therefore there is no removal of values at the end of the DFS. That is, we can keep the subtree information intact, while traversing the tree. So priority queue pq stores the $$$\text{distance from root}-a[v]$$$ value for the nodes that satisfy the condition. That is for the node node, pq[node] will have the mentioned difference for the nodes which satisfy the condition (d[child]-d[node]<=a[child]).

    In the big for loop, if we see a light child, we push all it's values into the current node's pq. Whereas, if we see a potential bigChild, we push all the elements of the current node into the bigChild's pq and then point to the bigChild's pq as the current node's pq.

    The point is, not to transfer the elements of the big child (which actually makes the algorithm run in O(nlog n)). Then we disregard the elements which do not satisfy the condition. If you think that's a problem, then think how many elements in total can you remove? So yeah this can, at max n elements, because only the elements that satisfy the condition for the current node, are percolated up as potential candidates.

    At this point, you can take the value of pq[node].size() as the answer. And then add the node itself in it's priority queue.

    I hope this helps.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please elaborate the binary lifting method for problem D?

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

    My Code 22652723

    easy to understand

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

      Instead of binary lifting, I think you're using binary search in here.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      For everyone trying to understand Sukeesh's solution, here is an explanation:

      Basic what we knows:

      1. $$$dist(u,v) = dist(root,v)-dist(root,u)$$$. We're given the condition: $$$dist(u,v) \leq a_i$$$, which can be written now as $$$dist(root,v)-dist(root,u) \leq a_i$$$ (where $$$u$$$ is an ancestor of $$$v$$$).

      2. If you're looking at vertex $$$v$$$, then it's ancestors' distances from the root, will be in strictly increasing order, starting from the root itself. That is, if $$$a_1,a_2,a_3,...,a_i$$$ are the ancestors of $$$v$$$, where $$$a_1$$$ is the root, and $$$a_i$$$ is the parent of $$$v$$$, then the distance of this series of nodes, from the root, will be in strictly increasing order. Thus we can do a binary search on them.

      So let's see the algorithm. We're doing a DFS here.

      Consider we're at the vertex $$$v$$$, and we have the information of it's ancestors saved in an vector $$$arr$$$. We're saving the distance of a node from the root in the array $$$d$$$, while we're going down while the DFS. So while we're at $$$v$$$, we have the distance of it's ancestors from the root already saved in $$$d$$$.

      Great.

      Now we look for the first ancestor $$$a$$$ which doesn't satisfy the condition:

      $$$dist(root,v)-dist(root,a) \leq v_i$$$
      $$$dist(root,v)-v_i \leq dist(root,a)$$$

      We can calculate the LHS of this formula for our $v$ boi, and then we can search for this value in $$$arr$$$. Let's say this value's index is $$$hi$$$. So, bringing partial sums in here fam.

      This part is good. So what do we have here? We can say that all ancestors of $$$v$$$ after $$$hi$$$ (including $$$hi$$$) till the parent of $$$v$$$ satisfy the condition, right?

      We're saving the partial sums in an array dp.

      So as done in partial sums, we do dp[par[v]]++ and dp[par[arr[hi]]--. You'll understand this is you know about partial sums. We increase the starting of a segment, and decrease after the end of it.

      Now we carry on to our DFS work.

      We do all this,and do complete our DFS from the root.

      Now we can compute the answer of each node, by using the partial sums we built during the first DFS (oh no, there's no second DFS, yet).

      So, we calculate the answer for each node, in the same way, we created the dp array(i.e. going through a DFS). So we calculate the dp value for the children first, and then use it to calculate the value of the parent, by adding the children dp values in the parent dp value. The function go is used to do that.

      void go(ll v){
	for ( ll j = 0 ; j < adj[v].sz ; j ++ ){
		go(adj[v][j].F);
		dp[v] += dp[adj[v][j].F];
	}
}

      Why is this working you ask? Consider a positive value is encountered. This means that this is a starting point for a segment of nodes which have some node $$$v$$$ for which the needed condition is satisfied. Thus we increase our dp value. If a negative value is encountered, we know that some segment has ended, and we decrease our dp value.

      Hope this helps someone.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In 739E — Gosha is hunting, The editorial writes "Not hard to prove that in group Y we should throw Poke Balls to Pokemons with greatest u - p." I think that we want to maximize PokeBalls probability when we throw PokeBalls. So shouldn't we throw pokeballs to pokemons with greatest p-u?

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

    That is not correct. Let me clarify a part of the editorial's proof for archival reasons.

    Assume that the pokemons have been sorted in descending order of $$$u_i$$$, therefore $$$u_0 >= u_1 >= u_2 >= .... u_{n-1}$$$. Now, let $$$i$$$ be the index of the last pokemon to be thrown an ultraball.

    Claim: For all pokemon in $$$[0, ... i - 1]$$$, we throw a ball at them (or perhaps two).

    Proof: Assume that there was a pokemon, say $$$x$$$, where $$$0 <= x < i$$$, and we don't throw a ball at $$$x$$$. But note that we do throw a ultraball at $$$i$$$. What is the total change if we throw that ultraball at $$$x$$$ instead?

    Case 1: We do not also throw a pokeball at $$$i$$$:
    — Loss in not throwing the ultraball at $$$i$$$ = $$$u_i$$$
    — Gain in throwing the ultraball at $$$x$$$ = $$$u_x$$$.
    Since $$$u_x >= u_i$$$, we can throw the ultraball at $$$x$$$ and not be worse.

    Case 2: We do also throw a pokeball at $$$i$$$.
    — Loss in not throwing the ultraball at $$$i$$$ = $$$(u_i + p_i - p_{i}u_{i} - p_i) = u_i(1-p_i)$$$
    — Gain in throwing the ultraball at $$$x$$$ = $$$u_x$$$.
    Since $$$u_x >= u_i >= u_i(1-p_i)$$$, we can throw the ultraball at $$$x$$$ and not be worse.

    Hence Proved

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

      Can you explain the Loss in case 2 proofbycontradiction? Does it mean that (ui + pi) -> either ultraball catches the pokemon or pokeball catches it. and (uipi + pi) -> either both types of balls catches pokemon or pokeball catches it.

      therefore (ui + pi) — (uipi + pi) -> ultraball catches the pokemon but pokeball does not.

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

    Yeah, I also think so

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div1-A or Div2-C Why not to just fill the whole array with the maximum available value which is 10^9-1 and the maximum minimum mex becomes 10^9 ?

You didn't mention anything like : the array(or subarray) elements need to be unique !

What am I getting wrong here ?

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

    "The mex of a set S is a minimum possible non-negative integer that is not in S."

    if you fill array with max value your ans will be 0

    → Reply