By KADR, 9 years ago, translation,

Hello everyone!

Codeforces Round #153 will take place on Thursday, December 6th at 19:30 MSK. This is my third Codeforces round and I hope there will be more.

I'd like to thank Shtrix, Seyaua, sdya and Gerald for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I hope you will like the problems.

Good luck and have fun!

UPD: Complete version of English editorial is now available.

Congratulations to the winners!

Division 1:

Division 2:

• +173

 » 9 years ago, # |   -45 All that red color suggest a hard contest :)
•  » » 9 years ago, # ^ |   +21 I guess that not hard but interesting :)
•  » » » 9 years ago, # ^ |   -43 Thx for negative votes :D
•  » » » » 9 years ago, # ^ |   +19 You're always welcome)
•  » » » » » 9 years ago, # ^ |   -46 It's better to not write anything :)
•  » » » » » » 9 years ago, # ^ |   +2 It looks like NiVeR is trying to reach a new low of negative comment rating and he's doing a pretty good job at it. :)
•  » » » » » » » 9 years ago, # ^ |   -16 And hes not alone :d
•  » » » » » » » 9 years ago, # ^ |   0 You tottaly got me dude ;)
•  » » » » » » » 9 years ago, # ^ |   -8 LMAO GUYS YOU'RE SO FUNNY)))))))))))))))))
•  » » » » » 9 years ago, # ^ |   -12 OH MY GOD IT'S THE BEST JOKE I'VE HEARD!!!!)))))
•  » » » 9 years ago, # ^ |   0 Hope so :)
•  » » » » 9 years ago, # ^ |   0 So gì mà so
•  » » 9 years ago, # ^ |   +9 This was discussed a short time ago: http://codeforces.com/blog/entry/5975
•  » » 8 years ago, # ^ |   0 JOIN THE ILLUMINATI illuminati.order100@yahoo.com JOIN THE ILLUMINATI FROM SOUTH AFRICA, USA, OR ANYWHERE IN THE WORLD TODAY BE RICH, FAME, AND POSSES POWER.email us on illuminati.order100@yahoo.com for immediate initiation New members registration is now open online now !!!!! BENEFITS GIVEN TO NEW MEMBERS WHO JOIN ILLUMINATI. A Cash Reward of USD $300,000 USD A New Sleek Dream CAR valued at USD$120,000 USD A Dream House bought in the country of your own choice One Month holiday (fully paid) to your dream tourist destination. One year Golf Membership package A V.I.P treatment in all Airports in the World A total Lifestyle change Access to Bohemian Grove Monthly payment of \$1,000,000 USD into your bank account every month as a member One Month booked Appointment with Top 5 world Leaders and Top 5 Celebrities in the World. If you are interested call the agent now send your e-mail to illuminati.order100@yahoo.com for immediately initiation.New members registration is now open online — E-mail via illuminati.order100@yahoo.comJOIN THE ILLUMINATI AND GET RICH AND POSSES POWER''''
 » 9 years ago, # |   -13 AT LAST !!
 » 9 years ago, # |   -24 Hac in hora ... Et defectus
 » 9 years ago, # | ← Rev. 2 →   -21 I have to go to school on Dec.7 Maybe i can't do this.T T
•  » » 9 years ago, # ^ |   +21 :| who cares ??!!
•  » » » 9 years ago, # ^ | ← Rev. 2 →   -12 Chinese education only has exams!
•  » » » » 9 years ago, # ^ |   -25 One guy already said WHO CARES but i think we should repeat it. WHO CARES.
•  » » » » 9 years ago, # ^ |   +41 So better go to school. You can use "virtual contest" in Codeforces, but you can't use "virtual life" option.
•  » » 9 years ago, # ^ |   0 I understand you.
•  » » 9 years ago, # ^ |   +2 omg
 » 9 years ago, # |   +9 yeees!Can you make more contests,please?It's boring when there's nothing on codeforces...:)
 » 9 years ago, # | ← Rev. 2 →   +6 Are the scores of the problems decided? edit: Sorry, I was not asking for the scores of the problems, but if they will be static or dynamic :)
 » 9 years ago, # |   0 I think contest had better be arranged in Friday or Saturday，in that case more people can compete in contest.
•  » » 9 years ago, # ^ |   +4 No it wouldn't be better because we would had to wait more. Everyone is getting bored from waiting.
 » 9 years ago, # |   +19 Let's hope the server will stable during competition
•  » » 9 years ago, # ^ |   +6 Let's pray for the welfare of the server. 42. Amen.
 » 9 years ago, # |   0 Seyaua, sdya are the same person ! :D ****
•  » » 9 years ago, # ^ | ← Rev. 2 →   0 No. They are twins :D **** [link]
•  » » » 9 years ago, # ^ | ← Rev. 2 →   0 hmmm...but their pictures are same... how can it be?
 » 9 years ago, # |   +6 I think it has been long since last competition. Thanks for all the contests and their makers, I really enjoy myself in the contests!
 » 9 years ago, # |   +7 Good Luck Everybody!
 » 9 years ago, # |   0 Good luck everyone!! Have fun!! :D:D
 » 9 years ago, # |   -28 Was I the only man who had "error 502" now?
 » 9 years ago, # |   +49 There is one thing that I will never forget about this contestThere's only one thing Petya likes more than numbers: playing with little Masha.
 » 9 years ago, # |   +14 Little Petya likes "a lot of things" a lot :D
•  » » 9 years ago, # ^ |   +1 Sometimes you get a mistake, the author is the same :D Sorry for my bad english :p
 » 9 years ago, # |   +7 I solve problem B of Div.1then lock my answerand go hack two contestant with same Test Casebut unfortunately when i checked my hack TC too my code , I saw my solve give WA too :|
 » 9 years ago, # |   +3 What was the challenge case for Div 1 Problem B? No one did many challenges in my room, so my solution could be wrong :( .
•  » » 9 years ago, # ^ | ← Rev. 3 →   +6 2 32 12 1Answer: NO3 32 3 13 1 2Answer: YES
•  » » » 9 years ago, # ^ |   0 Now that someone tells me, I'm scared of testing my code on it...
•  » » » 9 years ago, # ^ |   0 My code managed to pass those tests. Do you mind sharing what test you used to hack me?
•  » » » » 9 years ago, # ^ |   0 4 32 3 1 43 1 2 4
•  » » » » » 9 years ago, # ^ |   0 YES?
•  » » 9 years ago, # ^ |   +1 Something like4 72 1 4 32 1 4 3
•  » » » 9 years ago, # ^ |   0 NO?
•  » » » » 9 years ago, # ^ |   +2 Correct answer is "NO".
•  » » 9 years ago, # ^ |   0 1 1 1 1Answer NO :)
•  » » 9 years ago, # ^ |   +6 I think if there was no challenges, it would be a lot of WA. This task checks contestant's attention.
 » 9 years ago, # |   +14 Very slow system testing :(
 » 9 years ago, # |   +36
 » 9 years ago, # |   +22 Are the solutions being checked manually?
•  » » 9 years ago, # ^ |   0 Seems that they put too many test cases in Little Xor.
 » 9 years ago, # |   +9 Sooooo slow system testing :(
 » 9 years ago, # |   +2 The problems are harder and harder?T T need to work hard^ ^
•  » » 9 years ago, # ^ |   +12 Sorry to say but it's easier than the last contest :)
 » 9 years ago, # |   +7 Unlike Codeforces Round #152, this contest has a very low speed system testing... :(
 » 9 years ago, # |   0 Everybody seems to get WA in test case 12 in Div 2 -problem B. I wonder what that test case is ?
•  » » 9 years ago, # ^ |   0 I guess a case with n<3.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   +2 I think many people think that "-1"'s case is only on n <= 2 and all array fill whit the same number. if N = 3 and array is {2, 1, 2} we can't do any swap.
•  » » 9 years ago, # ^ |   +3 You can see this test case after the contest.
 » 9 years ago, # |   0 System testing has already lasted 20 minutes, but checked solutions of first 15 minutes of contest, that's amazing speed:)
 » 9 years ago, # |   +2 why you need that too many test cases !!! :o
 » 9 years ago, # |   +1 very slow test system(((
 » 9 years ago, # |   0 Seems strange, but I think Problem B was harder than Problem C. Problem C was quite standard, and non-standard problems cause much more trouble for the competitors:)
•  » » 9 years ago, # ^ |   +3 It is so bad of me that I even did not check the tricky case that I generated for Div 2 B.
 » 9 years ago, # |   +83 Thank you for really nice problems and amazing contest :)
 » 9 years ago, # | ← Rev. 3 →   0 Here is my solution to problem B div 1: http://codeforces.com/contest/251/submission/2710934 The veredict was: "Runtime error on test 1". But I tested the same test in my computer with the same code and it worked fine. Has anyone had this problem?
 » 9 years ago, # |   0 For Problem B ,Div 2 , an O(n^3) solution is also passing [code]I noticed through the test case that it is actually never going O(n^3) when all elements of the array are not the same and when n is large . But I can not understand why this happens .Can anyone explain please
•  » » 9 years ago, # ^ |   0 I think it is misleading, if we consider n <= 10^5 how is it possible that O(n^3) would pass? Well I guess that the swapping which leads to unsorted array is found quite fast and that is why a solution with such big complexity passes. Because otherwise also O(n^2) would be difficult to pass in that time lime.
•  » » 9 years ago, # ^ |   +8 The complexity of this solution is O(N).Suppose N > 3. Then it's enough to check only 3 different pairs of distinct integers. One of them will be the solution we are looking for. The reason is that these 3 pairs lead to 3 different arrays, but there are only 2 possible sorted arrays, so one of these 3 arrays will be unsorted.
•  » » » 9 years ago, # ^ |   +2 +1 to that. Thanks.
 » 9 years ago, # |   +1 .. . How to solve Problem E. ? ... QAQ
•  » » 9 years ago, # ^ |   +11 I'll post the complete editorial in a few days. Now I can give you a hint.Suppose there exists a node of degree 3. Let's take any such node and call it a root. Then we can reduce our problem to the following one: given a non-root node v we need to calculate the number of ways to place the sub-tree of node v on a rectangle 2xK for some K with the restriction that v is placed to the upper-left corner of this rectangle. Note that the value of K can be determined uniquely from the size of sub-tree. This problem can be solved with DP in linear time.The reduction to the described problem is also non-trivial, but at least it's easier than the whole problem.
•  » » » 9 years ago, # ^ |   0 。。。THX alot !...
•  » » » 9 years ago, # ^ |   +3 editorial in English too, I hope? Google Translate doesn't work well sometimes.
 » 9 years ago, # |   0 How to solve problem D div 1 ?
•  » » 9 years ago, # ^ |   +2 BFS + DFS + Bitmap + convex hull (Y)
 » 9 years ago, # | ← Rev. 2 →   0 Can anyone show me the logic in choosing 0 (numbers that divide lcm(2..k)) to be the mediate value in problem C div 1?
•  » » 9 years ago, # ^ | ← Rev. 2 →   0 In case you misunderstood my words (I assume that by seeing those down votes), this is merely a question :)
 » 9 years ago, # |   +4 Anyone can tell me how to solve C div 1 :( Just a hint, plz :D
•  » » 9 years ago, # ^ |   +4 The essential trick was that if your current integer is divisible by all numbers from 2 to k, then the only thing you can do is to decrease this integer by one. Therefore, you can use dynamic programming to count how much time you need to reduce your integer by LCM. For instance, suppose a=80, b=3, k=3. Then LCM(2,3)=6. So you count separately the time you need to get from 80 to 78, then from 78 to 72, the from 72 to 66, ..., from 12 to 6, and finally from 6 to 3. It's easy to notice that all of those in the middle are equal.P.S. That's a shame that I didn't see this trick during the contest, but I was thinking of some DP with LCM...
•  » » » 9 years ago, # ^ |   0 Then LCM(2,3)=62 what ????
•  » » » » 9 years ago, # ^ |   0 I don't get your question. LCM(2..k)=LCM(2,3)=6.
•  » » » » » 9 years ago, # ^ |   0 Sorry, I already understand your answer :D Okay :D thanks for your hint :)
 » 9 years ago, # |   -12 Fail (( My solution in D(div2) was correct ... I just forgot to clear my array ...
 » 9 years ago, # |   +3 Editorial is published in Russian here @ http://codeforces.com/blog/entry/6054I wonder if it is possible for someone to please kindly translate that into English for me?
•  » » 9 years ago, # ^ |   0
•  » » » 9 years ago, # ^ |   +4 Google Translate often does not do a sufficiently adequate job, eg. grammar and syntactical structure is not preserved.
 » 9 years ago, # |   +4 Where can i see the editorial?
•  » » 9 years ago, # ^ |   0 Editorial is published in Russian here @ http://codeforces.com/blog/entry/6054
 » 9 years ago, # |   0 Are there any editorial?
•  » » 9 years ago, # ^ |   0 only published in Russian, I'm afraid.
•  » » » 9 years ago, # ^ |   +10 I'll publish the complete editorial on both languages soon. Currently I'm out of country and don't have enough time for editorial. Sorry for the delay.
 » 9 years ago, # |   0 I can't understand the Russian tutorial of Div.1 E. >_< I hope the English tutorial will be published soon. :)