VK Cup 2012 Round 2
By Burunduk1, 12 years ago, translation, In English

Hello everyone!

It’s time for the second 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 175 competitors will advance to the second round immediately. 25 more competitors will advance to the second round via the second unusual rules wildcard round on March 28. This round will consist of only one problem with inexact solution.

Please, to make the round even more interesting for you, read the statements of ALL problems.

Good luck and try to win!

Announcement of VK Cup 2012 Round 2
  • Vote: I like it
  • +163
  • Vote: I do not like it

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

No english version?

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

Superfast systests, thumbs up :)

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

The contest is over but I still can't view other's code...why ? Need I just wait ?

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

edit: posted in the corresponding thread my apologies the titles look extremely similar :)

Somebody could explain me how this solution pass under the 2 seconds time limit, me and another five people got unsuccessful hacks in my room (my guess is because of the codeforces server speed): http://www.codeforces.com/contest/169/submission/1412269

How can I avoid this kind of situation in the future? Thanks

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

    This isn't even a problem from this contest :/

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

    for 10^9 iterations only 10 ms. Looks like compiler is optimizing the loop into a single statement. Modern days compiler are so smart.

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

I can't decide the complexity of my code: ---> here Is it O(n^2) or O(n^3) ?

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

    O(n^3): You have O(n^2) states and O(n) moves from each state.

    Also, you can try launch your solution with n = 1000 and n = 2000 and measure running time. Is t2 / t1 = 8 -> O(n^3)
    t2 / t1 = 4 -> O(n^2)

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

    It's O(n^3).

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

when to update the rating?

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

In the Div.2 problem B, this is a very ambiguous statement : "You are allowed to use not all elements from s." I thought we could never use all the elements of s and this caused my solution to fail.

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

    Hm... You could never use all elements. In 2nd test from statement we never uses element.

    Input:
987
1234567

    Output: 987 ~~~~~

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

      For example: Input: 1111 9999 The answer is 9999 and in this case we use all the elements of s. In my code initially, I was getting the answer 9991 without using all elements of s.

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

    I think the difference between "allowed to use not all" and "not allowed to use all" is pretty clear.

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

    This is not ambiguous at all.

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

Where can I fill my address if I get a T-shirt?

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

There are many coders failed in problem B Div1 because they didn't make enough iterations in the binary search.

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

    But I made too many iterations and got TL :)

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

      Then, you should binary search for the correct value. :)

      Edit: I think you should ternary search. :)

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

    Yes, I made 50 while 80 was enough. There should be an option to change 1 byte of the solution after the contest ;)

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

W8ing 4 d editorial

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

tourist is going to be the first target at Codeforces!

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

2 floating-point problem, not so nice. I failed problem C because I didn't set precision for cout. Beside that, the problems are nice.

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

Can someone explain to me what the checker output means?

wrong answer Jury has better answer: ja=99999/999990001, pa=1/10000
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It's rational number.

    ja = Jury answer, pa = Participant answer

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

      Thanks for the reply. But isn't my answer the same with the jury answer?

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

        Close, but no :)

        999990001%99999 = 1 999990001/99999 = 10000

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

          I'm not sure I'm following you. I've just computed this with my calculator:

          99999/999990001 = 0.0001 1/10000 = 0.0001

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

            Your calculator is not accurate enough.

            Try compare 999990001/99999 and 10000/1 (if a=b then 1/a=1/b)

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

            999990001 * 0.0001 = 99999.0001 != 99999. So, 99999/999990001 != 0.0001

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

    ja = jury's answer, pa = participant's answer

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

Could someone tell me why 1417148 got WA on test 7 but 1417142 got Accepted? The only difference is in the function "verify", 1417142 which got Accepted HAD a line fprintf(stderr,"I love Mike Mirzayanov."); ,and WA one didn't. Really fun :)

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

Any Tutorials (In English)?? and how do we come to know in whose blog tutorial is posted after each contest??

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

For [http://codeforces.com/contest/169/problem/B](Problem B) , "You are allowed to use not all elements from s." ,it simply implies that we are not allowed to use all elements from s.But the my solution that is accepted ,uses the fact that all elements can be used.I could not pass the pretests due to this ambiguity.Can anybody explain?????

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

    There is a difference between phrases:

    "You are allowed to use not all elements from S"

    and

    "You are not allowed to use all elements from S"

    If you are allowed to do something, it does not mean that you are not allowed to do the opposite.

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

      So if this was actually allowed, then what did the sentence actually want to convey(what was the use of adding that sentence) ,simply nothing... ,I hope this is not a Grammar competition

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

        It's actually a reminding sentence. Problem-setter doesn't want to repeat answering clarification like "am I allow to ..." (yes, you do — in problem statement). Also, it may be a misleading corner case so problem-setter stresses on it.

        Edit: it's not a grammer competition, of course. You will see this kind of sentence often, and in most cases, the purpose of problem-setter is good (i.e. try to make thing clearer, not try to be evil and cheat you :P)

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

          I agree with you,but I lost a hell lot of rating due to this.. :(

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

      And strangely enough, there is no difference between:

      “It is not compulsory to use all elements from S”

      and

      “You are allowed to use *not* all elements from S”

      still I guess a better statement could have been used.

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

    I also made the same mistake and when I tried to convey the ambiguity above, I got a lot of negatives for my comment. I think the statement was very complex to understand in the contest environment and could be explained in a better way or with a simple test case.

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

      Did you consider clarification from author during contest ? They are always there. Click on Ask, on Problems page.

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

It took me much time to find out that the c++ compiler on the grading server does not support %Lf (to output long double). Maybe there could be added a warning if you submit code containing %Lf (as with %lld).

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

Any tutorials coming?

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

When will the T-shirts be sent? =D

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

    The announcement section says, "All Round 3 contestants will receive VK Cup T-Shirts". So I think you should participate ( or at least register (?) ) in round 3 to receive T-shirts. Admins, please confirm !

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

I found that I forgot to register，when submit

→ Reply