KADR's blog

Codeforces Round #153
By KADR, 12 years ago, translation, In English

Hello everyone!

Codeforces Round #153 will take place on Thursday, December 6th at 19:30 MSK. This is my third Codeforces round and I hope there will be more.

I'd like to thank Shtrix, Seyaua, sdya and Gerald for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I hope you will like the problems.

Good luck and have fun!

UPD: Complete version of English editorial is now available.

Congratulations to the winners!

Division 1:

  1. Egor
  2. tourist
  3. rng_58
  4. kelvin
  5. Burunduk1

Division 2:

  1. inker
  2. WhoTheHellIsMe
  3. memo1288
  • Vote: I like it
  • +173
  • Vote: I do not like it

Comments Comments (92)
| Write comment?
»
12 years ago, # |
  Vote: I like it -45 Vote: I do not like it

All that red color suggest a hard contest :)

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

AT LAST !!

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

I have to go to school on Dec.7 Maybe i can't do this.

T T

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

yeees!Can you make more contests,please?It's boring when there's nothing on codeforces...:)

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

Are the scores of the problems decided? edit: Sorry, I was not asking for the scores of the problems, but if they will be static or dynamic :)

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

I think contest had better be arranged in Friday or Saturday，in that case more people can compete in contest.

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

    No it wouldn't be better because we would had to wait more. Everyone is getting bored from waiting.

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

Let's hope the server will stable during competition

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

    Let's pray for the welfare of the server. 42. Amen.

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

Seyaua, sdya are the same person ! :D ****

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

I think it has been long since last competition. Thanks for all the contests and their makers, I really enjoy myself in the contests!

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

Good Luck Everybody!

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

Good luck everyone!! Have fun!! :D:D

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

Was I the only man who had "error 502" now?

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

There is one thing that I will never forget about this contest

There's only one thing Petya likes more than numbers: playing with little Masha.

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

Little Petya likes "a lot of things" a lot :D

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

    Sometimes you get a mistake, the author is the same :D Sorry for my bad english :p

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

I solve problem B of Div.1

then lock my answer

and go hack two contestant with same Test Case

but unfortunately when i checked my hack TC too my code , I saw my solve give WA too :|

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

What was the challenge case for Div 1 Problem B? No one did many challenges in my room, so my solution could be wrong :( .

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

    2 3

    2 1

    2 1

    Answer: NO

    3 3

    2 3 1

    3 1 2

    Answer: YES

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

      Now that someone tells me, I'm scared of testing my code on it...

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

      My code managed to pass those tests. Do you mind sharing what test you used to hack me?

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

    Something like

    4 7

    2 1 4 3

    2 1 4 3

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

    1 1 1 1

    Answer NO :)

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

    I think if there was no challenges, it would be a lot of WA. This task checks contestant's attention.

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

Very slow system testing :(

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

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

Are the solutions being checked manually?

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

    Seems that they put too many test cases in Little Xor.

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

Sooooo slow system testing :(

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

The problems are harder and harder?T T need to work hard^ ^

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

    Sorry to say but it's easier than the last contest :)

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

Unlike Codeforces Round #152, this contest has a very low speed system testing... :(

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

Everybody seems to get WA in test case 12 in Div 2 -problem B. I wonder what that test case is ?

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

    I guess a case with n<3.

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

      I think many people think that "-1"'s case is only on n <= 2 and all array fill whit the same number. if N = 3 and array is {2, 1, 2} we can't do any swap.

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

    You can see this test case after the contest.

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

System testing has already lasted 20 minutes, but checked solutions of first 15 minutes of contest, that's amazing speed:)

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

why you need that too many test cases !!! :o

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

very slow test system(((

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

Seems strange, but I think Problem B was harder than Problem C. Problem C was quite standard, and non-standard problems cause much more trouble for the competitors:)

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

    It is so bad of me that I even did not check the tricky case that I generated for Div 2 B.

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

Thank you for really nice problems and amazing contest :)

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

Here is my solution to problem B div 1: http://codeforces.net/contest/251/submission/2710934 The veredict was: "Runtime error on test 1". But I tested the same test in my computer with the same code and it worked fine. Has anyone had this problem?

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

For Problem B ,Div 2 , an O(n^3) solution is also passing [code]

I noticed through the test case that it is actually never going O(n^3) when all elements of the array are not the same and when n is large . But I can not understand why this happens .Can anyone explain please

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

    The complexity of this solution is O(N).

    Suppose N > 3. Then it's enough to check only 3 different pairs of distinct integers. One of them will be the solution we are looking for. The reason is that these 3 pairs lead to 3 different arrays, but there are only 2 possible sorted arrays, so one of these 3 arrays will be unsorted.

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

.. . How to solve Problem E. ? ... QAQ

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

    I'll post the complete editorial in a few days. Now I can give you a hint.

    Suppose there exists a node of degree 3. Let's take any such node and call it a root. Then we can reduce our problem to the following one: given a non-root node v we need to calculate the number of ways to place the sub-tree of node v on a rectangle 2xK for some K with the restriction that v is placed to the upper-left corner of this rectangle. Note that the value of K can be determined uniquely from the size of sub-tree. This problem can be solved with DP in linear time.

    The reduction to the described problem is also non-trivial, but at least it's easier than the whole problem.

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

      。。。THX alot !...

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

      editorial in English too, I hope? Google Translate doesn't work well sometimes.

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

How to solve problem D div 1 ?

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

Can anyone show me the logic in choosing 0 (numbers that divide lcm(2..k)) to be the mediate value in problem C div 1?

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

    In case you misunderstood my words (I assume that by seeing those down votes), this is merely a question :)

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

Anyone can tell me how to solve C div 1 :( Just a hint, plz :D

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

    The essential trick was that if your current integer is divisible by all numbers from 2 to k, then the only thing you can do is to decrease this integer by one. Therefore, you can use dynamic programming to count how much time you need to reduce your integer by LCM. For instance, suppose a=80, b=3, k=3. Then LCM(2,3)=6. So you count separately the time you need to get from 80 to 78, then from 78 to 72, the from 72 to 66, ..., from 12 to 6, and finally from 6 to 3. It's easy to notice that all of those in the middle are equal.

    P.S. That's a shame that I didn't see this trick during the contest, but I was thinking of some DP with LCM...

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

      Then LCM(2,3)=6

      2 what ????

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

        I don't get your question. LCM(2..k)=LCM(2,3)=6.

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

          Sorry, I already understand your answer :D Okay :D thanks for your hint :)

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

Fail (( My solution in D(div2) was correct ... I just forgot to clear my array ...

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

Editorial is published in Russian here @ http://codeforces.net/blog/entry/6054

I wonder if it is possible for someone to please kindly translate that into English for me?

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

Where can i see the editorial?

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

Are there any editorial?

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

    only published in Russian, I'm afraid.

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

      I'll publish the complete editorial on both languages soon. Currently I'm out of country and don't have enough time for editorial. Sorry for the delay.

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

I can't understand the Russian tutorial of Div.1 E. >_< I hope the English tutorial will be published soon. :)

→ Reply