HolkinPV's blog

Codeforces Round #130 (Div. 2)
By HolkinPV, 12 years ago, translation, In English

Welcome, friends)

We are glad to introduce you regular Codeforces round #130 for Div.2 participants. Everyone can traditionally participate in it. There were some problems with registration of Div.1 participants, but now everything is alright)

Problems are prepared by command of authors: Pavel Kholkin (HolkinPV), Nikolay Kuznetsov (NALP) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces system and Mary Belova (Delinur) for translating problems. Also thanks to Alexander Kouprin (Alex_KPR) and Pavel Kunyavskiy (PavelKunyavskiy) for their help.

And again score distribution will be dynamic) More information you can find here.

Note that all problems will be given in random order.

We wish you good luck, successful hacks and high rating!

UPD: the contest is over, no matter what, we hope you enjoyed the competition

UPD2: The authors apologize for the situation with the problem E. The problem has affected a small number of participants from div2 (22 participants) and the solution of original version of the problem doesn’t differ a lot (in most solutions is sufficient to remove a couple of lines, solutions become more simple). Therefore, it was adopted the following decision:

  • for all 22 participants,who has problems with problem E and will have decrease of rating, the round is unrated.
  • for everybody else the round is rated

UPD3: after recalculation it was found that there are 20 such participants, not 22

UPD4: unsuccessful hacks, which answers differed from the correct whitespaces, are decided to ignore

UPD5: tutorial can be found here

  • Vote: I like it
  • +102
  • Vote: I do not like it

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

Will it be dynamic scoring.?? If not what is the score distribution??

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

Are you going to make all contests in future with dynamic score system? Or you just making experiments?

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

    Is there anything bad with it?!

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

      Yeah, I think this system need a lot of improvement, and now it looks very poor and unfair. Excuse me, developers, but it's my own opinion.

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

      My feeling is that in dynamic scoring system there is not so many points distributed (I have no statistic for this, just a feeling)... And so, the coders' rating is decreasing for most of them :-(

      I think it would be better if it's smoother (as discussed in comments on dynamic scoring blog).

      On the other hand I like these dynamic scoring rounds, because you do not know the final score until the very end of the contest (system tests).

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

How to judge Problem A? I've found a solution which generate "WE ARE THE CHAMPIONS MY FRIEND " for the second example.

There are two spaces between ARE and THE, but it's still right. Is this a mistake? Or some other reason?

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

    As per as I have found. Cf checks answers by tokenizing them. So whitespaces doesn't matter unless it is explicity mentioned as in some questions.

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

      Ah... thanks... Kind of unhappy :( I spent 20 minutes and hacked nobody...

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

        We have removed all such unsuccessful hacks.

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

          Instead of just removing the unsuccessful hacks, people with the incorrect answer (differing in number and position of spaces) should have failed system test. As I mentioned earlier, many of the contestants may have put in additional time to get the right answer.

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

Why my hack was wrong?

My attempt was like: WUBWUB...A, the expected answer is "A", the other guy solution prints " A" :/

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

    Just like what i said above... That's very intetesting... i think the judge regard space as nothing...

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

    You just got trolled by codeforces, they ignore white spaces.

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

    i think the judger ignores all blanks, but i don't know if it is right

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

      Then the problem statement should be: "Separate the words with one or more space."

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

    I also lost points for unsuccessful hacks for similar cases. Also, I took much longer time to code and test for such cases during my submission. This way of evaluation is really unfair.

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

    We have removed all such unsuccessful hacks.

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

Can anybody give me hint for problem B ? My code fail in preetest 9 :(

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

    My solution too.

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

    The state you use in your DP is described by the variable "sekarang", shouldn't the state also contain the last pile values? (int memo[100][52][52][52] instead of int memo[100] ...)

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

This contest should be unrated. Before you change the statement of problem E it's impossible to AC

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

    I partly agree with you, after the change of the statement , there was not enough time to solve it.

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

    There exists a solution for both versions, which differs by only one line. But I also think the round should be unrated.

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

      But it'd be unfair for those, who have spent almost two weeks in Div2 after the previous round and now have real chances to return back to Div1.

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

      You're right, to solve the previous problem you just need to do a subtract operation. It's not so good to change statement in the last few minutes.

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

    Another reason to make it unrated is that CF added 10 minutes to coding phase. It's true that system failed for ten minutes but it was 10 minutes of time to code and think for some others and in my opinion it's unfair. Let's wait and watch what they will do! :)

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

Can I have the time that the editorial be posted?

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

    I solved it by DFS order and functionnal segment tree. First we get the DFS order in O(N) time Then we get the k-parent in O(logN) per query(by the same method like LCA) Now we should solve a interval question : how many Di in L..R It can be solved by functional segment tree easily

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

How can some competitors solve problem E at their first attempt before the announcement?

Way to solve problem E:

Solve the wrong version of problem E and got WA on pretest 8.
Notice that the contest extended for 10 minutes.
Notice the problem statement change and fix it quickly and submit it.

I think this is a quick response to announcement contest, nice style :)

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

    Hello, can you tell me how to solve problem E?

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

    What is the wrong way to understand problem E? I didn't find the statement ambiguous and solved it.

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

      At first statement suggested that for test

      4
0 1 2 2
1
4 2

      answer is 0 (as 4 and 3 are 1-brothers and not 2-brothers)

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

Why Compilation Error is counted as -50?

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

Please help me out ! I'm new to codeforces enviroment. My solution id is 1931589 and want to know the full test case for which I got runtime error or bug in my solution ?

Thanks

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

    I believe you can't view the full test case because it's too large, you can only see part of it.

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

I am wondering, if on this submission: http://codeforces.com/contest/208/submission/1925102 I saw the error, it should give runtime error, is there a chance that I try to hack it and it should result in runtime error and it does not? (I dont know how exactly runtime errors are thrown on windows..)

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

Excuse me. . Can you update this blog so we can know this round will be rated or not ?

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

These problem was well designed.

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

Hi guys!

After reading the description of problem B, I was not quite sure about one part of the statement. After shifting one pile x onto another one (x-1 or x-3), is pile x effectively removed? in other words, are all piles renumbered after each move? still not clear to me after reading the statement several times.

Either way, I dont understand pretest 5: 7S 7S 4S 8H 4H (its answer is supposed to be "NO")

Assuming piles are removed: 7S 7S 4S 8H 4H => 7S 4S 8H 4H => 4S 8H 4H => 4S 4H => 4H.

Assuming piles are not removed: 7S 7S 4S 8H 4H => 7S 4S 00 8H 4H => 4S 00 00 8H 4H => 4S 00 00 4H 00 => 4H 00 00 00 00

So... I just dont get what I'm doing wrong here, in my opinion the answer should be "YES". Could someone enlighten me? Thanks!! :]

PS: Great contest, was fun... Thanks for you work guys!!

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

    x is always last. So, it's removed, but nothing renumbered

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

    Wow. I understand it now, this statement mislead me big-time: "During one move, a player can take the whole pile with the maximum number x (that is the rightmost of remaining) and ..."

    It totally sounded to me as if the maximum number of the pile to be put onto another one is x (of course, rightmost one)... and assumed every pile starting with pile 2 can be put on ones before. Not sure if this was intended challenge.

    A more obvious statement wld have been: The pile x, whereas x is the maximum possible value and therefore represents the rightmost pile, can then be put on...

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

      Firstly, I had the same idea as you, but then I've reread the statement, it goes "Let's number the piles from left to right, from 1 to x", further explaining what one can do with pile x.

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

        Yes, you are certainly right. The statement is definitely correct. It could just be written in a way the intent is more obvious. ;)

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

Hi, When the editorial will be available?

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

2:20 AM here and still wait for ratting

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

Sorry for the off — topic question, but I couldn't find any information about virtual participation. How can I join for a virtual competition, and will it be rated or less?

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

Is there any solutions about this contest?

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

Why Codeforces English Version is not so updated like Russian version? In Russian version, problem-set analysis is already given, but in English version its not up yet.

google translate is making me sick..

:(

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

    It's only the problemsetter's blame. When you're preparing contest (It takes at least several days!) you can easily find 30 minutes to write and translate analysis to English. When I was author, for me it seemed something necessary and obvious, and I don't understand, why such delays happen.

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

hacked by hackers

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

I am new on codeforces.com and how add friend??

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

Codeforces Round №**130** contest duration was also 130 (02h 10m=2*60+10=130m) :)

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

There is something wrong about problem E Blood Cousins.
Look this .
If input is:
3
2 0 2
1
1 1
Output should be 1,but this code will output 0.

→ Reply