VK Cup 2012 Round 1
By Burunduk2, 12 years ago, translation, In English

Hello everyone!

It's time for the first round of the VK Cup 2012. Let me remind you that the registration for this round is also required and it's closed five minutes before the start.

The problemset has been developed by various authors from VK, Codeforces and Saratov State University. We worked hard to make this time interesting for competitors and to have the best ones in the next 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 700 competitors will advance to the second round immediately. 50 more competitors will advance to the second round via the first unusual rules wildcard round on March 18.

There's one wish for everyone from Burunduk1: “Please, to make the round even more interesting for you, read the statements of ALL problems.”

Good luck and try to win!

Update: congratulations to all competitors with 1712 or higher score: you advance to the second round!

Update2: editorial is available: http://codeforces.com/blog/entry/4097

Update3: Several cheaters have been removed, the results now slightly differ. All participants with 1684 or higher score advance now to Round 2. Everyone else is invited now to the first wildcard round, the last chance to advance.

Announcement of VK Cup 2012 Round 1
  • Vote: I like it
  • +250
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +73 Vote: I do not like it

There’s also one wish from everyone to the Authors: "Please, Make the English Statment of the problems, good and correct!"

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

    I guess authors will not change statements 5 minute before the contest:)

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

      It was just a wish! :)

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

      +5 mins. Maybe they are changing? D:

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

Good luck ALL :)

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

No submit option for competitors out of contest? It kind of spoils the "rated round" thing if you cannot submit.

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

    I noticed that when I hit the register button, the front screen would still say that I was not registered, but when I went into the Friend Standings area, it displayed my name. (unofficial with the * by it)

    EDIT: Did anyone else see this?

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

WTF??? I can't submit even though I am a registered user!

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -27 Vote: I do not like it

WTF??? I can’t submit even though I am a registered user! quick repair this thing

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

Hey, I can’t submit for the contest VK Round 1 even though I’m unofficially registered. Are we just not allowed?

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

i'm sure i registered the contest as an unofficially participant, but i can't submit my solution!

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

so it will be unrated for out-of-contest participants?

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

    I'm sorry. Yes. It is just the result of wrong contest policy setup. It will not be such issue in the future. Sorry again.

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

I think we (unofficials) can submit now, but is this unrated then?

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

    it seems to be unrated. the official notice mentioned this.

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

I wish the system test to be fast !!! :D

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

Quickly-put comments about A,B and D Edit: And now C

It was a nice problem set, too bad we unofficials had that bug that made us unable to submit . I think it would have been a fun contest otherwise.

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

Anyone else got an O(n*k) solution to D that's timing out? (Slightly less than) 50,000,000 iterations isn't too much... I've tried it with C++ vectors and lists. Still too slow.

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

    my O(nk) (c++ too) passed in 390ms without any optimisations. Seems, your solution isn't O(nk) or has very big constant factor

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

      It is O(n*k), and I fixed it. First I reworked it to use just a regular array (no vectors no lists). That halved the times, but was still too slow.

      Here's the real problem. Originally I had an array like this: unsigned long long PS[50005][505];

      That one doesn't work. But this one does: unsigned long long PS[505][50005];

      The problem with the first set up is that my main loop was skipping around the memory a lot. That change alone reduced the running time on my machine by about two thirds.

      Lesson learned :)

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

        Why did you use long long? I had an Array[1..50015, 0..515] of LongInt in my solution, because I stored numbers of vertices on a specified distance from a specified vertex in this array, so considering that N <= 50000, there was no point in using 64-bit integers. Or did you store something else in this array?

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

          PS[k][i] = DP[k][i] + DP[k-2][i] +..., where DP[k][i] is the number of vertices whose distance from vertex 'i' is exactly 'k'. (Note that I'm only storing PS, not DP). By the way, I'm not using DFS. Just a loop.

          My solution is based on the following relation: DP[k][i] = Sum_{j is a neighbor of i} {DP[k-1][j] — DP[k-2][i] + DP[k-3][j]- DP[k-4][i] +...}

          Basically a principle of inclusion/exclusion solution.

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

    My careful O(nk) passed in 190 ms. O(nk)s differ :)

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

    My O(nk) solution in Pascal passed in 410 ms.

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

    A dfs for each node times out when the graph is dense.....

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

    My O(nk*log(n)) solution passed system tests)

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

It will be good to show the position of the submission in the queue near '?' sign during testing.

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

    +1

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

    and points that you will get if it'll pass

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

      maybe it would be better to see the place which you would take (in that context) if the solution passed. Because points don't tell much (at least for me)

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

Congratulations to RAVEman!! Results aren't official yet but as he won't be removed from the contest as he's obviously not a cheater I think we can consider him the winner of the first round ever of the VK Cup! Great job RAVEman!

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

Why can't I view the test data?

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

Sorry tourist, meret got the second place because he hacked me...

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

this round will be unrated？

ok...rating updated at last..

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

Problem C's name was very interesting for me. it reminded me "Avada Kedavra" which is the killing curse in "Harry Potter" :D

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

By the way, to rate an event that is not opened to everyone kind of diminishes the rating's value. I mean, the rating is designed to compare coders, how can it be just if part of the coders weren't given the chance to excel (or not) in some of the competitions, but others were?

In most tournaments the contestants either decide not to participate or get eliminated or miss registration, but the fault for not getting a spot in the match(es) is their own. In this case you are just saying "Well, some of you can enter, the others cannot." It will be rated for those who WE decide can enter.

The same goes for TopCoder during the TCO round(s), excluding top participants from the Qual round and under 18 participants from the TCO itself. Actually, I find CodeForces being more accurate and fair in that direction, making Qual rounds non-rated and doing parallel, rated rounds with the other rated tournament matches. I do understand that you had all good intentions to allow parallel participation of all coders, wishing to take part of the contest, however due to some problems it didn't turn out as intended.

Last, I do not ask for the official round to become unrated, neither the other one to become rated. Nor I'm criticizing the CF system or problems — I like them and I appreciate the time and effort you guys are putting into that. I'm just pointing out a problem with the rating systems (both CF and TC) that has been bothering me for some time.

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

    Also, it may be good to give ability to everyone to register either as rated or unrated. So in that case if someone thinks that current round may affect his rating in a not too fair way, then he can choose "unrated" option during registration.

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

      what is the point of this action? increasing a load on servers, which is very important for users who want to get honest results?

      if you don't want to change your rate you can always get in a "virtual contest" later. it even supports real-time results.

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

        In the case when someone is willing to participate in VK Cup Round 1 and pass to VK Cup Round 2, but he doesn't want to participate as rated.

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

          I don't see the point here. It seems to me that rating is important because it reflexes my performance. Hence, the more unrated rounds you participate in, the less significant your rating is.

          Just for fun, what will happen if your idea is applied? Well, I will try my best to become red, then choose "unrated" for all the following contests =)

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

    Both TC and CF's rating formulas are able to correctly update rating in contests that have rating distributions different than average. As they are based in expected position and all that stuff.

    I don't really think this is a problem. You could use roughly the same argument against certain time slots that are popular in some continents while it is 3:00 AM in other places. No competition is truly open to everyone.

    CF didn't rate the qualification round because of its structure that allowed tons of ties and it would have really caused fun rating outputs.

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

    Round was supposed to be rated for everyone, but technical mistake in round setup spoiled this

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

even i'am a official register for the round... why my login is access denied during the first hour of the round

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

Rules say that most rounds will be open for rated participation to out-of-championship participants, but can those participants who have already advanced to round 2 participate in Wild-card round 1 as rated?

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

    As I understand, Wildcard rounds will not be rated

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

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

→ Reply