BledDest's blog

By BledDest, history, 3 years ago, ,

• +92

 » 3 years ago, # |   +6 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?
•  » » 3 years ago, # ^ |   -72
 » 3 years ago, # |   0 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
•  » » 3 years ago, # ^ | ← Rev. 3 →   -12 Yes. It was test case 24 which was invalid.2 1 1 2
 » 3 years ago, # | ← Rev. 2 →   0 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).
•  » » 3 years ago, # ^ |   +4 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.
•  » » » 3 years ago, # ^ |   0 Oh I see. Thanks! I'll make sure to include an integer power function into my template next time.
 » 3 years ago, # |   +11 Problem E also solvable with Sqrt - Decomposition in (N + Q) * sqrt(N). Here is my solution 27599267.
•  » » 3 years ago, # ^ |   0 Could you please elaborate a bit? :)
•  » » » 3 years ago, # ^ |   +11 Firstly for every i find d[i], which is index of next K+1 th 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).
 » 3 years ago, # | ← Rev. 2 →   0 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.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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]).
 » 3 years ago, # |   +12 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
•  » » 3 years ago, # ^ |   +18 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
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 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'].
•  » » » » 3 years ago, # ^ |   0 By the time we need to compute dp[x][y] with x
 » 3 years ago, # | ← Rev. 15 →   +32 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 numberLet's create an auxiliary array a where a i 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) timeSubmission: 27601587You can read this paper for reference: ioiconf16
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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?
•  » » » 3 years ago, # ^ |   +5 I didn't try Wavelet Matrix before, I always get around big alphabets by using coordinates compression before building Wavelet TreeEven better, we can just add few more characters to the original Wavelet Tree to avoid expanding empty nodesThis is the same submission but for numbers in range [  - 109, 109 ]: 27621342The differences were:build: if(L == R) ==> build: if(L == R || pl >= pr)query: if(k < L) ==> query: if(k < L || l >= r)
•  » » » » 6 weeks ago, # ^ |   0 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
 » 3 years ago, # |   0 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 ?
 » 3 years ago, # |   0 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?)
 » 3 years ago, # |   0 Can any one give a proof outline for the solution to problem C?
•  » » 3 years ago, # ^ |   +2 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.
•  » » 3 years ago, # ^ |   +3 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 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 : 27611356PS : It Is only my second comment ever on a codeforces post , sorry if i am not able to clear your doubts :)
•  » » » 3 years ago, # ^ |   0 this explanation is great bud!...
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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 advancemy two submissions 27785255 (for >=,WA) 27785276 (for >,AC)
•  » » » » » 3 years ago, # ^ |   0 if dist1[i] == dist2[i], then Alice and Bob, both will reach a given node at same time. In which case, game ends.
•  » » » » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   +4 Hello!Can anyone tell me in details about function prev(x, y) in problem E, please. Thanks.Здравствуйте. Можете, пожалуйста, более подробно рассказать про функцию prev(x, y) в задаче Е. Спасибо
•  » » 3 years ago, # ^ |   -7 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) = 3So 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.
 » 3 years ago, # | ← Rev. 2 →   +12 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]
 » 3 years ago, # |   0 Problem C, will the situation become more complex if Alice goes first?
•  » » 3 years ago, # ^ |   +1 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.
•  » » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   0 how to do Problem B?
•  » » 3 years ago, # ^ |   0 You could refer to this....27663894I'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.
 » 3 years ago, # |   0 "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
•  » » 3 years ago, # ^ |   0 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
 » 3 years ago, # |   0 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
•  » » 3 years ago, # ^ |   +3 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).
•  » » » 3 years ago, # ^ |   0 Can you please explain what each function do
•  » » » 3 years ago, # ^ |   0 I know that arr array help getting the real color of a nœud because when we merge set we do not connect the two nœuds represented by the arc but instead we connect one of the node to the route noeud of the other set. Can you please explain how arr array help us getting the real color using xor?
 » 3 years ago, # |   0 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"?
•  » » 3 years ago, # ^ |   +6 Consider DP states DP[a1][b] and DP[a2][b], a1y. 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.
•  » » » 3 years ago, # ^ |   0 You claim: "...it may have itself chosen a 2 in its sequence". In terms of x, y, i, we have x = b, y = a 2, i = a 1. So, I ask, should it be "we can't guarantee we didn't use y in the first melody"?
•  » » » » 3 years ago, # ^ |   +6 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).
•  » » » » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 In your code, can you explain the meaning of the states DP(i,j) and DP2(i) ?
•  » » » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   0 Can someone help me with the first problem? can some1 pls explain it detaily?