Yes. It was test case 24 which was invalid.

2 1 1 2

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.

Could you please elaborate a bit? :)

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]).

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.

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?

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 * depth_s.

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.

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 :)

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.

У тебя функция prev работает за O(N).

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.

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.

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

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).

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

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.