JuanMata's blog

Codeforces Round #258
By JuanMata, 10 years ago, In English

Hello everyone!

Codeforces Round #258 (Div. 2) will take place on July 24, 19:30 MSK. Traditionally, Div. 1 users can take part out of the competition.

The round was prepared by PraveenDhinwa and me (JuanMata). This is our second Codeforces round, and hopefully not our last.

We have tried our best to make the problem statements as clear and interesting as possible. We hope that everyone will enjoy the round. :)

Special thanks to MikeMirzayanov for creating the wonderful Polygon and Codeforces platforms, Gerald for his extensive help in problem verification and testing, and Delinur for translation of problem statements into Russian. Without their help the contest would never have seen the day.

We wish all the participants good luck and high rating. :)

UPD: It is decided to use the dynamic scoring system.

UPD: Contest is finished. You can find the editorial here. :)

UPD: Congratulations to the winners. Here are the top 8 (the only ones to solve all the problems):

  1. skank
  2. western_theory
  3. jurbhm538
  4. chenrui9551
  5. zhouhebin
  6. MaxKU
  7. jmas2711
  8. hzwer

UPD: Wonderful statistics by DmitriyH can be found here. :)

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

Comments Comments (131)
| Write comment?
»
10 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Hey...It's time to make a Div 1 round! :)

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

Second time from India and third time from Indian subcontinent... :)
*** Editorail of your last round (Round 251) was awesome... Hope the best for this time, too... :)

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

    Thank you so much for your review. We will try to make it better this time :)

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

Who is going to be the main character? Devu again? :D

Good Luck

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

Why isn't this post on the home page too like all the other contest announcement posts? EDIT:fixed

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

Thanks, for providing the link of polygon. I was unaware of it.

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

    You could just google it !

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

      I was initially unaware of polygon, I only come to know about it through a blog post. I did not really know that everybody can make problems for even their own contests. polygon is quite nice :)

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

I know JuanMata personally and I can vouch for two things.

One is clear problem statements.

Another is — expect buttloads of football.

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

    "One is clear problem statements.", this should be correct, let us hope :).
    "expect buttloads of football.", no, not really.

    Actually he is a bit busy in his google orientation. So the problems statements are written by me. Otherwise you would have been completely right :)

    UPD: He has some time free today and tomorrow :) So you might expect both.

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

    i actually wanted this round to happen before the FIFA World Cup ended. but due to other contests in queue this was not possible. otherwise ur second point would have surely been true. :)

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

What was your first Codeforces round that you made its problem statemets?

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

There was a notification that today codeforces will not be available during some time, can somebody please tell me the exact timings when the site will be down, I forgot to note that down :(

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

    I Think it is 2:30am — 6:30am in IST as far as I remember It was 1:00am — 5:00am in MSK

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

    will Polygon also be down during that time?

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

why 258 is BOLD?

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

    so that it is easy for you to choose name of the directory for participating in the contest :P

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

Wa!So nice!

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

Wow, such contest, very good, but I'm too young, too simple and sometimes naive. But your contest makes me feel "EXCITED"!

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

Good Luck JuanMata!!

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

and scores??

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

    why so many downvotes?

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

      That is most stupid question ever asked.
      And there is always someone asking it.

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

    scoring now added to OP. :)

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

I like the editorials of PraveenDhinwa . They are awesome at codechef and hope here also .

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

YESSSSSS another JuanMata CONTESSSST!!!!

^_^

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

Even though the scoring is dynamic Please can you accept my request to sort the problems in increasing order of difficulty(According to you) so that I am atleast sure of solving the first two problems and don't have to click on standings again and again to confirm which problem is the most solvable .

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

    In IOI and ACM-ICPC problems are not in increasing order of difficulty.

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

UPD: It is decided to use the dynamic scoring system.

WHY??? :(

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

dynamic scoring = rating drop (in my case)

...but maybe this time finally :-D Never give up!

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

    I think this contest will prove exception to " rating drop (in my case)" :)

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

      If it really prove exception ,it will be my first time to be DIV1 let us play the game till the end and see the results :)

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

        haha, same here, currently I'm a little closer to DIV I, but it can be different after the contest, good luck ;-)

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

          anyway whatever the results I'm happy to solve D ,I think it's my first time ,I need only 6 point for DIV1

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

    same for me, I'm too unlucky in dynamic score

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

I'm so sad when my points gone down and my name change to be green. I will be more hardly.

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

i am a new user of codeforces can anyone help me please? what does DIV.1 and DIV.2 mean?

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

    When You are a beginner , you are attending the contest from DIV2 . When performing good in some DIV2 contests and achieving a handsome rating(1700+) , you will be able to attend the contest from DIV1.

    the problems of DIV1 are harder than the problems of DIV2. Good Luck :)

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

Dynamic score is ALWAYS dramatic... Can' t adjust the contest very well... And NO new users-without-any-submissions spoil our fun again...

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

Dynamic scoring is usually not very good!

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

In fact,I'm not good at dynamic scoring system.

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

4255 till now ,seems that we will have a long queue :)

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

I register for the contest but after that i realize i can't participate. very sad. wish all participants high rating!

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

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

I didn't see the part of problem D that string is only consisted by 'a' and 'b'. In my opinion you must wrote this important part of statement in problem statement, not only in input.

Btw, great contest, thank you.

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

    oh i got to know it now .... even i missed it .. but the contest was awesome .

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

    I didn't see it too :(

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

    i see "Each character of the string will be either 'a' or 'b'" right now after reading your comments. :))

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

    I didn't notice it too!

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

    I noticed it after 20 minutes. What about bolding these important things ? :))

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

    What was the approach to solve problem D?

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

Problem statement should be tested more carefully before launch. Hope next time we'll not be bother

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

Hey guys , I can't see others submission even after locking my problem.This problem is from the beginning. I lock my problem , I go to standings , I double click a submission of my locked problem. then I click the submission number. But nothing happens. After contest it's just fine. But I can see during the contest;. Why?

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

    During the contest, you can only see the codes of people in your ROOM after you lock. The way to do so is in the Room tab.

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

    you must go to the your room, not standing.

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

    You can see and hack only solutions of contestants in your room, so go to your room instead of standings

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

Awesome contest! Thanks, JuanMata and PraveenDhinwa :)

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

I suspect that problem B is difficult to hack, and there are small amount of hacks, but some systest fails will apear.

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

    Got WA on Test 74 :(

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

      I solved problem B incorrectly at 35 min. Later I tried to find mistakes, and found that tests like "3\n2 3 1" do not pass, because answer is "no", but program gives "yes\n2 3". I rewrote code, and had 10 minutes to search the same bug in codes of others, but it was difficult to understand whole long codes, and I didn't try to use this or more difficult test.

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

      I got WA on Test 69, because I did not take into account when n is 1 :(((

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

    507 sysfails! Initially 2187 -> later 1680 !

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

Nice round. Congrats to the authors! How to solve E ?

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

    Use Inclusion Exclusion princicple to solve the equationa[1] + a[2] + a[3] + .... + a[n] = s

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

How was problem C supposed to be solved?

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

    First, the condition is n%3 == 0. |Solve this system of equations : |x1-x2| = d1, |x2-x3| = d2, x1+x2+x3 = k with x1,x2,x3 is wins of team 1,2,3. Have 4 cases to solve. After check (n-k) is enough to give x1,x2,x3 to X1,X2,X3 satisfy X1=X2=X3=X.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
      5
3 0 0 0
3 3 0 0
6 4 1 0
6 3 3 0
3 3 3 2

      What with sample 5? It's impossible to play only three matches and have differences three won between 1v2 and 2 won between 2v3.

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

        yes, after k = 3 games this situation is impossible.
        the information given by our friend is inconsistent (what a bad friend, spoiling the football tournament for you! :P).
        so the answer is no by default.

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

      Thanx for explanation.I have implemented in the same way suggested by you in problem C but I am getting WA on test 4 and I am unable to determine the bug .Would you please take out your valuable time for it.Any help will be appreciated.Thank You. http://codeforces.net/contest/451/submission/7234615

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

      Thanx for explanation.I have implemented in the same way suggested by you in problem C but I am getting WA on test 4 and I am unable to determine the bug .Would you please take out your valuable time for it.Any help will be appreciated.Thank You. http://codeforces.net/contest/451/submission/7234615

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

    test for

    d1 =  ± d1

    d2 =  ± d2

    , always checking if you can have K games with those differences. doing so, you just have to solve a system of linear equations:

    Δ V1 + d1 = Δ V2

    Δ V1 + d1 + d2 = Δ V3

    Δ V1 + Δ V2 + Δ V3 = N - K

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

    I used binary search on the winning value of the middle team. Firstly , I have four case ++,-+,+- and --. Now for each case I tried to figure out the configuration that would fit into k. You can see my submission ,7228843.

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

      But it is O(T.log(N)), my algorithm is O(T)

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

Перед отправкой решения меня выкидывало из аккаунта.У кого ещё была такая же проблема?

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

    Надо поставить галочку "Запомнить на месяц" при входе

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

Wow, such fast system test which only cost 7 minutes.

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

System test is so fast! And I am very happy because I solved four problems in Div2 for the first time!

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

Give us editorial, please

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

worst contest that i see in my life!!!

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

WA on test case 67 :(

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

I scared I will get down rating

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

congratulations TankEngineer !

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

The contest was great! Btw, how to solve problem D ?

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

    Suppose you have found the number of odd and even palindromic substring for the first few characters of the string. For example, aabaaabb have 8 even palindromic substring and 13 odd palindromic substring. At the same time, we maintain the number of 'a's at even and odd positions, and the number of 'b's at odd and even positions respectively. In the above example, we have 2'a's at odd positions and 3'a's at even positions, while we have 2'b's at odd positions and another 'b' at even position.

    When we append a new character to the end of the string, we can compute the number of palindromic substring which ends with the new character. For example, if the appended character is 'a', the number of odd palindromic substring which ends with the new character will be the number of 'a's at odd positions, and the number of even palindromic substring which ends with the new 'a' will be the number of 'a's at even positions. Hence, the new string aabaaabba will have 11 (8+3) even palindromic substring and 16 (13+2+1) odd palindromic substrings (don't forget to consider the new character as a substring of length 1). There are several cases to consider depending on the parity of the position for the new character, but it is not hard to code them out.

    Repeat the above steps, each time appending a new character to obtain the final results. Example solution here: 7227422

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

      I didn't notice that the substring between 2 'a' or 'b' is always a good string :( If I did, I would be violet now :(

      Anyway, thank you very much :D

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

too long, update rating

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

Juanmata, fortunately for you, someone got 258th place, however, no one got 123th place in a round prepared partially by praveen123

If you didn't understand what I am talking about, read this comment

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

    LOL. but atleast OP has got +123 votes (at the time of writing this comment). :)

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

Did anyone use Hightail for the contest ? How was the experience ?

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

Nice Round.. Got many fun reading and thinking about the problems.. Still getting fun analyzing the errors of mine... Thank you very much.. Enjoyed the contest.. Hope we will get many more like this..... :D

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

Gave very bad contest but still +11. So sad.:(

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

I got down rating !

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

Thank you for the contest :) Very interesting problems.

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

Unbelievable! TankEngineer solved all problems in less than half an hour!!! Congratulations)

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

Problem D was awesome. Loved it :)

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

Hii,

In question B test case 26#

5

373362086 994096202 767275079 734424844 515504383

why "yes 2 5" is not an answer?by applying this, the sequence below is now a sorted sequence.

373362086 515504383 734424844 767275079 994096202

Please tell me if I am doing something really foolish.

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

In the title, why the font of "258" is Times New Roman, but not Verdana as "Codeforces Round"? :P

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

Round Stats

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

hey... in Problem C, initial number of wins for a, b, and c are not coming to be integer values for some test cases like: -> 999999999980 258442058745 258442058715 258442058720.

Please correct me if I am wrong.

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

    If n % 3 != 0, answer is "no". Because each team must have n/3 wins.

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

      Thanks for your reply...but that was not what I asked. -_-

      → Reply