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