VK Cup 2015: online mirror and final thanks
By Zlobober, 9 years ago, translation, In English

The registrations before 00:00 have been deleted, because the form didn't support teams. Please, register again if your registration has been affected.

VK Cup 2015 Final Round has ended two days ago. It's very likely that you've seen our previous posts. The last event to happen is online mirror of the final round. It will be held on Thursday, July 30th, at 19:00 Moscow time. Individual contestants as well as teams consisting of two people may participate in this round. Round duration is three hours, problems will be shuffled in comparison with to the original order. Both division participants may take part, but we want to warn 2nd division contestants that problemset may be hard for them. This round is a rated Codeforces round.

Finally, we want to thank all people that made this Championship. Following VK developers, Codeforces team members and the other people suggested their help to us while creating and preparing problems: PavelKunyavskiy, burunduk3, Dmitry_Egorov, Kurpilyansky, dark_ai, MikeMirzayanov, Zlobober, MaximShipko, kuviman, Nickolas, Errichto, sankear и malcolm. We want to thank the people that helped us very much by testing our rounds and giving great advices: winger и AlexFetisov. Also we want to say thank you to all VK members that helped us to run the onsite Finals: burunduk3, Burunduk2, KOTEHOK and many others. Thank to all of them!

Good luck and have fun on our Online Mirror!

UPD: Note that during the round the team is allowed to use only one computer. This means that you may code/use console/succeed in solving problems in any other manner by using only one computer at time. The only thing that is allowed from two computers is reading the statements.

UPD2: Since this is a team contest, specially for your convenience we publish the encryped zip-archive with pdf-statements of problems: vkcup2015-mirror-statements.zip. When round starts, we'll publish a password for it.

UPD3: The round will use the dynamic scoring with 250 points step.

UPD4: Due to technical reasons the round starts at 19:20 Moscow time.

UPD5: Password for statements archive: vkcup4ever. Good luck!

UPD6: Online mirror has ended! Congratulations to winners:

  1. rng_58
  2. Zenith: I_love_Hoang_Yen, ngfam_kongu
  3. OrOrZZZ!: zld3794955, KFDong
  4. Petr team: Petr, ilyakor
  5. jcvb_matthew99: matthew99, jcvb

Also, my personal respects for a team "Petr team: Petr, ilyakor" for only solution for a problem Е in this mirror, user rng_58 and a team "Excited: YuukaKazami, jqdai0815" for two correct solutions for problem С.

Congratulations to a user rng_58 that showed that a single contestant can compete with teams consisting of two people!

Rating will be updated shortly.

UPD7: Editorial!

Announcement of VK Cup 2015 - Finals
  • Vote: I like it
  • +195
  • Vote: I do not like it

Comments Comments (82)
| Write comment?
»
9 years ago, # |
  Vote: I like it +22 Vote: I do not like it

How it's going to be rated for teams?

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

What is the rule for teamed participants?

UPD:Mike's comment on this topic

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

Why I can't register team?

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

I'd really like to take part in this contest but I'm afraid of this problems. Is my fear justified shuld I pass this one?

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

    don't think too much about rating . Pleasure of participating with high rated coder is much higher than fear of losing rating :)

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

So not to cast stones or anything, but I was wondering why you guys consider rating team members individually a good idea. It feels like they're completely different skill sets. I remember TopCoder had a special SRM that lasted 4 hours and had super hard problems and they didn't rate it. I don't think they ever rated something else than a SRM-style contest. Codeforces ratings were already suffering from the fact that you can choose not to participate after reading the problems. This way it's easy for some people to only choose favorable problem sets. I know that it's their problem and all that, but it still undeniably affects rating relevance.

To me it feels that this move wouldn't do any favors to rating relevance. Again, you guys know better than me what you're doing and what you want the rating to reflect. I just wanted to know what your official reasoning is :).

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

    Well, rating doesn't have any real relevance to begin with. Long-term, it's a good measure of one's skill, but that's it.

    The thing with not being rated if you don't submit doesn't bother me much. If you don't try, your loss. But I'm thinking of skipping out on this round due to teams and individuals being rated together. A team simply has a huge advantage in time that the combined rating doesn't reflect properly. In a round for teams only/primarily, this isn't a problem, but I can't help but feel I'm at a big disadvantage to some people. I suppose I'll decide based on how teamy the registrants' list gets.

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

      As far as I see, we didn't have big rated rounds with both teams and individual registrants. So, your words about:

      A team simply has a huge advantage in time that the combined rating doesn't reflect properly.

      aren't confirmed with any previous experience. For us this round is a good possibility to see how rating works in such combined conditions.

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

        We do have a way to compete individually against teams, I've done so in many Gym trainings. It may not be the same thing, but it's something I can base my view on.

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

          The type of problemset is also important. When the problems require more thinking, the difference between teams and individuals are bigger.

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

            Xellos wrote his first comment when there was nothing about 1 PC per team rule. During VK Cup online rounds participants were allowed to use 2 PC, and in my opinion (and from my experience) it actually gives huge advantage. In this case "more coding" problemset is even worse comparing to "more thinking" one.

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

you said that problems will be hard can you compare the level, I mean for example the easiest problem will be harder that E div 2 ?
also it will be as usual if I didn't submit any problem score will not change ?

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

    Yes, if you not submit any problem, score won't change.

    The easiest problem here is like Div2 D, others are much harder.

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

      Just curious, what is "much" harder? Is it Div1 D and harder?

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

        Participate and you'll see ;)

        Anyway, the final standings on the on-site are available for you, so you can make an estimation regarding the difficulty level of problemset.

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

MaximShipko Did anyone see this black man before ?

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

How many problems will be ? How about scoring ?

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

Maybe my question is stupid, but I cannot find the rules for teams anywhere: is it allowed to use more that one computer (i.e. write code in parallel)? I don't see it forbidden anywhere, but looking at the photos from onsite, there was only one computer per team...

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

    Can you see any relevant way to control coding on more-than-one computer during online competition ? I think in this case it's free to be free :)

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

      There are no relevant ways to prevent cheating in general, like 10 people participating from single account (some people do it, e.g. kutengine and black_horse2014), using multiple accounts, OCR'ing solutions for hacking, etc. Still, decent participants follow rules.

      So, if organizers say that one team should use one computer (reasonable assumption, because these were the rules during the onsite), I will comply this rule.

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

    Teams should use one computer. It will be a broadcast about it.

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

      That's an extremely important information, which should be very well emphasized before start, broadcast at the beginning is definitely not sufficient. I bet vast majority of teams registered think that it will be possible to participate using 2 computers (being in completely different places, e.g. their own houses) and what do you think all those teams should do when they will see such a broadcast? They can't simply just use one computer if members are not in the same place.

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

        Considering this and the fact that the onsite isn't at the same time as the online, I get the feeling that this contest is just begging people to cheat. I think I'll skip this one.

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

          What does the fact you mentioned imply? I do believe that none of the finalists have spoiled problems to somebody participating in the mirror today because we explicitly asked them not to do that (and because I personally know more than a half of finalists, I really believe them). I don't see any other way how to use the fact that onsite isn't at the same time with the mirror.

          Nonetheless, it's up to you whether to participate or not.

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

          Come on, it's not like people who get to onsite rounds tend to help others cheat. I'm not exactly happy about teams+individuals (see my comment above), but screw it, I'm going to take it as a challenge.

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

            but screw it, I'm going to take it as a challenge.

            Eh, sure, I like that logic. The only thing I have to lose is rating.

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

        What's wrong with participating being in completely different places? They can still use Hangouts/Skype and coordinate who works with computer at any moment. Our OpenCup team (www.opencup.ru, it is mostly-russian ACM-like competition without age restrictions) does this all the time, and we never had any problems with coordinating, even with 3 people; with 2-people teams, it should be even easier.

        (but yes, I agree that this should be announced more prominently; e.g. add it to this "You can register on the coming round individually or in 2-members team. It will be rated for all individuals and teams" green message displayed on top of the page)

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

to take part,or not to take part?!!that is the question...

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

I love that my presence in this contest but my rating :((

goodbye div1 and expert and Specialist and Pupil and Hello newbie for along time :((

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

Why am I not able to register? :/

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

This one has got to have the most bad-ass problemset this year!!! Am I crazy for participating?

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

Interesting, from registered list I can see that a lot of people preferred to participate individually

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

Auto comment: topic has been updated by Zlobober (previous revision, new revision, compare).

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

Can I be reading my code trying to find bugs(as if it was printed) while my teammate is coding a different problem?

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

I missed the registration because codeforces was temporarily unavailable :/

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

Very very nice problems. Big congrats ! Looking forward for the editorial.

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

Isn't the complexity of F n log n?

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

Very difficult contest (even the easiest one is already at Div1-A level, and the second easiest is at Div1-C level), but nice problemset nevertheless.

Anyway, how to solve problem A and G?

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

    you can solve A with suffix array
    first of all prove that this greedy approach is correct: select the two strings which have most lcp and match them
    i think every matching that isnt max can be made into a max matching with 2-switches which the value of the matching increases everytime i cant really explain it really good just prove this i think it can be proved
    anyway after that we know that maximum lcp is between adjacent elements in suffix array so just get a set and a linked list and do stuff :D

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

      it can also be solved using trie, insert all strings(of both kinds) into the trie

      then do dfs to trie when you are in a node and you already have visited all its children then if you find at least one string from each kind inside subtree of that node then match them

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

        Well... now im depressed because i implemented my first suffix array and didn't think about the easier way :((

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

    A — make trie of all strings from input. Then dfs and matching strings from the subtrees of vertices before leaving vertex.#em8kM5

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

I just saw this lmao

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

Can someone tell me what is the original problems order in the official contest?

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

    I'll post it with an editorial in a few minutes, but you may try to figure it out by yourself =)

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

    I think C — F — E — D — G — A — B.

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

    I guess that G from mirror is E from onsite

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

Last hour I was thinking of B, had a very very simple greedy solution but cannot prove it's correct and not writing a byte for it (as so few ppl solving it, I was thinking well the solution should be very complicated), and in last 10 minutes, I thought that the time was running out and I just write it (in 2 or 3 minutes) and it passes systest lolz

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

Most solutions for G failed as expected (including my own)

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

Now me and jerry can say we solved a problem that YuukaKazami, jqdai0815 and scott_wu didn't solve. We're at the IOI right now and since we're obviously not good enough to beat them here, this is pretty much the closest thing to an IOI victory as we could have hoped for :D (and also nomnomnom delicious, delicious rating points)

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

Test cases were too weak for the last question!!

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

    Be more specific, what wrong solution passes them?

    EDIT: If you mean the pretests, that's working as intended.

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

OMG we are #2, I can not believe that I am not dreaming.. Now my life is complete. Thank you so much ngfam_kongu for coming up with solutions for most problems (I am just a coding monkey).

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

This "Convex Hull" passed the first 20 test cases :)

It is in my solution to G.

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

I failed G, because of I used int in cross product. I'm bored this stuff :(

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

How to deal with the range merging in D ?

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

    For operation 1 and 3 let's use a standard dsu data structure. In order to handle unions in range operations, let's keep a data structure that stores intervals. When one interval [L,R] is added, remove all intervals that intersects it, i.e intervals [L1,R1],[L2,R2],...,[Lx,Rx] such that L<=Ri and R>=Li. This intervals are going to be merged into one, so in the dsu data structure, we have to join the vertices that are in those interval: join(L1,L2),...,join(Lx-1,Lx). Each interval is added and removed once, so the number of join operations in linear;

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

You have thanked Errichto for his help in preparing the problemset . So shouldn't he have been restricted from participating in the contest ?

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

    He gave us a great help while preparing an on-line round 2, not the Final round. So, there was nothing preventing him from participation in this round.

    → Reply