Alex_2oo8's blog

Codeforces Round #206
By Alex_2oo8, 11 years ago, translation, In English

Hello everyone!

Very soon on 13 october at 19:30 MSK will take place Codeforces Round #206. I am author of the problems and it's my first round!

I would like to thank problem coordinator Gerald Agapov (Gerald), Evgeny Vihrov (gen) for problem testing and Mary Belova (Delinur) for translation of statements to English. Special thanks to Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

Score distribution will be standard in both divisions: 500-1000-1500-2000-2500.

I wish good luck for everyone and hope that you will enjoy the problems!

Congratulations to the winners! Special congratulations to rng_58, the only participant, who have solved all 5 problems!

First division:

  1. rng_58
  2. sankear
  3. VArtem
  4. sillycross
  5. Endagorion

Second division:

  1. sola_93
  2. Bega
  3. squirtle
  4. Dixtosa
  5. anupam.kanyal

UPD The editorial has been published.

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

Comments Comments (91)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it +82 Vote: I do not like it

I would really love if authors introduce with something about them that what they like, things they are working on, what motivated them to write, how fun is it to write problems and other stuff :)

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

    Maybe that he tell you how to solve these problems will be better.

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

      Those are called tutorials.

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

Why most div1 contests are either on Friday or Sunday?

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

New author, new type of problems! GL && HF!!!

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

Hope your first round Successful.

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

    What a D problems!
    0 Accepts for D in div2
    1 Accepts for D in div1

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

      It shows that Problem D was made totally professionally by Alex_2oo8.

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

        And it also shows that the problems were not ordered correctly — 173 accepts for E in Div1.

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

      & What a nice and beautiful problem E(div2)!
      Thanks U Alex_2oo8!

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

your rating graph is really impressive and motivating.. :)

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

i don't know why but : i have a feeling that it's gonna be an awesome round !

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

Gonna be my first CONTEST , can't wait :D

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

    "Score distribution will be announced soon." Soon = 2 minutes before start ? :|

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

contest started, and Score distribution not yet announced. >:(

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

Score distribution will be announced soon. Soon means after the contest ?

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

What is test 4 of Div1.B ?!

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

    You Misunderstood the question :D Read it again.

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

      what is the problem?

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

        Adding a letter to the string is different from moving on the board. Player can jump from one grid on the board to another grid as long as the corresponding strings are the same.

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

      same with me. 5 minutes before the contest, I realized that I was reading the question wrong :(

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

      Oh! I read again! Thanks!;)

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

    I looked my code many times and I couldn't find my bug. Damn it!!!

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

    I'd guess something like:

    3
aba
bcc
ccc

    (answer should be FIRST)

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

      If I understand problem...Optimal way must be 1,1 2,1 and sth... so DRAW?

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

        The players are not literally walking through the board, just building strings and verifying that they are correct. When after second move state is "ab" the player can extend it to both "aba" and "abc".

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

          But the problem said that "both players played optimally well",so,second won't be move to right at his first step

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

            It doesn't matter where he will "move", because he will get "ab" either way. The state in the game is just the string itself, not the way in which it was reached.

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

    I think it's something that stops solutions (like mine, that I couldn't fix in time) that don't account for the fact that the same string can be made by multiple correct paths. Like, if you make the state of the game a position on the board, the choices are to go right or down. But since the game is played with strings, not (directly) with paths, there can be more than two valid moves from a given state. (sorry if confusing)

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

    you can see that after the contest !!!!!

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

I get the feeling that systemtest on C is going to be deadly for many people :D

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

What was approach for Div 1 C? I did a n*logn*logn approach. seems like it will fail :(

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

    I think some pre-operation can change the order to O(nlog n).

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

System testing in this contest is really fast :) quiet happy about it :D

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

Why was E E.. :)

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

very good system test speed

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

Can somebody tell a solution of C (Div. 2)? Thanks.

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

    the solution will look like L L L . . L R . . R R R

    check the solution for each possible combination of Ls and Rs

    The solution for any combination =

    L*(number_OF_L) + R*(number_OF_R) + (QL or QR * abs(n-2*number_OF_L)-1)

    take the best

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

      Wow, much simpler than I thought. Thanks a lot.

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

    I spent the whole time trying to find a dp equation for it but it actually is a simple simulation question. Answer to the problem is MIN(all weights from right arm , first from left arm and rest from right arm, first and second from left and rest from right and so on until all from left arm).

    Take the case when we pick first and second from left arm and rest from right arm.Here, we get the minimum when we take w1 from left, w(n-1) from right , then w2 from left arm and then w(n-2) followed by rest from the right.This will remove the 2*qr overhead from the last 2 weights in the right and so on for the rest of the cases. Hope it helps!!

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

    You have to choose some index i (0 <= i <= n), such that the robot takes all the items <= i with the left hand, and all items > i with the right hand.

    The cost of taking the items, will be l * sum of weights of items <= i + r * sum of weights of items > i. Additionally, by choosing i, the robot takes i items with the left hand and n-i items with the right hand. If he takes the same number of items with each hand, or one more with the left/right hand, it's possible to alternate taking the objects. Otherwise, the additional cost for repeatedly taking items with one of the hands will be Ql * max(0, i — (n-i) — 1) + Qr * max(0, n-i — i — 1).

    If you precompute the cumulative sum of all weights in an array, you will be able to find the cost of choosing i in O(1), and you just need to find the minimum cost for 0 <= i <= n.

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

For both last div1 contest , this contest , problem E's score was wrong!!!

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

Did anybody notice nobody solved problem D for Div 2 (in the contest)?

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

    And only 1 person in Div 1 solved problem D too? I think the problem setter should have put the 2 Ds in H position!

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

why E is so easy and B is so hard???

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

    A x492
    B x37
    C x127
    D x1
    E x137

    I think that's unfair for those who just haven't read E on time. Maybe the authors meant some complicated solution instead of 3d dynamic programming?

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

      Oh, yeah, it's author's fail that some people didn't read E. For these people contest must be unrated, I think.

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

        Scoring doesn't affect your ability to read all problems. No reasons for the round to be unrated even for some contestants.

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

          I guess it was just sarcasm (or at least, nice try to be sarcastic), not an actual suggestion to make round unrated.

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

            Then that comment is addressed to you, not wackloner.

            Why do you think that it was unfair to put E problem on the place of E? All contestants were in equal condition.

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

              I didn't suggest unrated round too.

              Because it's easy. "All contestants were in equal condition" — it's not the only criterion for a nice round. We would also be in equal conditions if the results were purely random (with equal distribution for all contestants), so what?

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

              If we do a dice roll and select our winners based on that, it's fair for everyone as everyone is in the same condition.

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

                Yeah, it's fair — but there's no programming involved. In fact, dice games are much more popular than programming ones :D

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

        No, it's just author's fail E is placed E.

        (ok, edit: it was unfair for every contestant.)

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

          It wasn't unfair anyway. Just little author's mistake.

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

            Fair, unfair, I don't want to argue about words, I think anyone will agree that it was just, you know, bad.

            (And sure it was definitely unfair at least for problem E — it could be solved by more people.)

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

C(div.2) I have passed all pre-tests, but after system testing has recieved a WA#12. I understand my solution is wrong, but can somebody explain me how to solve this problem.

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

Very nice problem set, I really liked DIV2 E, you had to pay great care to get it right.

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

I really love this time for competition so let it be traditional. By the way I really love this kind of task, low size of code, big size of thinking. ;-)

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

Can anyone explain why this submission (problem B div 1) getting WA on 4th test case: 4776138?

My answer is "SECOND" because if both player play optimally, the string will be "cbcbcbc" and there are more 'b' than 'a' (but correct answer is "FIRST" and I don't know why). please correct me if i'm wrong?

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

    Read the huge discussion above -- you understood the problem wrong.

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

      Thanks for your reply :-) You're right, I did't undrestand the problem completely.

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

    it's not a simple game on the board — it's game with strings. After each move the string is fixed not the position an the grid. So in the test 4 after second move players have string "cb" and the next move for the first player is string "cba" — this is correct string and so the final string is "cbaaaaaac"and the first player win.

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

      Thank you for your detailed explanation, finally I understand why I'm wrong :-)

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

    The player are not moving on the board but are actually constructing strings & checking whether they are "good". For the 4th Test case:
    5
    cbbbb
    bcbbb
    aacbb
    aaacb
    aaaac

    • In the first turn, FIRST chooses "c" since this is only good string available.
    • Then, SECOND chooses "b" again because this is the only possible good string of length 2.
    • Now, in the third turn, FIRST looks for the paths with the current string on the board. It find two paths one horizontally left & other vertically down. On horizontal, she has choices "b" & "c". On Vertical path, she has choices "c" & "a". She chooses "a" because subsequently it would lead to her victory. .
      .
      the game continue
      .
      .
      Finally the string is cbaaaaaac if both play optimally & hence "FIRST" wins. Hence, this is the correct answer. Hope this helps to understand the problem. I also missed this point and got a WA.
    → Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Awesome round !! # Enjoyed throughout the ride :P # Couldn't figure out where I went wrong in Problem 'C'. If anyone would wish to take time in helping me, here is the submission detail : 4776717. Author : Expecting more rounds from you.

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

    There are one object with weight 93

    if your robot use left hand, the cost will be 93*78=7254

    if your robot use right hand, the cost will be 93*94=8742

    the minimum cost is 7254, but your output is 0.

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

Why is my program got TLE when it's already print the output? 4774997

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

Wonderful round! if there were the authors of this contest, I would definitely huge them!:D

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

Div2 Problem D reminds me of UVa. :(

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

had nice time.. great contest !! :D kudos to problem setter Alex sir :)

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

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

I dont knw why I got TLE for Problem Div1 E. As per my calculation the complexity is 42*6*18*3*5000= 68040000 (approximately). Where is my assumption going wrong? http://mirror.codeforces.com/contest/354/submission/4778403

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

Great problemset. But I can't think of a solution for problem Div1 C / Div2 E. Any ideas please?

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

    X is a valid GCD if for each a_i we have n_i * X <= a_i <= n_i*X + k for some numbers n_i. For each value of X we can try each possible multiple of X, and count how many elements in the array are in the range [n_i*X,n_i*X+k] by using an array d[p] = number of elements in the array less than p. We simply pick the greatest X for which all elements a_i were inside the ranges of X's multiples.

    If we check every X (2<=X<=1000000) and its multiples (1 <= n_i*X <= 1000000), we make around 10^7 constant time queries. This is fast enough to pass the time limits.

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

      Got it AC :). Very useful explanation. Thanks very much.

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

      what is the d[p],the p means what?

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

        The value of a number. E.g. if you have numbers 1, 1, 4, 6, than dp[0] = 1, dp[1] = 2, ..., dp[4] = 3, dp[5] = 3, dp[6] = 4.

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

Any hint for DIV2 D?

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

When will the tutorials be published?

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

Such an honor : ))

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

Quite good problem! But I think the points of B in Div 1 can be increase

→ Reply