Hello everyone!

Today, 8-th of April, the **third** round of the **VK Cup 2012** will take place. It's the last selection round. Let me remind you that the registration for this round is also required and it’s closed five minutes before the start.

It's rated round. It's allowed to participate out of competiotion. For all such participators it's also rated round. If you participate out of competition, you may play in the second division.

The problemset has been developed by various authors from **VK**, **Codeforces** and Saratov State University.

We worked hard to make problems more hard than usually but solvable in two hours. We hope, participation in the round will be interesting for you and only best of the best will pass to the Final Round.

This round will be run according to Codeforces rules: with room assignments, hacks and usual score decrease. It will be rated for you either if you participate in VK Cup or just solve it as a normal round.

Top **50** competitors will advance to the Final Round. VK Cup Final will occur in July in Saint-Petersburg.

Please, to make the round even more interesting for you, read the statements of ALL problems.

Good luck and try to win!

**UPD1:**

In Div. 2 Edition it will be used dynamic problem costs http://codeforces.com/blog/entry/4172. The problems will be ordered by increasing of expected difficulties, but their max scores will be determined according to the number of participants solved them.

Which will be the score distribution for the tasks? :-? 500-1000-1500-2000-2500 ?

'In Div. 2 Edition it will be used dynamic problem costs http://codeforces.com/blog/entry/4172'

When i had posted that,the "UPD1:" wasn't posted yet :P

I know.

good luck for everyone！

Ааааааа! заминусуйте меня полностью!!!

как скажешь ;-)

English translation?

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?

"Слиться" = "to fail".

Here is my translation:

I hope it'll help =)

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?

You can ask me how to fail!

он наверное уже икает)

the official contestants and unofficial contestants will be divided in Div1?(a question of room)

Official and unofficial contestants will be in separate rooms.

Division 2 problem A: I wonder when the input is: 3 10 1 1 1 Answer should be -1 isn't it? Because 3.333333*3 != 10 and the problem statement said "there were b milliliters poured in total. That is, the bottle need to be

emptied;" But the problem setter's answer is 3.333333Then, I think, you should give answer with more than 6 digits after the comma. 3.3333333*3 = 9.9999999. The difference then will be 0.0000001, while allowable deviation is 0.0000005 I guess, since the answers are rounded to the nearest number with 6 digits after the comma.

Тантай уулзсандаа баяртай байна, by the way :)

Nice to meet u too :)

i think the answer is not -1 Because, actually, there is a way to seperate the 10 cola. 10/3 for every bottle. Remember, our real world is continuous! but for computer, because of the accuracy problem, we cannot express 10/3 in fraction, so the answer is 3.333333. The answer is not precise, but it doesn't mean "no solution"

I have the same doubt. I challenged with 3 5 1 2 3 with hope of the correct answer is -1, but the official solution gives 2.666667 1.666667 0.666667 Apparently, 2.666667+1.666667+0.666667 is NOT equal to 5 in maths. Computers can't do float arithmetic accurately but that's not the point here, the problem is the result is not consistent with the statement, i.e, the bottle can't be empty at the end with such/any physically feasible distribution. In fact, 11/3 is not a finite fraction, while 11/4 is.

So I think this problem is of flaw.

A sample case for this condition would have helped during the contest.

Can anyone give some hint(s) for problem C? Thanks :)

Looks like it's mincost maxflow, what a surprise :(

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.

isn't E close to comb(n,2)?

No. You not only edges corresponding to works, but also you need edges from

ttot+ 1.Interesting name selection : Variable, or There and Back Again or "The Hobbit, or There and Back Again" :D

Problem C — Hate!

It's really similar to http://codeforces.com/problemset/problem/132/E (I think)

or http://usaco.org/index.php?page=viewproblem2&cpid=104 (although

I've read the statement. As I understand: solution = binary search by the answer + greedy. So It can be solvable

without [moncost]flows.Idea of solution is really similar.

But the problem itself, as I see, no.

D and E are too hard, and C is an old problem -- look : http://poj.org/problem?id=3680 Very unfair.

Yes, it is a bad idea to use existing tasks in general competitions.

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.org

2) Anyway, I hope, for many participators it was not too boring problem :-)

http://www.codechef.com/NOV10/problems/OVENTIME This problem is another similar (and harder) version of problem C.

When will be our ratings updated?

Mine is already updated.

Mine as well now.

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. :)

You can always save your library in Dropbox or something like that :)

http://db.tt/xvryFeon

PD. Congrats!

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 7

20 1 2 3 4 5 6

10 11 1 4 5 2 6

it returns 2, whilst correct answer is 3.

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.

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

Maybe now judge machines became faster, but I remember that before even 10^5 integers were causing time limit when reading by cin>> .

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.

I got AC with O(nlgn) complexity here:1504207

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 .

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.

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.

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).

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.

Ok, so now how do we get our T-shirts? XD

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?"

:)

I guess there should have the fourth group

4) If some competitors above us are unable to go to finals, can we get replaced?

Do we have official responses to our questions now?

When should we expect the editorial?

I wonder that who take charge of this contest. Who is the administrator that we can talk to?

There is an "in case of any questions" e-mail address in the finalist form.

Question to needing-visa finalists: Has any of you received invitation letter yet?

Problem E, I can't see the picture in problem description:

http://codeforces.com/problemset/problem/164/E

Step 5. Otherwise, find such task , that first, task ai can be done at time si = max

what is the pricture behind si=max???

Does there any dp solution exist of problem C (Machine Programming) for small constraints? Someone please give hints for dp solution.