gojira's blog

Codeforces Round #196
By gojira, 11 years ago, translation, In English

Hello everyone!

Codeforces Round #196 will begin in several hours (August 16, 20:00MSK).

You will mostly have to deal with Manao's problems, which this time range from watching movies and taking quizzes to treebuilding and battling evil undead.

I'd like to thank the following people for their contribution to this round's preparation: the Codeforces problem coordinator Gerald; Seyaua, who tested the problems; Delinur, who translated the problem statements into English; and Aksenov239, who proof-read the statements.

The points distribution in both divisons will be standard.

By the way, Sammarize mentioned he was probably the eldest author of a Codeforces round in the Russian version of his latest round's announcement. Since I'm even older, now I am holding the title ;)

The contest is over, I really hope that enjoyed it. The standings: Div1, Div2. Congratulations to top performers in Div1:

  1. tourist
  2. ilyakor
  3. al13n
  4. aa2985759
  5. rng_58

Congratulations to the winner of Div2, Ruthles, too!

The problem analysis is here.

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

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

First \m/

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

time is no good

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

best of luck to all

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

hoooray the contest is coming

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

Is that you are elder because your name is "eldar" :P (just joke)

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

Why I can't open "Codeforces.com" in English !? :(

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

A contest right after witnessing an intense CodeJam Final http://code.google.com/codejam/contest/2437491/scoreboard

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

"The points distribution will be announced later."

Don't let it happen again, don't let it happen again...

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

    Thanks, I totally forgot about it.

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

Problems was so good! They was clear and understandable. Thank you gojira!

And Thanks for rapid SYSTEM TESTING!!!

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

OMG I did 5 hacks with only one test (in Div2 C) : 1000000000 1000000000 2
WTF and my solution got WA 44

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

    I'm not very surprised: C div 2 / A div 1 was harder than usually, and the pretests didn't contain input with really big integers (only ~= 3 codes had "Limit time excedeed" on pretests after one hour on div 1). Somebody can explain the solution to this problem? I found this one very weird...

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

      As we have to minimise the number of times, score get doubled, so we try to make maximum number of "k-1" blocks (k-1 consecutive correct answers), so we can find the maximum number of "k-1" blocks one can have using binary search, and after that, remaining answers will be correct consecutively, we put this block in thw beginning to minimise the score...

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

        Yes, I found this part, but I didn't know how to calculate this first big block: with 10^9 10^9 k, it is ((((k)*2+k)*2+k)*2....) 10^9/k times... With k very low, it can be slow to calculate it from classic maner and I don't see any way to use dynamic, binary search or other thing to calculate it.

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

          it's (2^(n + 1)-2)*k you can calc it using binpow

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

            oO I don't know why, but during contest, I was thinking that was on the form of something like: 2^(n1)*k+2^(n1-2)+2^(n1-4)*k ... I have been a little blind, the solution was a lot easier than I was thinking.

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

            hi Sir how you get this type of formula and intuition?

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

          Recursion technique comes in. At least for me.

          Let a0 = 0 and an + 1 = 2an + 2k. Then the result after computing n times (of the "add k times 2" part) is an. (You can try it yourself.) Now we want to solve this recursion.

          There are now two ways: Guess (an = (2n - 1)·2k) or use classic technique of solving recursions, characteristic equations. (You can read about the latter part in a lot of places. I'll also gladly explain when I'm awake enough; it's 1.30 am here, so probably later today.)

          Anyway. It's now simple. Since we want times, we want to find a109 / k. This is now simply (2109 / k - 1)·2k, which I believe you know how?

          ...it's posted above. But this gives the insight on how to get the result.

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

    And where I made a mistake was ...
    I needed to replace res %= MOD; with res = (res%MOD+MOD)%MOD;
    Today is not my day, today is tourist's day :D (Or maybe mine too ... 5 hacks ;) )

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

when is the rating updated

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

I got rank 39 this time and it is my best rank. Thank you!!!

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

"The problem analysis is here, but I did not manage to translate it into English fully yet." the link of 'here' is incorrect! It linked to 8615 entry, but it has to link to 8629 entry!

The problem analysis is here!

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

this contest is wonderfull i hope you take more contests in CF. thank you gojira

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

Maybe it's not the most appropriate place to ask. But why solved problems from this contest in problemset are not marked green as they always were?

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

    Actually they were green!

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

      Maybe that is because of the division...

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

        I think this happened because # of problems, for example:

        Contest 328, 329 problems: 328A-328B-329A-329B-329C-329D-329E

        But this Contest (337, 338): 337A-337B-337C-337D-337E-338D-338E

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

    Seems usually div1 is base contest and div2 contains "copy problems" but today vice versa. Note problem codes in problemset

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

In Div1-E Problem's statement, what is written in the picture? what language is it?

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

Kto nibud' mojet obyasnit' pochemu eto resheniye nepravilnoye? http://mirror.codeforces.com/contest/338/submission/4297116. Delayetsya dfs s memoizaciyey. Zapominayetsya dlya kajdogo napravlennogo rebra ( v , u) naibolee udalenniy p ot v v poddereve "pod" rebrom ( v, u) vkluchaya u. Kolichestvo reber 2n-2, dlya kajdogo vizova dfs zapominayetsya memo, t.e. itogo resheniye O(n log(n)). Pochemu to ne prohodit test #6

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

    k chemu minusi? eto ved' mesto chto bi zadavat' voprosi po zadacham

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

      Perhaps transliteration is considered poor style.

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

    Perhaps the multiplication p*g.size() is done in [u]int32.

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

sspa and Williamacm are cheating in this contest, AGAIN!

their codes for problem C (338C - Divisor Tree) are almost the same, where the only a few differences are some variables' name.

sspa's code for C: 4291930

Williamacm's code for C: 4292531

I found out their cheating last time in Codeforces Round 194 (Div. 1). I think CF team should pay more attention to cheating behaviour in contests.

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

    I found yongheng5871 and error202's codes for problem C are the same as sspa.

    yongheng5871's code: 4293325

    error202's code: 4293287

    In Codeforces Round 194 (Div. 1), they four were found cheating already, and they cheated in this contest again!

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

      I'll fix it :) Could you explain me why so many сhinese coders can't take part without cheating?

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

        Maybe cause we have so large amount of population? I think the percentage of cheating isn't distinctly different among many countries.

        I feel so ashamed about this.

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

          Its interesting that , code of all six cheater is same and all six is from same university/state , may be they all participated from same room in a team and shared each other code and idea .

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

            I think so, too.

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

    4294295 4295368

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

My best rank.Thanks to gojira Gerald and Seyaua!

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

So it seems like in Codeforces , delay time for system testing is inversely proportional to delay time for rating update ....

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

    For div 2 participant already got new rating, why it delayed for Div 1 ?

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

      I think they are handling cases caught in cheating like the one pointed out be yxdb and hence the delay.

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

why ratings for div1 participant hasn't been updated :|

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

One more case of copy-paste solution: 4294756 by kartimisin and 4291795 by enesoncu

The only difference is comment /*asgasdgasdg*/, I guess only to make source code look different to a trivial comparison:)

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

Sorry if this is considered redundant or spam, but nice contest (Y)

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

Nice problem

→ Reply