### cyand1317's blog

By cyand1317, 22 months 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

• +114

 » 22 months ago, # |   0 Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).
 » 22 months ago, # |   0 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)
 » 22 months ago, # |   0 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
•  » » 22 months ago, # ^ |   0 Submissions to problems are not yet enabled. How did you submit the solution after contest?
•  » » » 22 months ago, # ^ |   0 I don't know about other problems but submissions for div1 d is enabled.
 » 22 months ago, # |   0 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.
•  » » 22 months ago, # ^ |   0 Someone plz tell me about how to do it.
•  » » 22 months ago, # ^ | ← Rev. 5 →   +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[1] <= a[2] <= ... <= 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.
•  » » » 22 months ago, # ^ |   0 "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.
•  » » » 22 months ago, # ^ |   0 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.
•  » » » 22 months ago, # ^ |   0 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.
•  » » » 22 months ago, # ^ | ← Rev. 3 →   0 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?
 » 22 months ago, # |   0 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?
•  » » 22 months ago, # ^ |   +1 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.
 » 22 months ago, # |   0 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?
•  » » 22 months ago, # ^ |   +40 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.
•  » » 22 months ago, # ^ |   +20 Anyone can explain or provide relevant link for the sqrt optimization of knapsack?Thanks
•  » » » 22 months ago, # ^ |   +25 You can check out the solution for problem "Polandball and gifts" described here:http://codeforces.com/blog/entry/49793
 » 22 months ago, # |   0 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!
•  » » 22 months ago, # ^ | ← Rev. 3 →   0 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)
•  » » » 9 months ago, # ^ |   0 It helped me a lot. Thanks!
 » 22 months ago, # |   +21 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.
 » 22 months ago, # | ← Rev. 2 →   +18 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 #.
•  » » 22 months ago, # ^ | ← Rev. 2 →   +12 It's a bit advanced for problem A; we've tested it during preparation, though.
•  » » 22 months ago, # ^ |   0 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
 » 22 months ago, # |   0 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); } 
•  » » 22 months ago, # ^ |   +1 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.
•  » » » 22 months ago, # ^ |   0 Thanks a lot!. I got it now.
 » 22 months ago, # |   +3 I didn't understand Div2 D solution at all. Can someone please explain elaborately?
 » 22 months ago, # |   0 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?
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 don't use map. It's too slow.
•  » » » 22 months ago, # ^ |   0 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
•  » » » » 22 months ago, # ^ |   0
 » 22 months ago, # | ← Rev. 2 →   +6 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
 » 22 months ago, # |   0 Can anyone explain how to solve knapsack in O(S sqrt(S))?
 » 22 months ago, # |   0 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 !
 » 22 months ago, # |   0 In question 924B the output for 3 2 1 2 10 is -1. Can anyone plz explain??
 » 22 months ago, # |   0 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
 » 22 months ago, # | ← Rev. 4 →   0 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
 » 22 months ago, # |   0 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 '.'
 » 22 months ago, # |   0 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?
 » 21 month(s) ago, # |   0 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
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 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.
•  » » 10 months ago, # ^ |   0 Hi, please check Petr's blog out, as he mentioned a problem like Bonus2 of MSD.