### Alex_2oo8's blog

By Alex_2oo8, 9 years ago, translation,

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:

Second division:

UPD The editorial has been published.

• +133

| Write comment?
 » 9 years ago, # | ← Rev. 2 →   +82 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 :)
•  » » 9 years ago, # ^ |   -38 Maybe that he tell you how to solve these problems will be better.
•  » » » 9 years ago, # ^ |   +23 Those are called tutorials.
 » 9 years ago, # |   +30 Why most div1 contests are either on Friday or Sunday?
 » 9 years ago, # |   +16 New author, new type of problems! GL && HF!!!
 » 9 years ago, # |   +22 Hope your first round Successful.
•  » » 9 years ago, # ^ |   +31 What a D problems! 0 Accepts for D in div2 1 Accepts for D in div1
•  » » » 9 years ago, # ^ |   +13 It shows that Problem D was made totally professionally by Alex_2oo8.
•  » » » » 9 years ago, # ^ |   +12 And it also shows that the problems were not ordered correctly — 173 accepts for E in Div1.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   +5 & What a nice and beautiful problem E(div2)! Thanks U Alex_2oo8!
 » 9 years ago, # |   +27 your rating graph is really impressive and motivating.. :)
•  » » 9 years ago, # ^ |   -7 Who's graph? Me?!
•  » » » 9 years ago, # ^ |   0 i didn't replied to your comment.. i commented to the author of this post. :)
•  » » » 9 years ago, # ^ |   0 Alex_2oo8, ofc
 » 9 years ago, # | ← Rev. 2 →   +1 i don't know why but : i have a feeling that it's gonna be an awesome round !
 » 9 years ago, # |   -7 Gonna be my first CONTEST , can't wait :D
•  » » 9 years ago, # ^ |   +3 "Score distribution will be announced soon." Soon = 2 minutes before start ? :|
 » 9 years ago, # | ← Rev. 2 →   -32 contest started, and Score distribution not yet announced. >:(
 » 9 years ago, # |   -18 Score distribution will be announced soon. Soon means after the contest ?
 » 9 years ago, # |   +21 What is test 4 of Div1.B ?!
•  » » 9 years ago, # ^ |   +6 You Misunderstood the question :D Read it again.
•  » » » 9 years ago, # ^ |   0 what is the problem?
•  » » » » 9 years ago, # ^ |   +11 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.
•  » » » 9 years ago, # ^ |   0 same with me. 5 minutes before the contest, I realized that I was reading the question wrong :(
•  » » » 9 years ago, # ^ |   0 Oh! I read again! Thanks!;)
•  » » 9 years ago, # ^ |   0 I looked my code many times and I couldn't find my bug. Damn it!!!
•  » » 9 years ago, # ^ |   +7 I'd guess something like: 3 aba bcc ccc (answer should be FIRST)
•  » » » 9 years ago, # ^ |   0 If I understand problem...Optimal way must be 1,1 2,1 and sth... so DRAW?
•  » » » » 9 years ago, # ^ |   +8 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".
•  » » » » » 9 years ago, # ^ |   0 But the problem said that "both players played optimally well",so,second won't be move to right at his first step
•  » » » » » » 9 years ago, # ^ |   +2 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.
•  » » 9 years ago, # ^ |   0 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)
•  » » 9 years ago, # ^ |   0 you can see that after the contest !!!!!
 » 9 years ago, # |   +25 I get the feeling that systemtest on C is going to be deadly for many people :D
•  » » 9 years ago, # ^ |   0 Yups, and in both divisions : )
 » 9 years ago, # |   +8 What was approach for Div 1 C? I did a n*logn*logn approach. seems like it will fail :(
•  » » 9 years ago, # ^ |   +7 I think some pre-operation can change the order to O(nlog n).
 » 9 years ago, # |   0 System testing in this contest is really fast :) quiet happy about it :D
 » 9 years ago, # |   +75 Why was E E.. :)
 » 9 years ago, # |   +1 very good system test speed
 » 9 years ago, # |   0 Can somebody tell a solution of C (Div. 2)? Thanks.
•  » » 9 years ago, # ^ |   +1 the solution will look like L L L . . L R . . R R Rcheck the solution for each possible combination of Ls and RsThe 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
•  » » » 9 years ago, # ^ |   0 Wow, much simpler than I thought. Thanks a lot.
•  » » 9 years ago, # ^ |   0 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!!
•  » » 9 years ago, # ^ |   +1 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.
 » 9 years ago, # |   +25 For both last div1 contest , this contest , problem E's score was wrong!!!
 » 9 years ago, # |   +4 Did anybody notice nobody solved problem D for Div 2 (in the contest)?
•  » » 9 years ago, # ^ |   +2 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!
 » 9 years ago, # |   +27 why E is so easy and B is so hard???
•  » » 9 years ago, # ^ | ← Rev. 2 →   0 A x492B x37C x127D x1E 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?
•  » » » 9 years ago, # ^ |   -26 Oh, yeah, it's author's fail that some people didn't read E. For these people contest must be unrated, I think.
•  » » » » 9 years ago, # ^ |   +1 Scoring doesn't affect your ability to read all problems. No reasons for the round to be unrated even for some contestants.
•  » » » » » 9 years ago, # ^ |   +3 I guess it was just sarcasm (or at least, nice try to be sarcastic), not an actual suggestion to make round unrated.
•  » » » » » » 9 years ago, # ^ |   0 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.
•  » » » » » » » 9 years ago, # ^ |   +8 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?
•  » » » » » » » 9 years ago, # ^ |   -7 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.
•  » » » » » » » » 9 years ago, # ^ |   +8 Yeah, it's fair — but there's no programming involved. In fact, dice games are much more popular than programming ones :D
•  » » » » 9 years ago, # ^ |   0 No, it's just author's fail E is placed E.(ok, edit: it was unfair for every contestant.)
•  » » » » » 9 years ago, # ^ |   +4 It wasn't unfair anyway. Just little author's mistake.
•  » » » » » » 9 years ago, # ^ |   0 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.)
 » 9 years ago, # |   +1 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.
•  » » 9 years ago, # ^ |   +3 4769568 Nice solution for C div2
 » 9 years ago, # |   0 Very nice problem set, I really liked DIV2 E, you had to pay great care to get it right.
 » 9 years ago, # |   +8 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. ;-)
 » 9 years ago, # |   +3 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?
•  » » 9 years ago, # ^ |   0 Read the huge discussion above -- you understood the problem wrong.
•  » » » 9 years ago, # ^ |   0 Thanks for your reply :-) You're right, I did't undrestand the problem completely.
•  » » 9 years ago, # ^ |   +3 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.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   0 Thank you for your detailed explanation, finally I understand why I'm wrong :-)
•  » » 9 years ago, # ^ |   +3 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.
 » 9 years ago, # |   +4 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.
•  » » 9 years ago, # ^ |   0 There are one object with weight 93if your robot use left hand, the cost will be 93*78=7254if your robot use right hand, the cost will be 93*94=8742the minimum cost is 7254, but your output is 0.
•  » » » 9 years ago, # ^ |   0 @tjandra : thanks a lot. My bad.
 » 9 years ago, # |   0 Why is my program got TLE when it's already print the output? 4774997
 » 9 years ago, # |   0 Wonderful round! if there were the authors of this contest, I would definitely huge them!:D
 » 9 years ago, # |   +3 Div2 Problem D reminds me of UVa. :(
 » 9 years ago, # | ← Rev. 3 →   +2 had nice time.. great contest !! :D kudos to problem setter Alex sir :)
 » 9 years ago, # |   +28
•  » » 9 years ago, # ^ |   0 :)(for those intrigued, as I was: WA on test 7)
•  » » 9 years ago, # ^ |   +3 It was trying to prevent you from that hack but didn't succeed!
 » 9 years ago, # |   0 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://codeforces.com/contest/354/submission/4778403
 » 9 years ago, # |   -10 Great problemset. But I can't think of a solution for problem Div1 C / Div2 E. Any ideas please?
•  » » 9 years ago, # ^ |   +11 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.
•  » » » 9 years ago, # ^ |   0 Got it AC :). Very useful explanation. Thanks very much.
•  » » » 9 years ago, # ^ |   -15 what is the d[p],the p means what?
•  » » » » 9 years ago, # ^ |   +1 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.
•  » » » » » 9 years ago, # ^ |   +1 dp[0]=0
 » 9 years ago, # |   0 Any hint for DIV2 D?
 » 9 years ago, # |   +6 When will the tutorials be published?
 » 9 years ago, # | ← Rev. 2 →   0 Such an honor : ))
 » 9 years ago, # |   0 Quite good problem! But I think the points of B in Div 1 can be increase