VK Cup 2012 Round 3
By Burunduk1, 13 years ago, In English

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://mirror.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.

Announcement of VK Cup 2012 Round 3
  • Vote: I like it
  • +103
  • Vote: I do not like it

Comments Comments (60)
| Write comment?
»
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

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

good luck for everyone！

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

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 4   Vote: I like it -25 Vote: I do not like it

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

    English translation?

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

      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?

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

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

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

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

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

      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?

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

    You can ask me how to fail!

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

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

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

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

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

    Official and unofficial contestants will be in separate rooms.

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

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

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

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

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

    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"

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

    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.

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

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

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

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

    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.

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

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

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

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

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

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

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

Problem C — Hate!

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

When will be our ratings updated?

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

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

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

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.

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

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.

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

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

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

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

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

    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.

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

    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 .

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

    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.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 2   Vote: I like it -16 Vote: I do not like 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.

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

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

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

      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.

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

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

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

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

    :)

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

      I guess there should have the fourth group

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

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

        Do we have official responses to our questions now?

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

When should we expect the editorial?

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

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

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

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

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

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

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

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

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

https://mirror.codeforces.com/contest/164/submission/78511593

plz check what's wrong in code. plz help to find out logical error.

→ Reply