VK Cup 2012 — Финал!
By MikeMirzayanov, 12 years ago, translation, In English

Today is the main VK Cup event: VK Cup 2012 Finals! Good luck to all participants. And to those who don't participate — enjoy the interesting competition. VK CEO Pavel Durov announced the upgrade of a prize fund in the greeting speech at the finals' opening! I'm starting to really regret that I am not a participant.

The participants compete for:

  • 1st place — $30000
  • 2nd place — $20000
  • 3rd place — $10000
  • 4-5 places — $2000
  • 6-10 places — $1000

Good luck! Wish you only positive emotions. Ready! Steady!...

UPD: The contest is over! I believe Alex_KPR will write about the contest and the closing ceremony soon. Thank you for participation and your interest. Here are the complete standings.

Congrats to the winners. The top-3 is:

UPD: As you have already noticed, the 16th July at 19:00 will start an unofficial online-version of the VK Cup 2012 Finals. Anyone can participate and feel himself as a finalist. Round will be unrated. If you already took part in the Finals or familiar with the problems, please refrain from participation. All problems will appear in the archive and will be available to everyone.

Announcement of VK Cup 2012 Finals
  • Vote: I like it
  • +76
  • Vote: I do not like it

Comments Comments (21)
| Write comment?
»
12 years ago, # |
  Vote: I like it +66 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -18 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +74 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
»
12 years ago, # |
  Vote: I like it +39 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +66 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +58 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +43 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it -7 Vote: I do not like it

          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?

          → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +12 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +17 Vote: I do not like it

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

            → Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 3   Vote: I like it +33 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +11 Vote: I do not like it

      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.

      → Reply