Recent actions
 On Alex_KPR → VK Cup 2012 Finals: Day 3, 22 months ago +3 Ok, i need more 2 friends to take a picture with me, i could be the winner of 2018. Just kidding, but maybe it work :pAmazing coincidence!!!
 On Alex_KPR → VK Cup 2012 Finals: Day 3, 22 months ago +56 First one is a good photo — exactly one member out of winning ACM team in each of years 2013, 2014, 2015, 2016 :P (photo taken before any of them).
 On Burunduk1 → VK Cup 2012 Round 3, 2 years ago 0 Problem E, I can't see the picture in problem description:http://codeforces.com/problemset/problem/164/EStep 5. Otherwise, find such task , that first, task ai can be done at time si = maxwhat is the pricture behind si=max???
 On MikeMirzayanov → VK Cup 2012 Qualification Round 1, 3 years ago +9 RIP not bumping old posts, rather
 On MikeMirzayanov → VK Cup 2012 Qualification Round 1, 3 years ago -23 .
 On Burunduk2 → VK Cup 2012 Round 1, 4 years ago 0 Hii,Can anyone suggest me why my O(nk) solution is giving me a TLE?? i'm just doing 'n' times DFS with a Depth bound of 'k'.You can find my submission here.Thank you
 On MikeMirzayanov → VK Cup — Computer Programming Championship, 5 years ago -16 I estimate probability of this to be 20%. Otherwise why VK security guards quickly hid suspect inside the building? If this was not Pavel Durov — why not to tell the police who he was and give all the materials (like video from inside)?
 On MikeMirzayanov → VK Cup — Computer Programming Championship, 5 years ago +27 We do not know for sure whether he really hit police officer or is it just a VK raider seizure attempt with the assistance of police (which is quite common in Russia). VK stock manipulations happening at the same time suggest the seizure attempt.
 On MikeMirzayanov → VK Cup — Computer Programming Championship, 5 years ago +28
 On MikeMirzayanov → VK Cup — Computer Programming Championship, 5 years ago -6 bad news.
 On MikeMirzayanov → VK Cup — Computer Programming Championship, 5 years ago +12 Looks like Pavel Durov has more serious problems to resolve now. And this requires a lot of money — hasn't been left for the contest =)P.S. It was not good idea to hit police officer by car...
 On MikeMirzayanov → VK Cup — Computer Programming Championship, 5 years ago +15 Does anybody know when is the next VK Cup round (VK Cup 2013) ?
 On MikeMirzayanov → VK Cup — Computer Programming Championship, 5 years ago +24 Yep. I've got it today
 On MikeMirzayanov → VK Cup — Computer Programming Championship, 5 years ago +14 Not yet. Hope to get before VK CUP 2013.
 On MikeMirzayanov → VK Cup — Computer Programming Championship, 5 years ago +14 Anyone who is not in onsite received T-shirt?
 On MikeMirzayanov → VK Cup 2012 — Финал!, 5 years ago 0 please give hints in problem "E(IT Restaurants)"..thanks!
 On MikeMirzayanov → VK Cup 2012 — Photos, 6 years ago Created or updated the text
 On MikeMirzayanov → VK Cup — Computer Programming Championship, 6 years ago 0 nothing
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago +11 I know a slightly different solution, which reduces the problem to Bipartite Graph Edge Coloring.The problem is, given a Bipartite Graph, color every edge such that if two edges meet at a vertex, they are colored different. It can be proved that the minimum number of color required is ∆, the maximum degree of a vertex. The coloring can be found in O(VE).For each vertex v in the original graph, we split it into ceil(deg(v) / t) vertex. The first trunc(deg(v) / t) vertex has degree t, while the last one has degree deg(v) mod t. The edges can be distribute to them arbitrary. The new graph has a maximum degree t, which means we can color the edges using t colors. The coloring on the new graph is the coloring we want.
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago -50 Хера се он по-английски строчит! `о.О`З.Ы. В смысле я восхищен донельзя.
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago +1 Good job!During the contest I coded the same solution without ensuring the lower bound conditions, and it failed as expected.Actually every iteration can be viewed as the circulation problem since we have lower bounds on flow for some edges, I've got AC this way. It doesn't give any proof that the solution always exists, though.
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago +33 OK, here you go.It’s obvious that the answer can’t be smaller than the number of nodes with degree not divisible by t. To achieve this value, every node v must have between floor(deg[v]/t) and ceil(deg[v]/t) outgoing edges of each of t colors (deg[v] is the degree of node v). Let’s construct such coloring and prove its existence by induction alongside.For t = 1 the result is obvious. For bigger t we find the set of edges to be painted with color t, delete this edges from the graph and continue the process for t-1. It’s easy to see that the final result will meet all the conditions. So why such set of edges for color t always exists?To find it, we add edges from source to the nodes of the first part and from nodes of the second part to the sink with capacity ceil(deg[v]/t) and find max flow. Now we need to ensure that lower bound condition for the flow from (or to) each node is satisfied.Let’s take a node v0 with flow less than [deg[v0]/t]. To increase the flow in that node, we need to find a path v0 -> u1 -> v1 -> … -> un -> vn, where nodes vi are from first part and ui from second, the edges in this path are in turn not-filled and filled with flow, and flow in node vn can be decreased (> [deg[vn]/t]). After that we just swap the flow between neighbouring edges.To complete the proof, we need to show that such path always exists. Assume the opposite. Let V and U be the sets of nodes from respective parts reachable from v0 by given method (from vi we take all not-filled edges, from ui all filled). Flow in each node from U equals ceil(deg[ui]/t), otherwise we could increase the total flow. By assumption, flow in each vi is <= [deg[vi]/t] and at least for one node the inequality is strict.Now if we count the total number of edges filled with flow between V and U in two ways — as edges starting from V, and as edges starting from U, then use inequalities listed above and the fact that [x] = floor(x) <= x <= ceil(x), we’ll get deg[V] > deg[U] for total degree of nodes. If we count the total number of edges not-filled with flow in the same manner, we’ll get deg[V] < deg[U]. This contradiction ends the proof.
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago 0 I also get accepted (without seeing your solution), and it turns out that our methods are similar. I just wonder how to prove the correctness.
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago +11 Is there gonna be editorial for this contest or should I post solution for problem A here?
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago +17 Anyway, this competition is a way for VK to look for new employees, and VK is interested in young (<=23yo) developers only. Don't ask me why: I cannot answer this question :)
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago +12 IMO age correlation with "hardness" is far from 1. They can make the rule similar to ACM ICPC's (i.e. <=const VK CUP finals per person), or just allow participation only to the ones who never participated in any onsite (i.e. IOI, ACM ICPC finals, GCJ finals, topcoder oncite, facebook finals, etc.). This way is much more effective for getting rid of hardened people :) Though I doubt this (getting rid of hardened people) is a very good idea.
 On Alex_KPR → VK Cup 2012 Finals: Day 3, 6 years ago +9 Awesome blog..Very nice descriptions and photography :) Just one question .. Cant we have the expected scores besides the question mark in the regular contests like in this
 On Alex_KPR → VK Cup 2012 Finals: Day 3, 6 years ago Created or updated the text
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago -7 I don't understand what people's age has to do with their fame and "hardness" in terms of programming contests. If organizers don't want well known and strong people at the finals, why not to cut them off based on their skills? We have ratings here and at TopCoder, so let's ban all people who's rating (or its maximum value) is higher than some threshold?
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago 0 Well, currently it leaves tourist as huge favorit (althrough we can see, from this contest as well, that luck is a big factor in onsite tournaments). Now competitors are randomly divided by age: some tops are eligible, some not, and I see no real reason behind this
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago +43 Pavel Durov told us that they are not interested in giving first prizes to known hardened people like Petr, because it's not so interesting.
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago +26 Based on feedback about final I can only hope that next year VK would waive age restriction
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago +58 Me too, VK is really the winner of the contest of contests. VK really make everyone happy in the event, including the participant like me that not performed well at the final round.By the way, I found my name-card with red handle, but in fact I'm yellow. So I want to become red by the final round. But unfortunately I become more 'yellow' caused by mistakes in different problems. So it gives me a lesson: coding/thinking carefully (and maybe checking twice) is more important to the speed of coding.
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago +66 Thanks for the really great event. This was definitely one of the best onsite competitions I've been to.
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago +7 Sorry to Interrupt, but will it have an editoral after the unoffical contest?
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago +39 A very nice competition! I can't believe every finalist can have a laptop! Thanks to VK and congratulations to the winners!
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago 0 I think there are some problems with Codeforces system after the contest. When I submit an AC solution with time 0.4s, it turn to about 1s now :-s Anybody has the same situation ?
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago Created or updated the text
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago -14 So I am not joining( fair enough ).
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago +3 Of course, yes.
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago -10 The same problem set will be given in the unofficial VK final?
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago +74 Congratulate to winners! This competition is really nice!I enjoyed it very much ^_^ And I'm very happy to take home a cool laptop.
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago -18 thought that tourist would have first place,congrats to winners and organizers for the great contest
 On MikeMirzayanov → VK Cup 2012 — Финал!, 6 years ago +66 Congratulations to 7k+ and s-quark! Thanks to VK, a very nice contest!
 On Alex_KPR → VK Cup 2012 Finals: Day 2, 6 years ago Created or updated the text
 On Alex_KPR → VK Cup 2012 Finals: Before the Opening Ceremony, 6 years ago Created or updated the text
 On MikeMirzayanov → VK Cup 2012 Final — coming soon!, 6 years ago 0 Best of luck Rudy (rudradevbasak) :) Make all Indians proud as you have been doing for a long time :)
 On MikeMirzayanov → VK Cup 2012 Final — coming soon!, 6 years ago -19 then tourist is going to earn 20.000\$... congratz :)
 On MikeMirzayanov → VK Cup 2012 Final — coming soon!, 6 years ago +6 Is there any dress code?
 On MikeMirzayanov → VK Cup 2012 Final — coming soon!, 6 years ago 0 No.
 On MikeMirzayanov → VK Cup 2012 Final — coming soon!, 6 years ago 0 May we use printed or hand-written materials?
 On MikeMirzayanov → VK Cup 2012 Final — coming soon!, 6 years ago +21 The post has been updated with questions and answers.
 On MikeMirzayanov → VK Cup 2012 Final — coming soon!, 6 years ago Created or updated the text
 On MikeMirzayanov → VK Cup 2012 Final — coming soon!, 6 years ago 0 ... it's FANTASTIC! ...
 On MikeMirzayanov → VK Cup 2012 Final — coming soon!, 6 years ago +10 ...number of zeros in cash prizes O_O ...
 On MikeMirzayanov → VK Cup 2012 Final — coming soon!, 6 years ago +15 i have a dream...
 On MikeMirzayanov → VK Cup — Computer Programming Championship, 6 years ago Created or updated the text
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago 0 Question to needing-visa finalists: Has any of you received invitation letter yet?
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +8 There is an "in case of any questions" e-mail address in the finalist form.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +18 I wonder that who take charge of this contest. Who is the administrator that we can talk to?
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +10 When should we expect the editorial?
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +28 Do we have official responses to our questions now?
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +31 I guess there should have the fourth group4) If some competitors above us are unable to go to finals, can we get replaced?
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +1 http://www.codechef.com/NOV10/problems/OVENTIME This problem is another similar (and harder) version of problem C.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +43 VK Cup Round 3 participants can be divided into 3 groups:1) "When our ratings will be updated?"2) "Ok, so now how do we get our T-shirts?"3) "When we will get our tickets to final?":)
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago 0 I've read the statement. As I understand: solution = binary search by the answer + greedy. So It can be solvable without [moncost]flows.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +8 Idea of solution is really similar.But the problem itself, as I see, no.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +21 I agree, it's not good idea to use old problems.1) I'm sorry, but authors of the contest are all from Russia, we just did not know about task 3680 from poj.org2) Anyway, I hope, for many participators it was not too boring problem :-)
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +28 Ok, so now how do we get our T-shirts? XD
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago -17 как скажешь ;-)
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago 0 I got AC with O(nlgn) complexity here:1504207
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago 0
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago 0 That is a more philosophical discussion (and, for example, problems on TopCoder are much different in this regard from ACM or CF). I believe that authors may choose to require a faster (asymptotically or practically) solution from the participants if they believe that it is important for the problem. In fact, time limits are often chosen so as to rule out programs with too high a constant (time limits on CF are actually quite loose most of the time, but make sure to visit CodeChef for some really painful series of TLEs ;) ). That being said, differentiating between O(n) and O(n log n) is very hard, because an nlogn solution with a FastIO implementation (own i/o parsing, much faster than scanf) often runs faster than a vanilla O(n) implementation. But there usually is a real difference between O(n log^2 n) and O(n log n).
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +9 Thanks for the common knowledge anyway. It is amazing but this makes cin faster than scanf (makes sense seeing how it does the "%d" part in compile time). I guess the issue is that you cannot use scanf anymore, not going to miss it.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago -16 And what is the point to rule out O(n log n)? I actually have a hard time thinking of a problem in which banning logarithmic factors actually made the problem more interesting rather than more annoying. (This effort to add artificial difficulty to B seems strange considering how they left a standard Max Flow problem in C).If they want to enforce scanf or esoteric common knowledge, that's fine but they should at least include the usual warning about that.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +10 It's common knowledge that in order to use cin for big inputs you have to use: ios_base::sync_with_stdio(0); This 1505453 is your submission with this line added.The limit of 10^6 is entirely normal for such a problem. Maybe it was also meant to rule out slow O(n log n) solutions.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +2 Same thing happens to me ... tle for using cin ... may b psetter should b little more responsible to give warning in such kind of huge input limit .
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago -21 IMHO, time limit for this problem is too strict. O(nlogn) looks reasonable for n=10^6. But I couldn't make it pass even with faster IO.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +3 Maybe now judge machines became faster, but I remember that before even 10^5 integers were causing time limit when reading by cin>> .
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago -16 So I just fixed my time out in B... By switching from cin to scanf... (and now I pass with 0.7s worst time).Guess the big input warning was missing in the warning. I find this very strange though, cause I don't remember having issues with 10^6 inputs before. Maybe it is that all the ints are in the same line and cin uses some sort of buffer for lines? I have no idea.But I think that making a non-bugged linear-time solution was interesting enough, The problem was fun without having to resort to scanf to optimize input time. I see no point in not using 10^5 as constraint for this problem. Also, I think that problems with 10^6 input should have at least a 3 seconds limit to compensate how it seems that at least 2 seconds are spent in i/o when using cin/something other than C instead of scanf :/But it is
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago 0 A sample case for this condition would have helped during the contest.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +11 Here is my translation: I log in Codeforces. Here I must be in top-300. There I have to be in top-50. And where I can fail? I hope it'll help =)
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +17 Approximate meaning: 1)I enter Codeforces 2)Here I need to get in Top-300 2)Here I need to get in Top-50 4)When will be the round which I can fail?
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago 0 "Слиться" = "to fail".
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago 0 I could only get the first three pics (using google translate, nothing special: I really can't get a word of Russian). The first says: "Join here in Codeforces". The second: "You! You've got to get on the top-300". Third: "You -- on the top-50"I can't really understand the last one. Any hint?
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago -16 Can somebody please give the test 22 for the task A (it would be even better to get the shorter version of it)?Edit. Ok I found easier counterexample for my solution, no need for this test now.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago 0 I think that the tests for the task B are too weak. I resubmited my solution 2 times, whilst the first incorrect version passed: http://pastebin.com/EztLGpMY . Counterexample:7 720 1 2 3 4 5 610 11 1 4 5 2 6it returns 2, whilst correct answer is 3.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago 0 You can always save your library in Dropbox or something like that :)http://db.tt/xvryFeonPD. Congrats!
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +44 It's one of the most thrilling match that I have played.In the first half hour, I did really stupid things(Misunderstand the Problem A, and then make 7 wrong try), and get very inpatient. Then I found 30+ minutes pasted and my A got only 180pt, it was really desperate.Fortunately, I came up with the solution just after reading the problem B. And for problem C, I got very sad when I found it was a very classical min-cost-max-flow problem . I have just re-installed my OS, and I haven't copy the code-library. So it costs me about 10 minutes looking for my code in TC.And the most thrilling part is waiting the result. My rank was 67 before start testing. When my code is running, I got very intense.Lucky, I passed 3 problems, and advanced. :)
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +7 Yes, it is a bad idea to use existing tasks in general competitions.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago 0 Mine as well now.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +5 Mine is already updated.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago 0 When will be our ratings updated?
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +3 No. You not only edges corresponding to works, but also you need edges from t to t + 1.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +5 isn't E close to comb(n,2)?
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +99 D and E are too hard, and C is an old problem -- look : http://poj.org/problem?id=3680 Very unfair.
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago -7 Nice to meet u too :)
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +6 It's really similar to http://codeforces.com/problemset/problem/132/E (I think)
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +91 Problem C — Hate!
 On Burunduk1 → VK Cup 2012 Round 3, 6 years ago +39 MinCostFlow. Vertex is a time, and work is a edge with capacity=1 and cost=-C. We need to find minimal cost flow not greater than K. V~1000, E~1000 and you even don't need Dijkstra's algorithm with potentials.