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

please give hints in problem "E(IT Restaurants)"..thanks!

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.

Хера се он по-английски строчит! о.О

З.Ы. В смысле я восхищен донельзя.

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.

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.

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.

Is there gonna be editorial for this contest or should I post solution for problem A here?

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

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.

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?

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

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.

Based on feedback about final I can only hope that next year VK would waive age restriction

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.

Thanks for the really great event. This was definitely one of the best onsite competitions I've been to.

Sorry to Interrupt, but will it have an editoral after the unoffical contest?

A very nice competition! I can't believe every finalist can have a laptop! Thanks to VK and congratulations to the winners!

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 ?

So I am not joining( fair enough ).

Of course, yes.

The same problem set will be given in the unofficial VK final?

Congratulate to winners! This competition is really nice!I enjoyed it very much ^_^ And I'm very happy to take home a cool laptop.

thought that tourist would have first place,congrats to winners and organizers for the great contest

Congratulations to 7k+ and s-quark! Thanks to VK, a very nice contest!

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

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

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

When should we expect the editorial?

Do we have official responses to our questions now?

I guess there should have the fourth group

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

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

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

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

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

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

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

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

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.

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.

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.

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 .

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.

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

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

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

Here is my translation:

1. I log in Codeforces.
2. Here I must be in top-300.
3. There I have to be in top-50.
4. And where I can fail?

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?

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

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?

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.

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.

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

http://db.tt/xvryFeon

PD. Congrats!

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

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

Mine as well now.

Mine is already updated.

When will be our ratings updated?

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

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

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

Nice to meet u too :)

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

Problem C — Hate!

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.

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.

Interesting name selection : Variable, or There and Back Again or "The Hobbit, or There and Back Again" :D

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"

Then, 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 :)

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

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

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

Official and unofficial contestants will be in separate rooms.