Ripatti's blog

Codeforces Round #150
By Ripatti, 11 years ago, translation, In English

Hi all!

That's the 150th (anniversary?) Codeforces Round. For the 1st and the 2nd divisions both.

Round is prepared by Ripatti , Gerald , Delinur .

Enjoy!

UPD. Points are standard: 500-1000-1500-2000-2500 for both divisions.

UPD2. Contest complete. Cheaters are deleted. Ratings are updated.

Div1 winners:
1. scottai1
2. vepifanov
3. rng_58
4. Egor
5. Komaki

Div2 winners:
1. mochavic
2. hanamaki
3. mfv
4. shef_2318
5. TangJie

Thank you for your participation. Come again.

Editorial will be tomorrow.

UPD3. Editorial. Sorry for delay.

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

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

I hope problems will be as good as contest number :)

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

What a short post! Great!!

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

    haha :D

    What the 157 symbols!

    So being shorter means being great?

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

      Take it easy please. I just said that it was not like the others. :)

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

Why is 150 a good number?

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

    There's no accounting for taste.

    But probably beause we still think of numbers decimally.

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

ill hope it will be good contest like last

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

I wanna pass a vector as a reference to a function. can anybody help me??? template code or helping links pls.

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

Will the problems be sorted by order of difficulty? What is the scoring system gonna be??

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

    I think not,as usually it is.

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

all you guys be cool like me !!

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

My contribution is positive. What did I do? o.O

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

Good luck & have fun !

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

Amazing anniversary :-ss I have never a problems like Div 1.A Amazing or bitwise

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

Seriously, why? Not enough servers? 'Shut down all the servers' button was clicked by an accident? Slow code? Strange Java behavior? 'The load was so high that we were not ready for it?'

It looks very strange and unnaturaly for me; CF rounds are not beta for a long time and there are still problems sometimes.

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

    sorry to say that but if the server isn't strong enough just limit a registration number : )

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

mnlfrnnds04 has 24 hacks so far, all of them on the same person. With 1 correct task he is third. Seems legit...

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

    He is very lucky that stay in chicky room, and he got crazy number of successful hacking attempt. Congratulation! =]]

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

      look at their profiles. same photos, same countries, a little bit alike nicknames. that's obvious...

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

        What is his room ??? anyone in his room please tell my some information abou this case please :D

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

        obvious cheater is obvious :d

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

    Yes. now they are 26. The both users are have equal avatar. "Nothing suspicious" :D. And the oth users are from Turkey. Again "Nothing suspicious" :d

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

    +28, hell yeah, How can he do that =)) Please teach me :D

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

      that's better to avoid doing like that:)

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

        Just kidding :D And what admin do next after this ????

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

          +44

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

            mnlfrnnds04 has 44 hack in his room :D and in my room overall was not 44 man

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

              watch

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

              How can we cheat for hacks? I don't get it... The roomates are determined randomly...

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

                it's just luck

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

                Maybe he has tried to do this a couple times and today he got "lucky".

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

                  I think he just wrote a solution that passes pretests only, then write some test cases that beat it.

                  After that, he modify the hacked solution to beat down the hack only and then invent another hack to beat down the solution again

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

                  You are GENIUS!!

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

                  Had found the same theory a little after my question, and I think you're right. But it will be detected very quickly if it is something like "if(input==hack1) then print(solutionhack1) else if (input==hack2) then print(solutionhack2) etc..." Or else, it can be too a good solution, but altered for permit hack like "if(input==hack1||input==hack2...) then print(42) else print(goodanswer)"

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

                  http://codeforces.com/submissions/hgrsm07 :D

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

                  The photo is same...

                  http://codeforces.com/profile/mnlfrnnds04 http://codeforces.com/profile/hgrsm07

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

      I can't be possible...

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

      people who are trying to explain this event, YOU'RE ALL GENIUS!

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

    He would be first even if his A and B won't pass system tests.

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

what kind of sorcery is this :) 44 hacks, same user, same country, same profile :)

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

PRETEST 4 WAS A TRICKY ONE FOR THE PROBLEM HYDRA............... ALMOST EVERYONE HAS A WRONG ON IT........

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

Could anyone explain me, what is the statement of the problem B? Let's assume two middle vertexes as S and T. I can't understand, could neighbours of vertex S be connected to vertex T. I thought, no. And, server problems...((

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

    tree with h+t+2 nodes

    I think no except you don't select the neighbour nodes for both S and T

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

Will this compitition be rated?The Net was error for too much time.

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

    But they increased the time to overcome that .. So I suppose it is alright

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

      I'm disagree.

      Imagine the following situation (it's from real contest): I opened one problem, solved it and then server gone away. I have to wait and can neither send my solution (and I lose some points), nor read the next problem (here I lose contest's time).

      Then imagine one (I know such persons too) who opens all problems in the beginning of contest. So, he have 5 additional minutes over me. Not fair, huh?

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

        You also had the opportunity to open all 5 problems. So it is fair to everyone.

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

        Well, I think it is reasonable precaution to open all tasks when contest starts

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

        My situation was better: I waited for five minutes to send problem, and than waited 5 more without any other opened problem. Than I got WA. Nice:)

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

        I'm just the first situation,and I solve the second problem but I can't submit at once,when I submit it,it's already 20 minutes later.

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

        Imagine if you want to ask a clarification (my case). Let's hope this doesn't keep happening in future rounds.

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

mnlfrnnds04 this person should be banned, he is first in div-2 illegally.

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

    of course with this one too hgrsm07 :D

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

      then I will survive unluckiness of 13 in standing :p

      Edit: as a result of omitting the cheater person, now I am ranked 12th, and consequently no person is ranked 13th! результаты

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

        And I'm 14th :) (Isn't it 13rd?)

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

    Of course, it's not fair with the other contestants.

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

      MDantas it looks that your solutions are identical to the Manoel's. And also very similar to the rafaelclp's.

      4 solutions very similar from 3 guys doesn't seems coincidence.

      See for example: 2572280 from SusanBoyle and 2572712 from Manoel.

      Not fair, indeed.

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

congratulations mnlfrnnds04!! The successful of a lot of challenges is the very great achievement!!!

...Oops...? Something seems to be wrong... (o_O)

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

The expected score for this match was 2158. :D

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

in Problem E, In pretest, My program prints "NO" in test case 1, but my program prints right answer in custom test. Please check my program..

-------------------------------- Sorry, my program was wrong.

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

I got this verdict in problem D(case 21) — "wrong output format Unexpected end of file — int32 expected". Does this mean I'm giving too much out-put? Submission link

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

    No, it means exactly the reverse — you gave checker not enough output — it tries to read int32, but gets EOF.

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

    It mean that you miss one (or more) integer

    UPD: I was too late(

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

can tell how made problem B???

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

    Note that there are not a lot of undoubtly lucky number upto 10^9 . So generate all of them

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

    I did a backtracking solution. You try all the pairs of (x,y), after that you produce all the possible numbers with a backtracking. This gives approximately O( 10^2*(2^10-2) ).

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

Div1 for first time .. so happy :D

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

Can anyone tell me why this brute force solution is able to pass Problem A (Div 1)? Solution I am not able to prove its worst case complexity. Perhaps, it is because of the pigeonhole principle. Is it possible that the tests were weak?

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

    Your code is correct and runs in O(N*20) for the worst case. When inner loop breaks with (temp==cur[j]) condition, it means that, a[j] and a[i] has some bit b set in their binary representation, but none of the a[j+1],....,a[i-1] has this bit set. If we contribute (i-j) to b(or to one of the bits which has above property), we see that for each 0<=bit<=20 we will do at most O(N) operations.Therefore complexity is O(N*20).

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

Was getting a TLE on Test 47 for problem B, and after the contest changing the loop from 0 -> N — 1 to N — 1 -> 0 reduced the time from hitting the TL on 2000ms to 281ms!

I still can't see any sense in making the TL that strict on the problem.

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

hi, i'm confused that why the java function BigInteger.isProbablePrime always lead to Runtime Error？ It's right in some OJ, but always RE in others like CF. Can you explain it? Thank you!

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

    It has been discussed in Russian somewhere. The problem occurs because of security policies: BigInteger.isProbablePrime() uses SecureRandom which could be prohibited

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

When we can have the tutorial??

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

The post said that day (contest day) "Editorial will be tomorrow." actually it didn't happened. But we can't say the are saying lies. because today it says "Editorial will be tomorrow.".. so logically they can never post a editorial :D but we can hope they will. (just joking) i hope this "tomorrow" will have an upper bound. :D

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

    It seems editorial is ready, but it still isn't available in english, but you can see it in russian.

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

So how do u solve The Brand New Function

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

What's the idea of div2_C?

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

It would be great if we have a tutorial soon :) :). waiting for the tutorial :) :) :) thanks.

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

Why my code get TLE on DIV2_D?2602812,I need your help!

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

What a coincidence. All the codes of MDantas and Manoel look identical.

→ Reply