By KAN, 4 weeks ago, translation, ,

Hi everyone!

Tomorrow, on the April 29, 2018, at 13:05 UTC we are holding the third round of VK Cup 2018 championship. This is the final online round, the next round is the final round in which top 20 teams from this round advance.

At the same time with the official round, we are holding parallel rounds for both divisions. Join them and see if you can beat top Russian-speaking teams! Top50 in the "Div1 Edition" contest will get t-shirts.

All rounds are rated, their duration is 2.5 hours.

The authors of the problems are Zlobober, Endagorion and me. Thanks qwerty787788 and gritukan for their great help in round preparation!

Good luck!

Congratulations to winners!

1. V--o_o--V, LHiC — solved all problems, two problems ahead the runner-up!
2. senek_k, demon1999
3. sinesight, SpyCheese
4. Melnik, hloya_ygrt
5. egor_bb, Nikitosh

Mirror for the first division:

Mirror for the second division:

The editorial is here, thanks all for participation!

Announcement of VK Cup 2018 - Round 3

•
• +275
•

 » 4 weeks ago, # |   -11 Parallel rounds, yeah! Hope translation of this round would be better.
 » 4 weeks ago, # |   0 Point distribution of each problem?
 » 4 weeks ago, # | ← Rev. 3 →   0 Oh, 3 Consecutive Div-2 Rated contest in three consecutive days,Its really amazing.
•  » » 4 weeks ago, # ^ |   -9 Yes, bro I think so.
 » 4 weeks ago, # |   0 Hope problem statements are clear and concise as the announcement!
 » 4 weeks ago, # |   +30 That happiness you get when you are going through your boring and monotonous life but you notice that codeforces added a new contest!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +12 Today I was running in the forest, did pull-ups on the tree branches, drank spring water from my hands, watched squirrel removing shell from a nut... but I had been interrupted by an alarm on my phone which reminded me of the contest =)
 » 4 weeks ago, # |   +7 Happiness is having codeforces round in 3 consecutive days. :DThanks a lot to the Codeforces team and the authors. :D
 » 4 weeks ago, # | ← Rev. 3 →   +9 registration of Educational Codeforces Round 43 can be closed till the system testing of this round ?!because anyone will become Div.1 in this round, the Educational Round will be rated to him as a Div.2 participantes (it's already done before)
•  » » 4 weeks ago, # ^ |   +3 They can move div 1 contestant from div 2 registration to div 1 manually. "it's already done before" too.
 » 4 weeks ago, # |   +1 CodeJam and Codeforces round in the same day. This will be challenging :D
 » 4 weeks ago, # | ← Rev. 4 →   +86 100000th contest!!!http://codeforces.com/contests/100000
 » 4 weeks ago, # |   +18 How many problems are there, and what's the score distribution?
 » 4 weeks ago, # |   -56 Too close to Code Jam 1B round :(
 » 4 weeks ago, # | ← Rev. 2 →   +51
•  » » 4 weeks ago, # ^ |   +37
•  » » 4 weeks ago, # ^ |   +24 And vs OO0OOO00O0OOO0O00OOO0OO and vs dotorya, I think.
 » 4 weeks ago, # |   +53 Score distribution?
 » 4 weeks ago, # |   +21 How many problems will be there?
 » 4 weeks ago, # |   +18 delayed...
 » 4 weeks ago, # |   +49 Please dont delay the contest. There's codejam today.
 » 4 weeks ago, # |   +34 Delayed by 10 minutes. So now I have just 15 minutes for dinner before Code Jam. :(
•  » » 4 weeks ago, # ^ |   +16 Eat fast like Major Payne.
•  » » » 4 weeks ago, # ^ |   +11 I just ate fast to finish before the start and now my stomach really hurts. (Didnt know there was a delay)
 » 4 weeks ago, # |   +20 tourist is back!!!
 » 4 weeks ago, # |   -26 Large number of hacks in Div.1 A.
•  » » 4 weeks ago, # ^ |   +23 Thank you, Cpt. Obvious. We would never have noticed that without you. You are truly the hero we need, although not the hero we deserve. /s
 » 4 weeks ago, # |   +9 World champions got first place here too !
 » 4 weeks ago, # | ← Rev. 2 →   +8 I sure am curious about the quality of system tests for D. I have a solution without proof that it works, but I sure made it hard to break without specifically breaking exactly this solution.
 » 4 weeks ago, # |   +16 How to solve C/Div1 ?
•  » » 4 weeks ago, # ^ |   +1 The condition for increasingness is "when xor-ing X with bi such that the highest set bit of bi is the d-th, the d-th bit of X must be 0". Therefore, we can group bi-s by the highest set bit.We can go from the highest to the lowest bit d and build the final sequence by merging everything with a given highest set bit with the sequence obtained in the previous step. We can't break that previous sequence this way and we only need to stuff the new bi-s at the beginning / after each 1 as the d-th bit; whether this is possible doesn't depend on what we did before.
 » 4 weeks ago, # |   +12 Answer cant be more than 5 in D right?
•  » » 4 weeks ago, # ^ |   +26 I've proved that it's always smaller than or equal to 5, or no solution exists.
•  » » » 4 weeks ago, # ^ |   +5 can you please explain why?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +14 We can find a direct path as one option. Other one is think in terms of creating a cycle(precisely three length) and then reaching n. So for no three length cycle to itself.It should be connected to rest n-2 vertices. Otherwise 3 length cycle exist. If not move one vertex down and then take a three length cycle to n because otherwise graph of n-1 vertices must be clique.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 What is the result on this test: 6 9 1 2 1 3 1 4 1 5 2 3 3 4 4 5 2 4 3 5 I see a path (1 — 2 — 3 — 4 — 5 — 2 — 6) of length 6... is there a path of length 5?
•  » » » » » 4 weeks ago, # ^ |   +5 1 — 2 — 4 — 5 — 2 — 6 is a path of length 5, for example.
•  » » 4 weeks ago, # ^ | ← Rev. 6 →   0 There are two cases(excluding the trivial ones when you can go to n using a short simple path):1) If the connected component of 1 in the original graph is not a complete graph, we can go 1->a->x->1->n, where x is not connected to 1 in original graph, but a is.2) If connected component of 1 is a complete graph not a triangle, we can go 1->x->y->z->x->1, where all x, y, z are in a's component. EDIT : This is incorrect.
•  » » » 4 weeks ago, # ^ |   0 On the second case, why can I go from z to x? Doesn't that edge erases when I visit x?
•  » » » 4 weeks ago, # ^ |   +5 In case (2) won't the z->x edge be removed when we go x->y?
•  » » » 4 weeks ago, # ^ |   0 I think the second case should be: 2) If connected component of 1 is a complete graph, and n is not in it, then answer is -1. And also case 1) is not correct. We can have a path of length 5, ig the connected component of 1 is not complete. So, if we could not found a way as described above for the first case ( 1->a->x->1->n, where x is not connected to 1 in original graph, but a is.), we can find a way (1->x->y->z->x->1) where x, y, z are in the connected component of 1, and we have the edges 1-x, 1-y, 1-z, but we don't have z-x. I have got it accepted using these changes
•  » » » » 4 weeks ago, # ^ |   +15 Ok so I can detail a bit more (sorry for the late reply, I was doing GCJ). There is no solution if and only if all nodes except 1 from 1's component are directly linked to 1 and, removing 1 from its component you're left only with cliques (all the components are complete). Broadly speaking, my solution was something like:Consider the optimal solution x1, x2, .., xK. Either they are all distinct which means the edges should be those from the initial graph, or at least 2 are equal. Let j be the smallest index for which you also have iN? Obvious solution2) A direct path from 1 to N of length 2 or 3? Definitely optimal, cause you can't get any better by doubling a node (you'd need 1 x y 1 N in the best case for a node-doubling option)3) Does the component of 1 also include a node that is not directly connected to 1? Then there must be a node at distance 2 as well (you can get it through bfs). You can then obtain 1-x-y-1-N which has length 4, definitely optimal4) All nodes in 1's component are directly linked to it. Delete 1 from its component and now you may assume that you can start from any point. Since you can start from any point and you want to minimize j so that x[j] = x[i], you may choose i = 1, x[j] = x[1] (why not, there's no use into delaying the occurrence of that thing, provided you can start anywhere). If all components are cliques, you definitely can't do anything, cause as I said for that double node to exist there must be 2 vertices x[j — 1] and x[j]=x[i] which don't have an edge in the initial graph, and since it's impossible to find that here, you have no solution. If at least one pair of nodes S, T exists where S and T are connected (provided you erased 1), You may run a bfs from S, and find at least one node T' at distance 2 (since from the existence of T, you know they are not all linked to S). Then you may have the following path 1-S-midNode-T'-S-N which has length 5, again optimal.
 » 4 weeks ago, # |   +3 what is the hack for div1 A?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 2 5 1 0 1211 4 1 5
•  » » » 4 weeks ago, # ^ |   0 LOL
 » 4 weeks ago, # | ← Rev. 2 →   +138 ![ ]()
•  » » 4 weeks ago, # ^ |   0 Now, I regret why my solution wasn't hacked so that I can check this case! My solution will be wrong now! :(
 » 4 weeks ago, # |   +11 What is pretest 11 in Div1D?
•  » » 4 weeks ago, # ^ |   +10 I am guessing it is: one's connected component is a triangle, not containing n. Answer is -1 then. BTW, Is the answer always <= 5?
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 My code works on this test case, but probably something similar fails it.And yes answer is always smaller than 5 if not  - 1, if 1 N is closed, and there is a vertex u at distance = 2 from 1, then the edge 1 u is intially closed, and opens once you leave 1, so you can travel from 1 to u to 1 to N.EDIT: This is wrong, see my other comment.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I got WA on the same pretest. My solution was to do a DFS for paths of length no more than 3. If we are able to reach N than that is the solution. Otherwise if there is a path of length 2 from 1 to some other node X, then we can go from X to 1 (because the tunnel is now open) and then from 1 to N.What is the flaw in this logic?
•  » » » 4 weeks ago, # ^ |   +8 Cerberus97 found a countertest (fails my code at least) 5 5 1 2 1 3 1 4 2 3 3 4 path is 1 2 3 4 2 5
 » 4 weeks ago, # |   +139 Hate rounds with so many hacks. What's sad is that there are some people who treated that case, but treated it wrong (one of my few hacks was on a poor guy who was printing y1-y2, provided y1
•  » » 4 weeks ago, # ^ |   0 I treated the case correctly but forgot to add line separators :/
 » 4 weeks ago, # |   +32 if(r1==r2) { printf("%d\n", abs(c1-c2)); } Forgot the "continue;" in Div1-A :D :D
•  » » 4 weeks ago, # ^ |   +53 I also forgot the if(r1==r2) { printf("%d\n", abs(c1-c2)); } 
•  » » » 4 weeks ago, # ^ |   +4 Even the mighty fall! :P
 » 4 weeks ago, # |   +1 How to solve div1A? binary search + greedy? min(only run, min(take nearest elevator(left), take nearest elevator(right)))?
•  » » 4 weeks ago, # ^ |   0 Yes, I did it that way, but I handled the binary search part by using Java's TreeSet (which internally is a red-black tree implementation). A special case is when the starting and the ending rooms are on the same floor — in that case you don't need any stairs, nor elevators. :)
•  » » 4 weeks ago, # ^ |   0 we both are winning or losing together today.
•  » » 4 weeks ago, # ^ |   0 yes if you consider a stair being an elevator with maximum speed 1
 » 4 weeks ago, # |   +1 How to solve Div1B/Div2D?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +21 I have written a greedy solution which passed pretests:chose larger x (from x1 and x2). Try to assign them greedily from larger server size. Choose lower server till it works (v/2, v/3, v/4..).Then do the same with remaining one.if any one doesn't work, swap x1, x2. Repeat. Edit: It failed on test 40. Not sure why. Take this solution with a grain of salt. Edit2: Okay, Algorithm is 100% correct. My http://codeforces.com/contest/967/submission/37727934 was also correct for test40. I switched the order while printing the answer, Also it was last damn test case.
•  » » » 4 weeks ago, # ^ |   -10 mkagenius I did it the same way. And I also got WA on test 40 :)
•  » » » » 4 weeks ago, # ^ |   0 Okay, that hints towards wrong algorithm unless we made same coding mistake (quite unlikely unless a silly one).
•  » » » » 4 weeks ago, # ^ |   0 mkagenius ok, i was just simulating for max(x1, x2) and not for both. That's so silly.Here's the Accepted sol: http://codeforces.com/contest/967/submission/37740696
•  » » » » » 4 weeks ago, # ^ |   0 bad luck, and only test was there with reverse order.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 this is my Alg "not greedy" https://ideone.com/kCGiVY
•  » » » 4 weeks ago, # ^ |   0 Could you please explain it?
 » 4 weeks ago, # |   +1 How to solve div2 D / div1 B ?
•  » » 4 weeks ago, # ^ |   0 Sort the array elements in pairs(ar[i],i). Now assuming each array element of the sorted array s_ar[i] as the minimum element for two types of services separately, find j so that (j-i+1)*s_ar[i].first >= x1 and store in cal[i] for 1st type and similarly store for 2nd type in val[i] . Now check if there exists i
 » 4 weeks ago, # |   0 Can O(m sqrt(n) log(n) log(sqrt(n)) solution pass Div 1 E?
•  » » 4 weeks ago, # ^ |   +5 Yes (sadly)
•  » » » 4 weeks ago, # ^ |   0 I gave up this contest after reading E cause I had no better idea...
 » 4 weeks ago, # |   +1 I liked this contest a lot, the problems that I tried all seemed (particularly Div2D) were really interesting to think about but at the same time not all that hard to implement. Great job to writers! (Although div2 A was a bit hard)
 » 4 weeks ago, # |   0 Can someone tell me why this solution for Div 1 — C : http://codeforces.com/contest/966/submission/37727089 is giving me tle. It is a O(n * 60) solution.
 » 4 weeks ago, # | ← Rev. 2 →   +10 What happened with D in official round? UPD: everything is okay now.
 » 4 weeks ago, # |   +3 The night of failing system test... I just wanna cry.
 » 4 weeks ago, # |   +195 Cheater exposed.![ ]()
 » 4 weeks ago, # | ← Rev. 2 →   +3 What the heck!!! in Div2C?
 » 4 weeks ago, # | ← Rev. 2 →   0 Div-2-D1st testcase :6 8 163 5 2 9 8 7output:YES2 22 65 4Whats wrong here???
•  » » 4 weeks ago, # ^ |   +2 It should be "Yes"
•  » » » 4 weeks ago, # ^ |   0 Got WA on 1st case
•  » » » » 4 weeks ago, # ^ |   +5 Maybe "YES" should be "Yes"
•  » » » » » 4 weeks ago, # ^ |   0 As far as i know , CF consider same between Yes and YES..
•  » » » » » » 4 weeks ago, # ^ |   0 Not in this problem. I made the same mistakes too.
•  » » » » » » 4 weeks ago, # ^ |   0 Each problems have their own checkers. If the checker considers them different, only Yes will be accepted.
•  » » » » » » 4 weeks ago, # ^ |   0 Usually, problems give you know that there is no difference between Yes and YES.
•  » » » 4 weeks ago, # ^ |   0 I thought they didn't check case. They keep changing rules.
•  » » » » 4 weeks ago, # ^ |   0 It's not that 'they' change the rules. It's the setters' responsibility to make checkers for each problem, and it's up to them whether they'll allow different cases or not.
•  » » » » » 4 weeks ago, # ^ |   +5 Maybe it should not be left for the setter (unless explicitly specified that case matters) Coz people have lost points due to wrong hacking attempts in the past. Either way it should be documented either globally or per contest that case matters or not.
 » 4 weeks ago, # |   +8 Explain me, please, which rounds have got "practice" and which — hasn't?
•  » » 4 weeks ago, # ^ |   0 I think almost every CF contest have "pratice". But there is some time after the contest (approximately 30 minutes) when you can't submit your solutions
•  » » » 4 weeks ago, # ^ |   +5 Thank you!
 » 4 weeks ago, # |   0 I don't understand why there is so few submissions for div1 D. It is just simple case analysis
 » 4 weeks ago, # |   0 How to solve Div1E?
•  » » 4 weeks ago, # ^ |   +58 You know you solved it, right?
•  » » » 4 weeks ago, # ^ |   +1 Eh, my solution is really weird (O(qn^0.5log^2n)) and I bet there is a better one
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +63 I can offer O(n2) in 1.7s, Maybe it's better in some way =)
•  » » » » » 4 weeks ago, # ^ |   +49 Wow, you always amaze me :o
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 i solved it in nlognsqrtn with some optimizations.
•  » » 4 weeks ago, # ^ |   +2 you solved it :)
•  » » 4 weeks ago, # ^ |   +35 Split queries in blocks of size k. For each block build compressed tree consisting of vertices that change in this block, their lcas and the root. For each edge in this compressed tree, store all balances for vertices on that edges in sorted order. When some vertex changes, change all its ancestors and for each edge on the path to root you need to add\subtract 1 from all balances on that edge. You need binary search for it so this solution works in . But you can get rid of it if you notice that you don't need to store balances with absolute value greater that k. Then it will work in . I had no time to implement this optimisation and got OK without it. Sadly I spent 40 minutes solving B, so I wrote E few minutes before the end and had no time to debug it.
 » 4 weeks ago, # |   +34 last tshirt wowoowoooowow
 » 4 weeks ago, # |   +1 Got WA on pretest 7 for problem C Div.2, does anyone know what this case was? My approach as just print abs(y1-y2) if on the same floor, otherwise binary search for closest elevator and for closest stairs and print the minimum of the two.
•  » » 4 weeks ago, # ^ |   +5 Closest may not be optimal. You have to check closest on both sides of your current location.
•  » » » 4 weeks ago, # ^ |   0 Damn how did I never think of that, thank you
•  » » » 4 weeks ago, # ^ |   0 Still getting WA, here is a link to my submission if you would mind telling me what is wrong.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 equal_range(stairs.begin(),stairs.end(),y1); Why do they have to be equal to current location?
•  » » » » » 4 weeks ago, # ^ |   0 That's equivalent to make_pair(lower_bound(stairs.begin(),stairs.end(),y1),upper_bound(stairs.begin(),stairs.end(),y1));
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 Okay. Well, that doesn't serve the purpose -- that will always fetch positions on the equal or right of current. left side remains unexplored.Use lower_bound and lower_bound — 1.
•  » » » » » » » 4 weeks ago, # ^ |   0 Thank you
 » 4 weeks ago, # |   0 Can anybody help me why my solution to problem c of DIV2 failing 8th test case. Actualy it is giving output in exponential form which I am unable to understand why?.Any kind of help would be appreciated. submission link
•  » » 4 weeks ago, # ^ |   +4 I'm pretty sure fabs(x) returns a double so replace it with abs(x) and it should print correctly.
•  » » » 4 weeks ago, # ^ |   +6 Thanks..It worked !!
 » 4 weeks ago, # |   +10 for div 1 C i chose greedily the minimum value with which we should xor so that we can find the next value in a which is greater than the previous value. I used trie with deletion. Here is the code . http://codeforces.com/contest/967/submission/37730673. Why doesnt it work ?
•  » » 4 weeks ago, # ^ |   0 because there is a counterexample !
•  » » 4 weeks ago, # ^ |   0 If you will "chose greedily the minimum value with which we should xor so that we can find the next minimum value in a which is greater than the previous value", you will get AC.
•  » » » 4 weeks ago, # ^ |   0 i am sorry for my english sentence, but i did what you told. plz see my submission.
•  » » » » 4 weeks ago, # ^ |   0 I have solved the problem in that way during the contest. So it should work and you should look for bugs in your code. Btw, your trie implementation is a bit terrible at first glance =)
•  » » » » » 4 weeks ago, # ^ |   0 Ok. N dont we need trie ?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 You have a bunch of places where you need to use long long. A few examples I found: 1<
•  » » » 4 weeks ago, # ^ |   +8 i have given this statement #define int long long. N i corrected some places where i have given 1<
 » 4 weeks ago, # |   +70 You can assume you don't have to wait for an elevator
 » 4 weeks ago, # |   +10 A good contest.But it has too long background for its problem.
 » 4 weeks ago, # |   +5 Damn, my solution got hacked just because I missed one =` sign in comparison! This is gonna be a good lesson for me! :-(