BledDest's blog

By BledDest, history, 7 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +92
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

The editorial is really nice. Learned a new concept in problem E. But what if K is not fixed? Any idea how to solve the problem if K is different for each query?

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

There's a test case for problem C which has x = 1 which is obviously invalid as it was given in the problem that x is not equal to 1. Maybe the test case is 24

  • »
    »
    7 years ago, # ^ |
    Rev. 3   Vote: I like it -12 Vote: I do not like it

    Yes. It was test case 24 which was invalid.

    2 1 1 2

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Is anyone able to explain the difference between pow and powl? I got WA for problem B due to precision error (link). After changing pow to powl, I got AC (link).

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    powl does calculations in long double and pow — in double. Obviously, the first one has more precision. Anyway, just use integer pow function (write it youself, i believe that c++ doesn't have one) when you work with integers and you won't have such problems.

»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Problem E also solvable with Sqrt - Decomposition in (N + Q) * sqrt(N).
Here is my solution 27599267.

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

    Could you please elaborate a bit? :)

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Firstly for every i find d[i], which is index of next K+1th A[i].
      Then for each query we have to find how many d[i] between L and R which is bigger than R.(which is equal to also (R - L + 1) minus how many small and equal to R between this range).

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone help me how dp is used in problem D. Acc to editorial, to update dp[x][y] first term should be greater than second one, thus while updating we would have:

if (x>y) dp[x][y] 

else if(y>x) dp[y][x] 

so we have left term of = for update ready.

Now for right terms of = there is a little confusion. Acc to the editorial we should update dp state using dp[i][y] with constraints, as we might get intersection with dp[x][i].

My doubt is how dp[i][y] guarantees no intersections and what if we constrain dp[x][i] with similar as we have in dp[i][y], would there be still intersections?

I tried to draw the 2D matrix of dp[][] , but problem is linear, I couldn't correlate both as per editorial to understand the solution.

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    We are currently updating position y, so we have already calculated dp[i][j] for 0 ≤ i ≤ n, 0 ≤ j < y. If y > x then the value of dp[y][x] is known and you can just take it (dp[x][y] = dp[y][x]).

»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

In Problem D,

if we respect the condition: we will update dp[x][y] only using values of dp[i][y], where i ≠ y and i < x.

When i<y, How can we guarantee that we didn't use i in the second melody?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    First up — dp[i][j] signifies that the first melody ends at position 'i', and second melody ends at position 'j'.

    The statement - " update dp[x][y] only using values of dp[i][y], where i ≠ y and i < x. "

    Meaning- We consider all cases where first melody ended at position 'i', and check if it is possible to append the 'x'th element of the array in the first melody. Hence, even when i<y, we DEFINITELY know that we used 'i'th element in the first melody itself, because the first melody ENDS at position 'i', so it definitely CONTAINS 'i'th element. Further, among all such combinations where the first melody ended at position 'i', we know that we have the most optimal combination selected as dp[i][y].

    Observe

    " update dp[x][y] only using values of dp[i][y], where i ≠ y and i < x. " So we explicitly remove the case where 'i'th element was indeed contained in the second melody as its last element.

    The gist

    When i<y, How can we guarantee that we didn't use i in the second melody?

    Because, we definitely used it as the finishing point of first melody.

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      when is dp[x][y] value updated if x < y, as dp[y][x] is updated in this case. and we need this value to update dp[x'][y'] when i < y' in dp[i][y'].

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

        By the time we need to compute dp[x][y] with x<y, we will have already computed the value of dp[y][x]. Now, dp[x][y] signifies first melody ending at x and second one ending at y; which is same as second melody ending at x and first ending at y (if we just reverse the notion of 'first' and 'second' melodies).

        Hence, as we already have dp[y][x] computed, we copy this value to dp[x][y] as well.

»
7 years ago, # |
Rev. 15   Vote: I like it +32 Vote: I do not like it

For E problem, I did the O((n + q)logn) solution using Wavelet Tree like this:

When we encounter the (k + i)th occurrence of any number we mark ith occurrence of that number

Let's create an auxiliary array a where ai is the time at which ith element in the original array was marked (if it was never marked let it be n + 1 otherwise it will be the index of (k+1)th occurrence starting from index i)

The answer to any query [l, r] = (r - l + 1)  -  (number of elements in that range marked with a number  ≤ r)

Counting number of elements in range [a, b] that lie in range [l, r] can be done in O(logn) time using Wavelet Tree, constructing the tree takes O(nlogn) time

Submission: 27601587

You can read this paper for reference: ioiconf16

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for sharing this material, I've never heard of wavelet tree until now. Gonna love it — I usually get RE for my persistent tree submissions as I usually don't allocate enough memory for it.

    However, after reading the paper I still don't quite understand how does wavelet matrix works in O(sigma) time with the "partitioning trick". Would you mind give an example of how does wavelet matrix works (differs to wavelet tree) for some of the standard queries (quantile / rank / range-count) mentioned in the paper?

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I didn't try Wavelet Matrix before, I always get around big alphabets by using coordinates compression before building Wavelet Tree

      Even better, we can just add few more characters to the original Wavelet Tree to avoid expanding empty nodes

      This is the same submission but for numbers in range [  - 109, 109 ]: 27621342

      The differences were:

      build: if(L == R) ==> build: if(L == R || pl >= pr)

      query: if(k < L) ==> query: if(k < L || l >= r)

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

        Hey, can you suggest any resource for reading more on wavelet matrix that can help me in understanding your solution. I already know wavelet tree.
        Thanks in advance

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

I'm struggling a bit to understand the question about The Melody ... Can someone recommend some similar, simpler problems or concepts which will help me understand it ?

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

For the explanation of problem F I don't quite understand how would do you answer the queries in O(qlog^2q) time. The best I could think of is using sack on the segment tree but that doesn't improve a single merge to the cost of O(log q). Would someone mind further elaborate on this paragraph?

Now we can add a new edge and remove last added edge. All these operations cost (O(logn)) because we won't use path compression in DSU — path compression doesn't work in intended time if we have to rollback. Let's actually start solving the problem.

(From the next paragraph of the above I assume that the edges are stored in a segment tree that is similar to a lazy progration segment tree — except we are not pushing it, right?)

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

Can any one give a proof outline for the solution to problem C?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    First notice that Alice will always be going in the subtree where Bob is (because she wants to finish as quickly as possible). Second observation is that, the game will always end at the leaf vertex; if not, then say game ends at v which is not a leaf in the optimal solution (here optimal solution implies maximum number of moves). Then, Bob can go to any leaf vertex in the subtree of v to increase the number of steps in the game which contradicts our fact that our pervious solution was not optimal. Hence, the game must end at a leaf vertex. Also, as Alice always increases her depth at each move, so the game will end at some leaf, say s, when Alice will come to that leaf and answer will be 2 * depths.

    Now, we need to just find a leaf vertex such that Bob can reach there before Alice and is at the highest depth from Alice. The procedure to do this explained in the editorial.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The Explaination Given By hrushikesht Is Much Better And Simple than The one given in the editorial , it took me some time to come upto this logic
    Thanks to rajat1603_ and _Reborn_ .
    All We Have To Do Is Create 2 Distance Arrays
    _- 1. Distance1[i]: distance of ith node from alice
    _- 2. Distance2[i]: distance of the ith node from bob
    Both of this can be done by DFS And just One Function

    After Which All We Need is To Check if Distance1[i] > Distance2[i]
    (**distance of ith node from alice > distance of ith node from bob**)
    If So Ans=max(Ans,2*distance1[i])
    This is Because We Can See That
    The Total Number Of Moves Is always equal to the number of moves by alice * 2

    Here is My Code : 27611356

    PS : It Is only my second comment ever on a codeforces post , sorry if i am not able to clear your doubts :)

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

      this explanation is great bud!...

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        i did the same ...but i am not able to get/understand the fact that why dist1[i]>dist2[i] why not dist1[i]>=dist2[i]

        i made two submisionss one for >= and one for >. I got AC in latter but the one in which >= was there the test on which it failed the output was 30 and correct is 8 !! i dont know if i have understood the question correctly or not or its my logical error

        can anyone explain me ??

        thanx in advance

        my two submissions 27785255 (for >=,WA) 27785276 (for >,AC)

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

          if dist[i]==dist[j] then it might happen that alice and bob will meet at some other intermesiate node in their path to final leaf node.

»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Hello!

Can anyone tell me in details about function prev(x, y) in problem E, please. Thanks.

Здравствуйте. Можете, пожалуйста, более подробно рассказать про функцию prev(x, y) в задаче Е. Спасибо

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

    For eg. if x = 7(1 based indexing), y = 2 and the array is [1 3 3 5 3 4 3 6]. prev(x, 1) just returns the greatest i < x such that a[i] = a[x] a[7] = 3. prev(7, 1) = 5 Also prev(5, 1) = 3

    So prev(7, 2) = prev(prev(7, 1), 2 — 1) = prev(5, 1) = 3.

    You may also notice that prev(7, 3) would return 2.

    It just checks whether there are y more soldiers to the left of x with the same type as a[x] or not. If there are, it just returns the index of the yth previous soldier, else it just returns -1.

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

      Thank you. I was facing trouble to understand this. Now I got it.

»
7 years ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

Problem F can also be solved in O(n * sqrt * log*). First of all, split queries in buckets of size SQRT and solve them independently. Before starting to compute answers, take the edges that are valid throughout the fixed bucket and color the graph built out of them. You can process an edge of the bucket by applying the standard algorithm with DSU on precomputed connected components and bucket's new edges. There are only SQRT new edges and at most 2 * SQRT useful components. My implementation can be seen here : [submission:http://codeforces.me/contest/813/submission/27621652]

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

Problem C, will the situation become more complex if Alice goes first?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Please correct me if I am wrong.

    The situation doesn't necesserily change if Alice goes first. We can consider a more general case where Alice gets a boost of, say k moves. On each step Alice can go repeatedly to the subtree belonging to Bob. If she encountered Bob at any node during the first k moves, that is our answer. Else, we can apply the same soulution to the subtree which corresponds to the vertex Alice remains after k moves.

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

      Understood. Thank you! I was thinking what will happen if A deceived B into coming close to her, though it is dangerous. Your analysis remind me this situation shouldn't be considered in this problem.

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

how to do Problem B?

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

    You could refer to this....27663894

    I've just calculated all powers of x & y in the range and then we could just add them.

    Then we can just check max sequence once we all unlucky years, in the range of l and r.

    Sorry if the code isn't that readable but I hope it helps.

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

"Now iterate over all vertices and check if Bob can reach this vertex earlier than Alice. If he can then update the answer with the lowest vertex that can be reached from this one"

Can anyone please explain this line to me. I've got trouble understanding the editorial to this question

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

    It just means that Bob is checking all nodes that he can reach before Alice catches up to him.

    So, we can check all nodes that are reachable under this constraint and find the one having maximum depth.

    This will help us find our answer.

    Hope this helps...27663362

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

Hello,

speaking about the tutorial of the problem F did any one mange to implemented like it's explained.

If not can you please reference your submission and give me a few explanation I did see same implementation but I don't get the general idea.

Thank you very much

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I did. You can find my code here.

    The variable invalid_cnt stores the number of "bad" edges, i.e. edges which introduce an odd-length cycle and hence, destroy bipartiteness. The graph is bipartite iff its value is 0. Also, instead of sum, I have used xor (does not make a difference). You need to merge sets carefully. If you are adding edge (a, b) and merging the respective sets, the distance of a and b to the root change iff the original distances are same (here distance is always 0/1).

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

    Here is an implementation based on the tutorial with clear notes , code, hope it helps you.

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

In problem D, it's claimed "we can't guarantee we didn't use i in the first melody". But if we use dp[x][i], it means, that the second melody finishes in note i, that's why we can guarantee we didn't use i in the first melody. Do I misunderstand something? Or maybe author meant "we can't guarantee we didn't use y in the first melody"?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Consider DP states DP[a1][b] and DP[a2][b], a1<a2<b, i.e. let a2 be the note chosen after a1 in the first sequence. You cannot make this transition as you do not know that path taken by the second melody before it reaches b, it may have itself chosen a2 in its sequence.

    Instead, think of it this way. Mark all the indices that appear in either of the two melodies. Iterate over them from left to right. So, if you are at DP[x][y], x<y, you will only consider those indices p such that p>y. If you add p to the first sequence, you get the state DP[y][p]. If you add it to the second, you get the state DP[x][p]. The benefit of doing this is that this will prevent the same index getting chosen by both melodies.

    You can take a look at my code for this approach.

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

      You claim: "...it may have itself chosen a2 in its sequence". In terms of x, y, i, we have x = b, y = a2, i = a1. So, I ask, should it be "we can't guarantee we didn't use y in the first melody"?

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        First melody ends at i and second ends at b. There exists some y such that i < y < b. We cannot append y to the first melody because we may have used it in the second (leading up to b).

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

          When you say "we may have used it in the second", does it mean y? If yes, it should be "we can't guarantee we didn't use y in the first melody" instead of "we can't guarantee we didn't use i in the first melody" in the editorial.

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

      In your code, can you explain the meaning of the states DP(i,j) and DP2(i) ?

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

        DP2[i] is the max length of a melody ending at index i.
        DP[i][j] is the max sum of lengths of two melodies, which start at i and j.