Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | tourist | 3775 |

2 | Benq | 3724 |

3 | orzdevinwang | 3697 |

4 | Radewoosh | 3651 |

5 | jiangly | 3632 |

6 | cnnfls_csy | 3620 |

7 | -0.5 | 3545 |

8 | inaFSTream | 3478 |

9 | fantasy | 3468 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 178 |

2 | awoo | 167 |

3 | BledDest | 165 |

4 | Um_nik | 163 |

5 | maroonrk | 162 |

6 | SecondThread | 159 |

7 | nor | 158 |

8 | -is-this-fft- | 153 |

9 | kostka | 146 |

10 | TheScrasse | 144 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Educational Codeforces Round 22

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/04/2023 03:45:39 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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?

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

Yes. It was test case 24 which was invalid.

2 1 1 2

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

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.

Problem E also solvable with

Sqrt-Decompositionin (N+Q) *sqrt(N).Here is my solution 27599267.

Could you please elaborate a bit? :)

Firstly for every

ifindd[i], which is index of nextK+1^{th}A[i].Then for each query we have to find how many d[i] between

LandRwhich is bigger thanR.(which is equal to also (R-L+ 1) minus how many small and equal to R between this range).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:

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.

We are currently updating position

y, so we have already calculateddp[i][j] for 0 ≤i≤n, 0 ≤j<y. Ify>xthen the value ofdp[y][x] is known and you can just take it (dp[x][y] =dp[y][x]).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?

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], whereSo we explicitly remove the case where 'i'th element was indeed contained in the second melody as its last element.i ≠ yand i < x. "The gistWhen 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.

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

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.

For E problem, I did the

O((n+q)logn) solution using Wavelet Tree like this:When we encounter the (

k+i)thoccurrence of any number we markithoccurrence of that numberLet's create an auxiliary array

awherea_{i}is the time at whichithelement in the original array was marked (if it was never marked let it ben+ 1 otherwise it will be the index of (k+1)th occurrence starting from indexi)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 inO(logn) time using Wavelet Tree, constructing the tree takesO(nlogn) timeSubmission: 27601587

You can read this paper for reference: ioiconf16

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?

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 [ - 10

^{9}, 10^{9}]: 27621342The differences were:

`build: if(L == R)`

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

`query: if(k < L)`

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

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

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 ?

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?

(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?)

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

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

vwhich 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 ofvto 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, says, 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 byDFS And just One FunctionAfter 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 * 2Here 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 :)this explanation is great bud!...

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)

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.

Hello!

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

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

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.

Thank you. I was facing trouble to understand this. Now I got 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.com/contest/813/submission/27621652]

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

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

kmoves. On each step Alice can go repeatedly to the subtree belonging to Bob. If she encountered Bob at any node during the firstkmoves, that is our answer. Else, we can apply the same soulution to the subtree which corresponds to the vertex Alice remains afterkmoves.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.

how to do Problem B?

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.

"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

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

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

I did. You can find my code here.

The variable

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

In problem D, it's claimed "we can't guarantee we didn't use

iin the first melody". But if we usedp[x][i], it means, that the second melody finishes in notei, that's why we can guarantee we didn't useiin the first melody. Do I misunderstand something? Or maybe author meant "we can't guarantee we didn't useyin the first melody"?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.

You claim: "...it may have itself chosen

a_{2}in its sequence". In terms ofx,y,i, we havex=b,y=a_{2},i=a_{1}. So, I ask, should it be "we can't guarantee we didn't useyin the first melody"?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).

When you say "we may have used

itin the second", doesitmeany? If yes, it should be "we can't guarantee we didn't useyin the first melody" instead of "we can't guarantee we didn't useiin the first melody" in the editorial.In your code, can you explain the meaning of the states

`DP(i,j)`

and`DP2(i)`

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