### UESTC_Nocturne's blog

By UESTC_Nocturne, 6 years ago, ,

Hello everyone!

Codeforces Round #201 is scheduled to take place at Friday, Sep. 20th at 19:30 MSK(23:30 CST)

Setters are: CMHJT and me.

Testers are: error202, havaliza and tourist.

Thanks to xiaodao for her help in rewrite the statements into codeforces style, Delinur for her help in translating the problems to Russian, and MikeMirzayanov, who has designed such a powerful platform.

Special thanks to tourist and Gerald in giving advise about the problems so we could put them in a more proper order.

500 — 1000 — 1500 — 2000 — 2500.

We are going to use standard score distribution in both divisions. The problems are not so hard, but you need more thinking rather than coding.

Good luck!

UPD1: Congratulations to the top 5 winners in each division!

1.cgy4ever

2.rng_58

4.Egor

#### DivII

1.Thrax

UPD2: the editorial is published here

•
• +283
•

 » 6 years ago, # | ← Rev. 2 →   +1 Thanks for the contest! The problems are not so hard, but you need more thinking rather then coding. It seems that the problems will be very interesting.Good luck to all participants!
•  » » 6 years ago, # ^ |   -69 please give me "-" thank you:)-v-
•  » » 6 years ago, # ^ |   -18 I see your point, Konjac.
•  » » 6 years ago, # ^ |   -20 Ok, sorry if I give bad idea (at first I think it's good idea). Thanks for your vote.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +7 Are you a bot who copy automatically comments with high number of upvotes? That's why you just used tjandra comment witout any reason? Edit: After looking at your previous comments, yes, it's exactly that...
•  » » 6 years ago, # ^ |   -9 You are right , they only needs a bright mind :)
 » 6 years ago, # |   0 Good luck to everyone.Thanks to XHXJ.
 » 6 years ago, # |   -15 Compact and interesting statements wanted! Thanks! :)
 » 6 years ago, # |   -45 Orz XHXJ ....
 » 6 years ago, # |   +2 I will definitely take part in this round because UESTC_Nocturne has given me a lot of suggestions on my computer programming. Special thanks to you and Good luck to everybody. By the way,his nickname in pinyin is "xue jie"~~~~
•  » » 6 years ago, # ^ |   -16 And for me too. Hope will be not so easy, not so hard. But if it's harder then it will be more intersting.
 » 6 years ago, # |   -14 ORZ...Good luck! God bless us!
 » 6 years ago, # |   -22 oh ! 26 hours remaining ! I can't wait ! :-<
 » 6 years ago, # |   -72 Thanks to the setter for preparing this contest :-)If there're some tricky case, I hope all tricky case is put on the pretest, so if my code got accepted (pretest passed) it'll accepted too after system test.
•  » » 6 years ago, # ^ |   +52 Ok, sorry if I give bad idea (at first I think it's good idea). Thanks for your vote.
•  » » 6 years ago, # ^ |   +14 So, What does hacking mean then?? All of solutions will be right and no one could hack another...
 » 6 years ago, # | ← Rev. 2 →   +9 A small question, xiaodao...her help? ^_^tourist!!!! Always be my super idol!!!!Hope it to be an awesome round and Everyone enjoys it!
 » 6 years ago, # |   +44 Sooo you say it is going to be the best tested round?:D:D
 » 6 years ago, # |   0 So sad that i can't take part in this contest, but all the same thanks to setters and testers and good luck for others.
 » 6 years ago, # |   +10 I apologize for my ignorance, but I always wondered what does UESTC stand for ?
•  » » 6 years ago, # ^ |   +21
•  » » » 6 years ago, # ^ |   -8 Thank you captain obvious. I actually wanted to know about from people that live there :)
•  » » 6 years ago, # ^ |   +7 University of Electronic Science and Technology of China.
•  » » » 6 years ago, # ^ |   -21 is it the best university in China?
•  » » » 6 years ago, # ^ |   0 yes，It is very famous in China.
•  » » » » 6 years ago, # ^ |   -13 He asked if it was the best
 » 6 years ago, # |   0 UESTC_Nocturne CMHJT It's first time for you in prepare a Round ?
•  » » 6 years ago, # ^ | ← Rev. 5 →   +8 CMHJT have already set a few hardest problems on codeforces.(#172 D, E and #183 C)UESTC_Nocturne has set lots of problems before but this is her first time on codeforces.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +2 first of all thanks for your reply. Can i get some links for this problems :) ?
•  » » » » 6 years ago, # ^ |   0 Reply not Replay :)
 » 6 years ago, # |   +1 Good luck to everyone!Long time no coding in codeforces.
 » 6 years ago, # |   -37 Who wants to get more points, put like.
 » 6 years ago, # |   +7 Best of luck to everyone , problems set by some of the best people in the arena , looking forward to it :)
 » 6 years ago, # |   +8 first time to attend div1 I know it is so hard for me but good luck
 » 6 years ago, # |   -22 minus
 » 6 years ago, # |   -21 today and he will codeforces 201, and involves more than 3,000 people
 » 6 years ago, # |   0 Wish everyone enjoy this round.
 » 6 years ago, # |   0 Why I always got WA on #4 on D Div2?
 » 6 years ago, # |   0 someone push Start System Testing button please
 » 6 years ago, # |   +21 Great round, thanks! Problems are interesting, indeed there was no need to write big solutions, except, maybe, problem B. Seems like it should cost 1500 instead of 1000 — it's the most hardcoding problem today =)
 » 6 years ago, # |   0 Why solutions are not visible even after the contest??
•  » » 6 years ago, # ^ |   0 because system testing isn't started yet
 » 6 years ago, # |   +2 Very great contest, problems were very intresting but not much hard. Could someone explain the solution of Div2.C / Div1.A? By induction I proved that if we have k numbers and there is no valid move, those numbers should be a, 2a, ... , ka, but couldn't find the complete solution.Thanks in advance.
•  » » 6 years ago, # ^ |   +1 Try GCD to solve this kind of tests.
•  » » 6 years ago, # ^ |   +9 Let's denote g = gcd(a1, a2, ...an). It's obvious that every number in the end will be divisible by g. From other side, we can obtain g with Euclid Algorithm. Thus we can prove that resulting set is . So the answer is , where amax is the greatest ai.
 » 6 years ago, # |   +21 I think the worst thing and the best thing in the world may be you HAVE to skip a high scoring solution because you find a bug in it. :D
 » 6 years ago, # | ← Rev. 2 →   0 had i seen the gcd part in C, it could have easily been my best! Hacked two solutions which made the same error as me. Good and false-motivating pretests!
 » 6 years ago, # | ← Rev. 3 →   0 After seeing the number accepted solution from the dashboard,it seems, in div-2 problem A is harder than problem B ... :(
 » 6 years ago, # |   +3 In problem D, the following phrase confused me:Please note that mzry1992 can give orders to the robot while it is walking on the graph. Look at the first sample to clarify that part of the problem.Does it mean that our orders can depend on where the robot goes, as opposed to some set of orders fixed before the movement?In the contest, I misinterpreted it as "the robot can receive orders only when it moves from the starting vertex", and that makes the statement controversial.
•  » » 6 years ago, # ^ |   +7 Yes, you can determine whether give a order to robot on every node it pass.
 » 6 years ago, # | ← Rev. 2 →   0 How did you solved A ? Thanks.
•  » » 6 years ago, # ^ |   0
•  » » » 6 years ago, # ^ |   0 Thanks a lot. I didn't notice that comment.
 » 6 years ago, # |   0 it seems lots of people FST in problem C. :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   +25 I hate TLE! I think an O(nlogn) algorithm should pass the system test.However, it didn't change anything about this round being a good round.
•  » » » 6 years ago, # ^ |   +3 my O( (b - a + n) log n) solution works in 124ms.
•  » » 6 years ago, # ^ |   +6 Yes, this is thanks to you.
 » 6 years ago, # |   0 I did not participate in this round,but i am glad to see so balanced and amazing problems thanks to UESTC_Nocturne. I want to solve problemc C(div 1),I know only DP solution in O(n*(a-b)).what is correct solution?
•  » » 6 years ago, # ^ |   +3 each time choose such x_i that makes a-a%x_i minimal and a-a%x_i>=b. the correctness can be proved by the monotonicity of your dp function.
 » 6 years ago, # |   +27 Tasks are very nice, especially A, C and D. (B is a coding task and it's fine. For E, I don't know the solution yet.)I'm very luck to win this round by finding this trick in task C: x[] can have repeat numbers.Thanks for the writers/testers!
•  » » 6 years ago, # ^ |   +6 Congratulation！For E, the standard solution is short, but need to find out something intereting, we will post editorial later and you can find details in it.
•  » » 6 years ago, # ^ |   +53 I've finally solved E in upsolving :) I had the idea during the round but didn't manage to deal with corner cases in time.Here's my solution: http://codeforces.ru/contest/346/submission/4523388Hopefully long method and variable names make it understandable.
•  » » 6 years ago, # ^ |   +38 Oh, and congratulations on the victory!
 » 6 years ago, # |   +4 When will ratings be updated???
 » 6 years ago, # |   +10 Why is TL for problem C is only 1 second?I wrote a solution in java during the contest and got TL (4522683). But when I wrote the same in c++ after the contest I got AC (4522630). This makes me sad.
•  » » 6 years ago, # ^ |   +3 There exists a subtle O(a-b+n) solution.Even written in java would get accepted.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +9 Well, yes. The solution is very nice indeed. However I found an (a-b) log n solution and I settled for it, because I figured it's common sense it should pass and it didn't. There are other (a-b) log n solutions that do pass however, but have smaller constant or use less memory.Did you intend to only accept the linear solution? If that's the case, why not give a-b <= 1e7 so people know the log n factor is too much?
•  » » » » 6 years ago, # ^ |   0 No,most (a-b) log n program written in java got AC.
•  » » » 6 years ago, # ^ |   0 I guess you might forget that you need to sort xi or you use radix sort instead of quick sort.
 » 6 years ago, # |   +2 Great contest!! Thanks to the problem setters and testers!!
 » 6 years ago, # |   +11 Cool problems. Never had so many dumb bugs in a contest in my life :SFor example, in A, I computed the gcd, but forgot to divide by it, i.e. didn't do anything with it :D
 » 6 years ago, # |   0 How to solve C (div1)?
•  » » 6 years ago, # ^ | ← Rev. 4 →   +6 There's a apparently a linear solution, but an nlogn solution that passes in time (for example, my solution in the practice room) is this.First, it's very important to make the given numbers unique, i.e. eliminate duplicates. Then you take each x_i and for every multiple of x_i between a and b (call it y) update best[a-y] = max(best[a-y], x_i) (I'll explain what best[i] is in a second). This whole thing is O(nlogn) (the worst case is when X = [2, 3, 4, ... n+1], because then you have the most multiples).When you have that, then you process numbers from a down to b. For every such number (let's call it c), you want to compute the minimum number of moves you need to do to get to it from a (that's the 'minlen' variable in my code).There are two options basically for each c. You either use the solution for c+1 and reduce a by 1, or you make a "jump". You store all the minlen values for larger c values in a Fenwick tree (or some such structure that allows you to do range minimum queries). Then you use best[c-a] to know what is the largest x_i that is a divisor of c. Using that x_i, you can get to c from any number in the set {c+1, c+2, ..., c+x_i-1} in one step. So you query the Fenwick tree for the minimum in that set, and increase that by 1.HTH
 » 6 years ago, # |   +1 My code prints output in pretest-1 in my PC BUT it prints no output in codeforces. Can anybody explain?
 » 6 years ago, # |   +26 Nightmare。
 » 6 years ago, # |   0 can anyone explain me logic behind the solution of problem C of DIV 2 ? I have seen 1-2 codes , that is something i was thinking while contest, but still i am not able to get that solution. Can anyone please explain little bit ? thanks in advance.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Idea: In the end of the game all numbers printed will be g 2*g 3*g ... MAX_NUMBER where g = gcd(a[1], a[2], ... a[n])
•  » » » 6 years ago, # ^ |   -10 This is actually not correct, though the answer with that assumption stays the same. Consider the case 2, 3, 5. Here g=1, but you can't make any moves, i.e. can't add 1 or 4.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +3 I can add 1 = 3 — 2 and then 4 = 5 — 1.Also, obviously we may get g because of Euclid algorithm. After that we may get all the numbers up to MAX_NUMBER using - g
•  » » » » » 6 years ago, # ^ |   +5 Ah, you are correct, my bad :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I guess this is problem A from div1 (the Alice and Bob one)?First, notice that it is never possible to get a number that is not a multiple of the gcd of all the numbers (let's call the gcd d). That's because if d divides both a and b, it will divide |a-b| as well. Therefore, you can divide all the numbers by d.Also, you will never be able to get numbers larger than the max number (obviously), or lower than 1. Now, the key thing to notice that out of the remaining numbers from 1 to MAX, the numbers you can't get always come in pairs. That is because if you have three numbers a
 » 6 years ago, # | ← Rev. 2 →   +20 Problem 346C - Number Transformation II has already been used on Baltic Olympiad last year link.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Sorry but .. what is the connection between this two problems? ..And ... is there any website I can submit these problems?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 The differences are that in BOI task you have to transform n into 0 (also there is many n's), you can use only second type operations and all x[] values are prime (but it doesn't really matter). When I saw problem C, I wondered that I just know the solution, which should also get AC.I don't know if it is possible to submit BOI problems somewhere, but here are statement + test data + solution. So, it was possible to find the solution during contest, which is not so good, I think.
•  » » » » 6 years ago, # ^ |   +18 There are literally thousands or even tens of thousands of problems with solutions on the web. Sometimes duplicates will occur, there's nothing really wrong with that. Probably 99% of the competitors in this round never saw this particular BOI problem.
•  » » » » 6 years ago, # ^ |   0 Since b is no longer always zero, there are more necessary tricks to avoid getting TLE.
 » 6 years ago, # |   0 Div2 D, had around 140 submissions , but only 10 got AC. Mine failed on #30 test case and cant seem to figure out a way around it. Any hints on how to solve it ?
•  » » 6 years ago, # ^ |   +1 You can do dynamic programming where the state (a, b, v) solves the subproblem where you're at index a in s1, at index b in s2 and the first v characters of virus are the suffix of the subsequence you've found in the prefixes of s1 and s2.I assume many solutions failed on updating v. When you take a character (s1[a]==s2[b]), it is not enough to check if (virus[v]==s1[a]) and then either increase v or set it to 0. Instead, you must do something very similar to Knuth Morris Prat, i.e. there might be a smaller prefix of virus present in the new subsequence (i.e. the new v value may be smaller than the old one, but not 0). See my code in the practice room for details if you like.
 » 6 years ago, # |   +29 4519236Hacked by this test: ZZZZZRR ZZZZZRR ZR 4520203Accepted but wrong output for same test. I think CF should add hack tests to final tests like TC.
 » 6 years ago, # | ← Rev. 2 →   -18 Problem A (Div 2): why "lexicographically smaller"? Simply "smaller".
 » 6 years ago, # |   +4 When will we get Editorials for this Round? Nice Problem Set :)
•  » » 6 years ago, # ^ |   +2 it's up now http://codeforces.com/blog/entry/8903
 » 6 years ago, # |   0 What deceptive pretests... originally accepting my brute force on E xD
 » 6 years ago, # |   0 This round was so good. "The problems are not so hard, but you need more thinking rather than coding" was true. Thanks for the setters :D
 » 6 years ago, # |   0 can somebody expain how to use KMP for tracing virus growth in DIV2 Problem-D
•  » » 6 years ago, # ^ |   0 Когда выйдет разбор?
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 разбор/editorial на английском правда
•  » » 6 years ago, # ^ |   0 not necesary at all , naive string matcing O(N ^ 3 * 26) for this problem , which is fast enough:)
•  » » » 6 years ago, # ^ |   0 can you explain how to define third dimension in dp corresponding to virus string
•  » » » » 6 years ago, # ^ |   0 dp[i][j][k] , we'are at 'i' in string1 and 'j' in string2 and soltuion string has suffix with maximum lenght k , such that prefix of virus.
 » 6 years ago, # |   +5 It was very intersting! Thanks!
 » 6 years ago, # |   0 The robot is so cute, isn't it?
 » 6 years ago, # |   +8 I love this competition。