YuukaKazami's blog

Codeforces Round #146
By YuukaKazami, 12 years ago, In English

Hi!

Codeforces Round #146 is going to be here soon. Round is prepared by YuukaKazami, MinakoKojima. I write problems for Div I and MinakoKojima write for Div II. Gerald did a great job in coordinating round preparing, and he also give some pretty good advise about problems. I'd like to express my gratitude to him. Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces system and Polygon system as well and Mary Belova (Delinur) for translating problems. Also thanks to donehl for testing the problems and making his comments about the problems.

Score distribution is 500-1000-1500-2000-2500 in both divisions.

Hope you enjoy the problems! =)

I apologize for the 10 minutes delay.I'm very sorry for the inconvenience I caused. So I'm writing a good editorial for compensation :)

The Editorial is here: Editorial

Congrats to winners!

Div1:

1.rng_58

2.Dmitry_Egorov

3.bjin

4.Petr

5.Egor

6.tourist

Div2:

1.RiKang

2.Caesar11

3.Gabaum

4.ilona

5.Bidhan

6.sm_hossein

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

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

Orz .. .

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

sorry for the trouble

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

Orz WJMZBMR & xiaodao

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

That would be interesting to participate in contest made by you but unfortunately we have our Moscow ACM ICPC Quarterfinal today at the same time :-(

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

made in China... hope i can become yellow...

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

Orz

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

orz

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

orz！！！！！！！

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

why isnt the time again as usual ?

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

    Because there is a contest in Codechef tonight, Check here to see more details.

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

      i guess you are right but its a little hard to attend contest in this timing i wish they run in in another day but in the usual time

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

        Usually, contests end at 1:30 Am in China, as I see. Not good for any day :)

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

        2500 people think that time is ok.

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

        3:30 AM in FLorida — US, and it is good for me.

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

despite this there are a lot of contesters !!

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

Orz

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

This time is right!

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

Good luck to everybody. Have a nice exam.

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

orz

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

orz!!

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

What do these mysterious letters mean? Is it a Chinese word?

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

Let the battle begin

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

Orz

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

OMG again 10 mins delay :(

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

    Hey CodeForces, it's 4AM in Brazil and i've been awake since yesterday. =/

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

      I made an alarm to wake up, coz here is morning, if I knew I would'we made it 10 mins later, it would mean a lot to me :D

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

    I suppose it's not so easy to maintain the server. Be patient :)

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

That was Snooze

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

Hope I can become purple.Good luck everyone!

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

orz....

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

OMG!!1 Is YuukaKazami a girl?

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

    Sure not.

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

    ...Can you see my avatar?...I hope I could be a girl, though...

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

      There are 6 distinct characters in "wjmzbmr". These characters are: "w", "j", "m", "z", "b", "r". So YuukaKazami is a female and you should "CHAT WITH HER!".

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

        lol...So this guy will be fell in love with me again and see a "thin man" in real world~~~

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

        it's a trap.. :p

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

      It's hard to judge whether you're a girl or not through the avatar. ^.^

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

Too mathy for this morning...

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

    Many many many math to night, I am in american here is 5:55 am.

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

A, B, C, D — math. E — strings. Very nice problemset, xiaodao, thank you.

UPD: It's not a sarcasm :D

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

    Before end of contest, it was incorrect when you told even so rough classification...

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

Looks like Petr and tourist couldn't solve Div 2 problem

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

    Maybe they just worked on other high score problems, or challenging.. As a result, they earned more points than anyone who solved C.

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

It seems that system testing hasn't started now.When will it start?

UPD: It has started.

UPD: It seems systest today is very slow.

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

    I love when somebody plays in "Captain Obvious" game for contribution only so much.

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

Maths Everywhere!

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

Thank the authors for this intense thinking contest, great work! I wish the editorial would be done soon.

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

Anyone can teach me how to solve "how many times does a string x occur in a string s" as mentioned in the description of Div2 E?I sucked at that point already.

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

    The fastest way is to use Knuth–Morris–Pratt algorithm. Article on Wikipedia

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

      In this problem KMP wouldn't run in time (if you get 10^5 "a" queries on a 10^6 string your running time is 10^11). You need an Aho-Corasick automaton or a suffix array. Or something using hashing.

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

        Nezzar didn't ask, how to solve this problem. He asked just, how to calculate the number of occurences of one string in another.

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

          Just saying that either Aho-Corasick or a suffix array is an out-of-the-box solution for the problem as stated, but without the cyclic rearrangements. To find one string in one other string just once you could certainly use KMP.

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

systest in 3600 .. 3599 .. 3598 .. 3597 .. 3596 .........

UPD : 3595 .. 3594 .. 3 .. 2 .. 1 .. 0. Systest!

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

going back to blue again >_<

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

When is system testing?I'm worried that my C(Div2) will fail.......

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

Well people system test in two hours, american people go to sleep!!!!

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

finally starts

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

Seems I just have to wait for the editorial then :D

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

Is this the slowest systest ever?

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

    That's because there are 100+ test cases for Div.2 B and C

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

      But the number of test cases in each round before are also 100+.

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

    It is.(

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

Very slow judge :(

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

    it's good that problem E & D had less than 3 AC ,so we can imagine there is an end time for this slow system testing !

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

Problem D Div 2, I has just read some solution, but i can't understand :( Anyone help me please :D

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

    Let E[i, j] be the excepted score for clicks from i to j(inclusive). Let L[i, j] be the excepted 'o' s starts from left, of clicks from i to j. Let R[i, j] be something like L[i, j]. Then we have: 

    E[i, j] = E[i, k] + E[k + 1, j] + 2 * R[i, k] * L[k+1, j]

    , for any i < k < j.

    Think about: If we got x 'o's in clicks [i..k], y 'o's in clicks [k+1..j], then score x^2 is calculated in E[i, k], y^2 in E[k+1, j], and we actually need (x+y)^2 = x^2+y^2+2xy. And since R[i, k] and L[k+1, j] are independent, the 2xy part is calculated as 2 * R[i, k] * L[k+1, j].

    Now we take k = j — 1, i = 0, and let e[j] = E[0, j], r[j] = R[0, j]:

    e[j] = E[0, j] = E[0, j-1] + E[j, j] + 2 * R[0, j-1] * L[j,j] 
     = e[j-1] + p[j] + 2 * r[j] * p[j]
r[j] = (r[j-1] + 1) * p[j]
    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What an amazing solution :D

      Thank you :)

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

      what a amazing! I only come up with a O(n*n) dp solution.

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

        Me too! I try to DP it but failed :(

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

          I get a TLE in 68th case :(

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

            Of course :D

            I have never think like this solution :)

            It helps me so much, thank Ray again :)

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

              I got this solution 5 minutes after the contest, saddly. Then I waited hours for the system test to end. Finally I got 1AC.

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

The evil test case 61 of LCM Challenge :|

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

sorry for the slow judging...I put too many test in Div2B and Div1A...I didn't expect some solution are too slow T_T...anyway...the judging is done now...

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

    Anyway,I think it's a good contest.I would like also thanks to MinakoKojima for the problems in Div.2.

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

    This contest is very valuable, thanks to YuukaKazami and MinakoKojima. :D

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

    Try to refresh the rating as quick as possible.

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

      I suppose the system is calculating the rating change.

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

        Then why does it take 30 minutes to recalculate it for 2000 people? The complexity is O(n).

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

          good question ! :D

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

          You know how it works? 'Cause i don't.

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

          How slow is that :( I think it's n^3 :)))))

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

            Even it is n^3, it will be done in just one minute.

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

              :-? 2000^3 calculations in just one minutes

              Oh yeah, may be n^4 :))))

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

                Ha~~~

                But usually it is done in about ten minutes, I think.

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

                  Sure it is :D and the rating update has done :D

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

Egor — the luckiest man of this contest

His E's submission 2402930 is only 14s to the contest end and runs 16ms to the time limit.

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

    Well,He use some interesting strategy to reduce the time, It is just...very good job to do this cool stuff.

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

    I optimized my solution until last possible moment. Actually it runs between 2950-3050 ms on server, so I got lucky indeed

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

Ratings are now updated. Log off and on to see them.

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

Can anybody tell me why Div2.C 2398837 is Runtime error on pretest 1. exit code: 13131313 It is at least not throwing any exception in my system. I suspect BigInteger#isProbablePrime but don't know why?

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

    It even shocked me .. The same code run at IDEONE is also throwing Exception http://ideone.com/7efDIa

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

      i don't know java but use throws exception will lead u to correct runtime

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

        you mean main method throws exception like this 2405543 it didn't help ... still same issue. I don't know want is wrong. java experts please help.

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

I am quite shocked. My following simple Brute Force solution for DIV 2 Problem C:LCM Challenge got Accepted.. :D

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

    This problem is very easy if you think carefully :)

    It include 3 cases

    1: n odd => result = n * ( n — 1 ) * ( n — 2 );

    2: n is not odd and ( n mod 3 = 0 ) => result = ( n — 1 ) * ( n — 2 ) * ( n — 3 );

    3: n is not odd and ( n mod 3 <> 0 ) => result = n * ( n — 1 ) * ( n — 3 );

    Brute force is quiet "buffalo" for this problem :)

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

      nice observation but can you please provide proof of it

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

Hi A short-solution programming contest will hold on October 24 at gpac.blog.ir

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

the link for the tutorial is: http://codeforces.me/blog/entry/5592

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

what does orz mean? and when when will you write editorial? I'm waiting for that :)

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

    Editorial and orz

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

      orz is used in Japan's net-slang terms. "orz" is used to show when you are in a quick depression and sad or have given up on something.

      Before, thinking by myself what could it mean, I realized that orz denotes admiration and they thank the author in this way. But I was wrong, and now I still cannot understand why they are in a quick depression because of the round. Can anybody explain it?

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

Orz

→ Reply