### cyand1317's blog

By cyand1317, 4 years ago, Long time no see!

As VK Cup Round 2 and its two parallel rounds (Div. 1 and Div. 2) comes to a close, we're here to congratulate on all who did well on the contest and cheer for everyone who participated — the queue won't stop you!

Here are the detailed tutorials for the problems. Feel free to discuss in the comments!

Kudos to arsor for translating the tutorials into Russian!

Model solution
Alternative solution (Errichto)

(by cyand1317)

Model solution
Alternative solution with DSU in O(nm alpha(n)) (skywalkert)
Alternative solution in O(nm)

(by cyand1317)

Model solution

(by KAN, prepared by fcspartakm)

Model solution

(by cyand1317)

Model solution

(by KAN, prepared by cyand1317)

Model solution

(by KAN)

Model solution

(by Claris and skywalkert)

My gratitude to the coordinators, problem authors, testers, and every participant. You made all this possible! Cheers \(^ ^)/ Tutorial of VK Cup 2018 - Round 2   472, Comments (49)
 » Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).
 » funny python fact: in 956B NlogN solution in Python3 is very likely to get TLE. For the pretests, I got AC with 950ms out of 1000. I fixed it by switching to PyPy, and of course another option was to optimize the solution to O(N)
•  » » good! your solution quite nice and helpful, learned a lot!!!
•  » » » agree!
 » Hi, can some author pls check this my same solution got tle in contest and passes outside. TLE:- http://codeforces.com/contest/956/submission/36596404 AC:- http://codeforces.com/contest/956/submission/36601475
•  » » Submissions to problems are not yet enabled. How did you submit the solution after contest?
•  » » » I don't know about other problems but submissions for div1 d is enabled.
 » div2 E(div1 D) "That leaves us only with a binary indexed tree to be implemented." How to use a binary indexed tree to solve the problem "Inversion pairs".The only way I can find out to solve this is using set or balanced binary search tree.
•  » » Someone plz tell me about how to do it.
•  » » 4 years ago, # ^ | ← Rev. 5 →   Each plane can be represented as a line segment from (-w, a[i]) to (w, b[i]). So a pair (i, j) of 2 planes is counted if two segments are intersected. i.e. a[i] <= a[j] && b[i] >= b[j] W.L.G: a <= a <= ... <= a[n]. For each i from 1 to n, count the sum of values in [bi, ∞], then increase the value at b[i] by 1.
•  » » » "For each i from 1 to n, count the sum of value in [bi, ∞], then increase value at b[i] by 1." Yes, this is a clear way to do that. It is just like the way I found out by using set before. My way is just using a set, with inserting b[i] like your "increase value at b[i] by 1", and calculate the counts like your "count the sum of value in [bi, ∞]". Thank you.
•  » » » I spent a very little time and found out I can count the intersections of the set "segment((v+w)/x,(v-w)/x)", and I can't implemented it correctly and completely within a half our.
•  » » » I used about 25min, thinking about 2-pointers to solve this, and at last was some how convinced I should use some data-structure, and there was just 5min left.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   I understand how number of inversions can be counted with BIT. But how two different type of planes which are (left to right plane) and (right to left plane) could be treated in the same time even though -w decreases speed of left to right plane but increases speed of right to left plane?
 » In the tutorial of DIV-2D: In order to satisfy later days, ti ≥ tj - (j - i) should hold for all j > i. What does it mean by this line?
•  » » On each day we can increase t by at most one, thus ti ≥ ti + 1 - 1, which is equivalent to the condition that ti ≥ tj - (j - i) holds for all j > i.The tutorial will be updated soon, thanks for pointing out.
 » What's the best solution jury has for E? I think my solution can be optimized into S sqrt S (where S is sum of values, of course), and it's not significantly harder than S^2What was the reason of such a small S?
•  » » We know the solution, but we thought it was not interesting to accept only such solutions, the main idea is how to do the knapsack, not how to optimize it.
•  » » Anyone can explain or provide relevant link for the sqrt optimization of knapsack?Thanks
•  » » » You can check out the solution for problem "Polandball and gifts" described here:http://codeforces.com/blog/entry/49793
 » Can someone please tell me what's wrong with my code for Div2C? It is failing test #9. :( 36602743 Instead of using upper_bound to search for k (like everyone else did), I did lower_bound to search for i. According to me, it should give the same result, and I can't find my mistake. Please help! Thanks!
•  » » 4 years ago, # ^ | ← Rev. 3 →   Actually, it's not the same.For sample input:4 63 5 6 9 Answer should be: 0.75 — Triple (5, 6, 9)Your output: 0.66667 — Triple (3, 5, 9)
•  » » » It helped me a lot. Thanks!
 » My solution for E: it's clear that the bottoms of important boxes from the answer should form a subinterval [l, r] of [L, R] and their order doesn't matter; we need to put some boxes with sum of heights  ≥ L and  ≤ R - (r - l) below them let's suppose that x boxes lie completely within [l, r]; if we don't need to use all remaining important boxes to get them high enough, the answer is at least x + 1; either way, it's at least x these x boxes should be the smallest x important boxes; proof: if there's an important box a and a smaller unused important box b, we can replace a by b and decrease r; if there's a smaller important box b used below height l, we can swap a and b, which doesn't change r and increases l, creating another valid solution thanks to this observation, let's use a fast enough DP to find all heights  ≤ R reachable only using unimportant boxes; then, we can keep adding to them important boxes in the reverse order of heights and before adding each of them, find the smallest possible l (that can be constructed using boxes added so far as a subset sum) and binsearch for the maximum number of important boxes that haven't been added to the subset sum candidates yet and have height  ≤ R - l now we've got the maximum possible x (as defined above); the answer could be x + 1, but only if we construct it using these x smallest important boxes let's find all subset sums of the remaining important boxes, remove the sum corresponding to their full set and add all unimportant boxes; if we can construct a height  ≥ L and , the answer is x + 1 Here, "fast enough DP" is the classic O(RN) DP for subset sums implemented using bitsets, which give us a massive speedup, something like O(RN / 64). My code runs in 30 ms.
 » 4 years ago, # | ← Rev. 2 →   It's not hard to solve 956 A in O(n·m).Make a bipartite graph with rows and columns where row and column are connected if in there intersection there is #.Now just do Dfs on components and then check if in intersection of every row R and column C in component there is #.
•  » » 4 years ago, # ^ | ← Rev. 2 →   It's a bit advanced for problem A; we've tested it during preparation, though.
•  » » There is an easier solution with O(n*m) complexity. You can just make array, f[i] — first row such that a[f[i]][i] = '#'. Now for each row iterate over columns and if there is more than one distinct f[i] for this row, answer is no. There are some other simple cases, just look this code: 36581433
 » please help me debug this Div 2-C code. I can't figure where the mistake is submission#include using namespace std; int main(){ int n,u; cin >> n >> u; int e[n]; for(int i=0;i> e[i]; } double ans=0; int i=0,k=2,f=0; while(ku){ ++i; } if(ki+1){ f=1; ans = max(ans,(double)(e[k]-e[i+1])/(double)(e[k]-e[i])); } ++k; } if(!f){ cout << -1; return 0; } printf("%0.17f",ans); } 
•  » » You're moving the two pointers i,k in the wrong order : what you're doing is for all k increase i until (i,i+1,k) is valid, then move onto k+1. But it's possible that increasing i further for the same i yields a better result : try "4 1000 1 100 101 200" You need to increase i one by one, and for each i it's true that the largest possible k (as long as e[k]-e[i]<=u) gives the best possible answer for this i.
•  » » » Thanks a lot!. I got it now.
 » I didn't understand Div2 D solution at all. Can someone please explain elaborately?
 » My solution for D passed pretests but failed same test case in system testing (TLE) . How is that possible?? http://codeforces.com/contest/956/submission/36599452 Also i think my solution is nlogn so there should not be any problem with time? Can anyone help?
•  » » 4 years ago, # ^ | ← Rev. 2 →   don't use map. It's too slow.
•  » » » I think the problem was with long double. I was reading values directly in long double variables. Instead if i read them as int and then initialize my long double variables with integer than it takes considerably less time. http://codeforces.com/contest/956/submission/36609647
•  » » » »
 » 4 years ago, # | ← Rev. 2 →   Alternate solution for 956C - Riverside Curio:First, note that d[i] = d[i-1] + m[i-1] – m[i] + (0 or 1). The only condition is that d[i] >= 0. For each day from 2 to n, greedily "choose" +0. Now at some day i in the future, maybe d[i] turns out to be negative. In this case, we need to go back and change our choice from +0 to +1 on exactly -d[i] days.What happens if I change the choice for day j <= i from +0 to +1? I get a +1 to all d[k] s.t. j <= k <= i. So, it's easy to see that if I need to overturn a choice, I should do so for the latest day on which I made a +0 choice. That means that every time I make a +0 choice, I can just push the index in a stack, and anytime when d[i] < 0, I can pop from the stack exactly -d[i] times and add (i – stack.top() + 1) to the answer.Link — 36588535
•  » » can u please explain how is d[i] = d[i-1] + m[i-1] – m[i] + (0 or 1) this equation formed ? thankyou.
•  » » » d[i-1] + m[i-1] + 1 imply the number of marks on day i-1. So the number of marks on day i equals d[i-1] + m[i-1] + 1 + (0 or 1), (0 or 1) mean the mark on day $i$ is coincided or not. => $d[i] = number\ of\ marks\ day\ i - m[i] - 1 = d[i-1] + m[i-1] + (0\ or\ 1) - m[i]$.
 » Can anyone explain how to solve knapsack in O(S sqrt(S))?
 » ok, i just wanted to solve some of the problems, and i got stuck at B.here is my implementation.if you know, please tell me what is wrong !
 » In question 924B the output for 3 2 1 2 10 is -1. Can anyone plz explain??
 » Test cases for 924 A were weak.The grid size was 50 x 50. I solved the problem converting every row (considering # as 1 and . as 0) to a binary equivalent integer. Now, for every two rows with integer values, I was checking if (a == b) || (a & b == 0).But I took it as an integer, and so it was only taking the last 32 positions in the row. I was also checking for the column, and it was valid only for the last 32 positions in the col.With a long long integer, having 64 bits (50 required in problem), the solution should be correct.Any testcases where the grid is of size 50 x 50. And you place random elements in the top left subgrid of size 18 x 18, it should fail.But my code still passed the system testing.Link to solution: http://codeforces.com/contest/957/submission/36584331
 » 4 years ago, # | ← Rev. 4 →   Please, help! (Task D) Why does these quadratic solutions get wrong answer on test 4. http://codeforces.com/contest/924/submission/36670452. http://codeforces.com/contest/924/submission/36671090. Firstly I calculte all pairs of points of left and rihgt side. Then i iterate over all points on left and right side and check pairs o them. I tried to find a bug in this code, but I couldn't.P.S.: I undersand that i incorrectly calc pairs of points on the one side
 » For 924A can someone pls explain why it's if (a[i][k] && a[j][k]) no_intersect = false; ??? I don't understand how this if condition translates into checking for intersection. Please tell the equivalent of checking with '#' or '.'
 » My solution for div2E is giving slightly wrong ans for large testcases. Can somebody suggest why or give a smaller testcase where my code fails?
 » Could you describe your solution for Bonus2 of Minimal Subset Difference? Judging by the limits, it seems unlikely to be exponential, so I'm really curious to see what it is
•  » » 4 years ago, # ^ | ← Rev. 2 →   I'm sorry that we are going to prepare another problem related to the Bouns2 approach, so please let us suspend for a while longer before revealing it. Also, we encourage people to come up with the same idea (or better optimized) individually.
•  » » Hi, please check Petr's blog out, as he mentioned a problem like Bonus2 of MSD.
 » Regarding Problem C: Riverside Curio 1)The number of watermarks strictly above the water level on each day=m[i] and one mark is used to mark the water level so the minimum number of marks should be >=(m[i]+1), secondly, the number of watermarks on a day[i]>=day[i-1]so we should move from left to right and take the maximum of all indices to the left of index i and m[i]+1 to assign the the number of watermarks on the day i. 2)There is a possibility that after assigning the number of watermarks on each day there might exits day[i] and day[i-1] such that day[i]-day[i-1]>1 so we should remove such adjacent false relations as day[i]-day[i-1]<=1 so initialize day[i-1]+=(day[i]-day[i-1]+1) in such cases where day[i]-day[i-1]>1 and in order to do this step traverse from right to left. My submission: https://codeforces.com/contest/924/submission/94533526