### caustique's blog

By caustique, 6 years ago, translation, ,

Hello, Codeforces!

Codeforces Round #202 will take place today, September 27 at 19:30 MSK.

The idea behind the round was born when my friends and I were interning at Facebook this summer. This round probably has the highest number of authors for a Codeforces round to date. The authors of the problems are Azizkhan Almakhan azizkhan, Michael Kolupaev al13n, Filip Hlasek fhlasek, Ivan Mandura budabudimir and myself, Igor Demidov caustique.

Maxim Korystov dark_ai, Alexander Fedulin Jughead and Ibragim Ismailov ibra, Vladimir Chalyshev cmd and Sergey Sklyanichenko Sklyack helped us with preparation of the round.

The ideas behind the 2 problems were inspired by Anton Ermilov ant.ermilov and Dmitry Krasnov navi-spb.

Testers of the round are Alexey Safronov yarrr and Alexey Shmelev ashmelev.

I would also like to thank Gerald Agapov Gerald for his help in preparing the contest.

I hope you find problems interesting and diverse. I'm sure that everyone will find the problem to their liking.

Scores are as usual 500-1000-1500-2000-2500.

Good luck and have fun!

Congratulations to the winners!

Div. 1

Div. 2

Attention! Editorial for all problems is available!

• +272

 » 6 years ago, # |   +48 Awesome, time of next three rounds are close!
 » 6 years ago, # |   +82 Wow, first contest author from Kazakhstan
•  » » 6 years ago, # ^ |   -13 your name make me think about my favorite brower
•  » » » 6 years ago, # ^ |   -8 catch a diaosi!!!
•  » » » » 6 years ago, # ^ |   0 I think you're Chinese
•  » » » » » 6 years ago, # ^ |   0 YES YOUR RIGHT !!
 » 6 years ago, # |   +1 I'm damm sure, this gonna be some round !!! I mean 5 authors => awesome + cool + exciting !!! :)
 » 6 years ago, # |   -16 i hope there won't be any mathematical problems , but still g & hf to all
 » 6 years ago, # |   0 Good Luck and Have Fun
 » 6 years ago, # |   +43 Many authors = Many personalities = Different kind of problems = Good for everyone ;)
 » 6 years ago, # |   +24 Scores will be announced closer to the beginning of the round. 2 min remain :|
•  » » 6 years ago, # ^ |   0 f5 f5 f5 f5
 » 6 years ago, # |   0 this is the worst contest I've ever seen
 » 6 years ago, # |   +3 1st problem has very weak pretests. I hacked 5 solutions with 25 25 25 100 ))25 25 50 50 100 is also good for hacking ))Thx for contest)
•  » » 6 years ago, # ^ |   0 Can you tell me how to hacked other's solution?
•  » » » 6 years ago, # ^ |   0 After you pass the pretest, lock your problem in the dashboard using the icon like a lock, then you can view and hack others' solutions in the room page by double clicking on scores of that problem.
•  » » » » 6 years ago, # ^ |   0 Thank you very much! hehe!!
 » 6 years ago, # | ← Rev. 2 →   0 Many tricky cases in problem A(Div 2) ... :DI hacked six solution with 25 25 25 100 &25 25 25 100 50 ...:)Thanks for the contest... :)
•  » » 6 years ago, # ^ |   0 Mine is 25 25 25 100 & 25 50 50
 » 6 years ago, # |   0 the problems of today's Div-2 contest are tougher than usual Div-2 contests! i wonder why?
 » 6 years ago, # |   +3 Pretest 9 for Problem B Div 2 :(
•  » » 6 years ago, # ^ | ← Rev. 2 →   +2 I think pretest 9 is smth like this:53 3 3 3 3 3 3 2 3
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 Found one special case:83 4 4 5 10 10 10 10 10Though I didn't pass yet. Answer should be 23.
•  » » » 6 years ago, # ^ |   +3 I think the answer is 41
•  » » » » 6 years ago, # ^ |   0 Yes, my fault. 41 is the correct answer.
•  » » 6 years ago, # ^ |   0 To hell with this pretest 9 on Problem B Div 2.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +1 Nothing was helping me, but total rewriting helped.
•  » » 6 years ago, # ^ |   0 Might be one of these : 11 3 3 3 3 3 3 3 3 4OR9 2 10 10 10 10 10 10 10 9
•  » » 6 years ago, # ^ |   0 well, as it turned out, Pretest 9 was a big test case, different from what we expected :P
 » 6 years ago, # |   0 Why div.2 so hard just on problem B... Do I only have to solve it by DP?
•  » » 6 years ago, # ^ |   0 I solved the problem by dp but I saw some greedy solutions but I do not know if there correct
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 Found one special case:83 4 4 5 10 10 10 10 10Though I didn't pass yet. Answer should be 41. Greedy seems to be unavailable.
•  » » » » 6 years ago, # ^ |   0 no, 41
•  » » » » 6 years ago, # ^ |   0 it should be 41 41 > 23 I use greedy for my solution but no so sure about it :D
•  » » » » 6 years ago, # ^ |   0 no answer should be 41 since you can use 4 (costs 5 ) and 1 (costs 3)
•  » » » » 6 years ago, # ^ |   0 Answer should be 41
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 by a glance on the question I think we need to use at most 2 digits for all optimal solution. O(9*9)?
•  » » » 6 years ago, # ^ |   +1 I think we must try get max numbers and then change some first on other, more big. I don't sure. http://codeforces.ru/contest/349/submission/4583482
•  » » » » 6 years ago, # ^ |   0 Yes, It was correct solving. I got OK
•  » » » 6 years ago, # ^ |   +1 no for examle 61 7 8 8 8 8 8 8 8 9 it should be 99811111
•  » » » » 6 years ago, # ^ |   0 Thanks for this testcase.
•  » » 6 years ago, # ^ |   +1 Need to use DP for problem B.
•  » » » 6 years ago, # ^ |   +1 nope, greedy solution is ok just find maximum digit can be made and use the remainder to change some first digits into higher digit
•  » » » » 6 years ago, # ^ |   0 Cool.. Thanks for your input. I did use greedy at first but messed up with the implementation.
 » 6 years ago, # |   +10 Hope no FST, and be red after this round. :D
•  » » 6 years ago, # ^ |   +3 Congrats for being RED :)
•  » » » 6 years ago, # ^ |   0 Thank you.
•  » » 6 years ago, # ^ |   0 & whats fst?
•  » » » 6 years ago, # ^ |   0 It's Failure System Test.
 » 6 years ago, # |   +11 Wow, so many Runtime Errors in final testing for Div1 B. Even Egor failed this problem.
 » 6 years ago, # | ← Rev. 2 →   0 Almost everyone who solved problem Div-1 A did binary search, this is my accepted solution: 4576049It's just O(1) (after reading the input), to be honest I couldn't prove if this solution is correct or not. Can anyone check it please and tell me why it's correct? Or are the test cases weak?
•  » » 6 years ago, # ^ | ← Rev. 4 →   0 I can prove only that it is correct — my O(1) solution passed. Proving correctness is harder.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 http://codeforces.com/contest/348/submission/4576666nearly same compared to you
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 answer >= max(a[i]) and the second inequality is your binary search's inequality. Solve this system and be happy :)
•  » » 6 years ago, # ^ |   0 Can you please explain how you applied Binary Search on this problem? I really want to know, because I could just think of brute-forcing it.
•  » » » 6 years ago, # ^ |   0 You must chhose number of game — m, then check, than all in array <= m and that free players more that m(for arbiter). http://codeforces.ru/contest/349/submission/4581586
•  » » 6 years ago, # ^ |   +11 It's easy to see. Let the answer be K. So the first person can be supervisor in (k — a[0]) games, the second in (k — a[1]) games and so on. So (N * k — sum(a[i])) games there is a supervisor. It must be bigger or equal than K cause there were K games. N * K — sum(a[i]) >= K. K * (N — 1) >= sum(a[i]). And we didn't mentioned that K >= max(a[i]) (that's obvious). So the answer is MAX(MAX([i]), sum(a[i]) / (N — 1));
•  » » » 4 years ago, # ^ |   0 i couldnt get why N * K — sum(a[i]) >= K.
•  » » 6 years ago, # ^ |   +10 It is obviously correct. Let xi be the number of rounds skipped by i'th person, . We need xi ≥ 0, X - xi ≥ ai, so xi ≤ X - ai. Summing up, . Consider arbitrary X such that this statement is true. Then you can take xi = X - ai - αi, so that αi ≥ 0, . Since right side expression is  ≥ 0, such αi exist, this finishes the proof.
 » 6 years ago, # |   0 Really intresting problems. I liked all of them , especially D form Div1. I think these were very original problems. Congrats to the authors ! Thank you , you made my day ! :DBtw, can someone explain how to do B-div1 & D-div1.
•  » » 6 years ago, # ^ |   +38 Actually D is just a quite straightforward application of this theorem: http://en.wikipedia.org/wiki/Lindstr%C3%B6m%E2%80%93Gessel%E2%80%93Viennot_lemma
•  » » » 6 years ago, # ^ |   +34 Moreover, searching for number of tuples of nonintersecting paths, we can see this article as second link in Google.
•  » » » » 6 years ago, # ^ |   +49 This theorem was used in recent Japanese competition.
 » 6 years ago, # |   0 When will ratings be updated?
 » 6 years ago, # |   0 Can someone please gives some idea about DIV2 C?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 we can solve it by making an equation like this : ans ==> the answer/minimum game must be make(ans-a1) + (ans-a2) + ... + (ans-an) >= ans (the sum of all players become supervisor must be greater or equal than the minimum game)in short we can found ans >= ((a1+a2+...+an) / (n-1))but only by that it'll be failed in test case when there are some players that didn't need to be supervisor at all (in example case : 8 4 4 4 4 1 1 1 1 should output 4 instead 3) so the answer become max(ans,max_game_player_needed) hope it help :D pls correct me if im wrong
 » 6 years ago, # |   0 Awesome problem-set..!!Waiting to know solution of D div.2
 » 6 years ago, # | ← Rev. 2 →   0 deleted!
•  » » 6 years ago, # ^ |   +4 else if (y > 2) { y-=3; }must be else if (x > 2) { x-=3; }
 » 6 years ago, # | ← Rev. 2 →   0 Hi there! :) I submitted my B problem's solution in the contest, and the checker gave wrong answer; but in my PC and in even in the custom test, it gives the right answer! Even I submitted it after the contest, but it gave wrong answer too. Here's my submission. Can anybody give any reasons for this? I would be happy if Codeforces moderators could explain this. Thanks! :D
•  » » 6 years ago, # ^ |   +4 Sorry, I found my mistake :D
 » 6 years ago, # |   0 Did anyone in Division 2 exceed memory with a DP on Problem B? I haven no idea what happened on mine. :O
•  » » 6 years ago, # ^ |   +6 You are using a String array of size 10^6 , so it is so obvious the reason why
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 You have to generate the result, instead of storing the result in a string array. Hope that helps
 » 6 years ago, # |   +2 I'm in div 1 now
 » 6 years ago, # |   +4 Can anyone help me with Div.2 Prob. A ? Link : http://ideone.com/b0HLLwIt shows WA on test case 12. Please help. Thanks.
•  » » 6 years ago, # ^ |   +5 It looks like you totally misunderstood main problem statement or solution idea. ;-)
•  » » » 6 years ago, # ^ |   +5 Please correct me if I am wrong. With taking input, I am checking whether the desired change is available or not. If true, I am adding 25 to the counter, else , I am printing "NO";
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Your code is wrong with case like:725 25 25 50 50 50 100Answer should be "NO".
•  » » » » » 6 years ago, # ^ |   +6 Thanks to all for replying. I got my mistake. The shopkeeper can only give change with the help of those bills which he has got from previous transactions i.e; by using 25, 50 or 100 bills.
 » 6 years ago, # |   0 Hi everyone!My solution for Div1 B failed on final test 32, and it cannot be viewed completely under the submission. Does anyone know what final test 32 for Div1 B is?Thanks!
•  » » 6 years ago, # ^ |   0 I do not know about test case #32. However, there goes a common mistake that lcm exceeds "long long" range, which may be divulged under a huge input, but you can pass through the pretest with the mistake.
 » 6 years ago, # |   0 I was hoping that there would be at least one Big Lebowski fan around here, so I introduced few references into the problem statement. Hope you enjoyed the round :)
 » 6 years ago, # |   -8 Could someone explain why this submission has became tl? It's a simple greedy that a lot of people have got accepted with this method. http://codeforces.com/contest/349/submission/4581168 Thanks.
•  » » 6 years ago, # ^ |   +5 for(int j = 8; i >= 0; j--) ...
 » 6 years ago, # | ← Rev. 3 →   -15 problem with problem B DIV 2.
 » 6 years ago, # |   +10 Where are you, editorial?
 » 6 years ago, # |   +1 This question is a bit difficult to read
 » 6 years ago, # |   +5 oh man i forgot it yesterday
 » 6 years ago, # |   0 div 1 problem is really challenge for me, i wonder where is the tutorial?
 » 6 years ago, # |   +15 When will the Editorial come? Can't Wait to see it for Div. 1 B...
 » 6 years ago, # |   +9 Problem B is unpleasantly similar to 2012/13 Czech/Slovak Olympiad in Informatics (these 2 share the problems and are held at the same time), Regional round, problem 2. The only difference is that we had a binary tree in that problem. The general one needs extending the idea and there is a lot of possible overflow to take care of (since that problem was theoretical), but I feel that it helped me get a better result.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Hey Xellos, I like a lot your way of explaining problems ideas, so could you give a short description for Div2 problems. A sort of short tutorial :)
•  » » » 6 years ago, # ^ |   0 I would, but I still haven't solved Cdiv1, and I kinda don't want to make an actual editorial if I'm not the author. If it doesn't appear in several days and I solve the rest of the problems, I might post one instead.
 » 6 years ago, # |   +17
•  » » 6 years ago, # ^ |   +3 thanks a lot Egor! i really enjoyed watching this!can u continue to make screencasts for future contests? thanks in advance! :)
 » 6 years ago, # |   0 For Div-2 B my approach, Find the minimum d ( minimum amount which takes to paint a digit with highest index) and divide the total paint by min d. This number gives total no of digits which can be painted. i.e. the answer will have this many digits. Now only thing you can do is, if there is still left over paint ( total paint — paint used upto this point ), you can improve, in the sense you can replace already used digit and left over paint with a higher digit by using greedy method. Repeat the improvement until you have some left over paint and there is a digit with higher index which you can replace. My Solution
 » 6 years ago, # |   0 Still no editorial :/
 » 6 years ago, # |   +2 Editorial, where are you?
 » 6 years ago, # |   -6 Editorial Please ??!!
 » 6 years ago, # |   -16 Please post the editorial for div. 1!!!
 » 6 years ago, # |   -9 Please post the editorial for div 2
 » 6 years ago, # |   +3 Thanks for the contest! Won't there be an Editorial?!
 » 6 years ago, # |   0 Thanks for the editorial too.
 » 6 years ago, # |   +5 Hi! Does anyone of you know an approach to solve Div1 C problem? I'm very curious about its solution.
•  » » 6 years ago, # ^ |   +6 Thanks to SillyHook06, whose superb contest submission helped me solve this awesome problem !! The essential idea is to bifurcate all given sets as big and small: Let us denote by T the collection of all big sets [those sets which have size >= sqrt(n)] and by S the collection of all small sets [those sets which have size < sqrt(n)]. What remains is to exploit the following two properties: 1) Each element of S contains atmost sqrt(n) elements. 2) The total number of elements in T is atmost sqrt(n). To do this, one can precompute for each big set, the sizes of its intersections with all other sets. Precomputation takes O(n*sqrt(n)) and processing each query takes O(sqrt(n)). I find it difficult to state all details in a short post. Here is my practice submission (with a few comments): 4607191
•  » » » 6 years ago, # ^ |   +5 Big thanks for your reply :)
•  » » » 6 years ago, # ^ |   +1 I will attempt to briefly explain the query processing: a[i] stores the current value at position i considering only the updates on small sets. (eg: The initial array is all zeroes. Big set #0 and small set #1 both contain the index 3. Set #0 is updated with 4 and set #1 with 7, then a[3]=7) ct[i] stores the total update value on big set i (eg: if set #2 is a big set and is updated thrice with values 2,6,3 then ct[2] is 11). sum[i] stores the current result of big set i considering only the updates on small sets (eg: The initial array is all zeroes. Set#0 is big and set #1 is small. The intersection of these sets is of size 2. Set #0 has been updated twice with 3,4 and set #1 once with 5. Then sum[0] will store 10, ignoring all the updates on all big sets including itself.) Update a small set X: Update a for all elements of X, sum for all big sets. Update a large set X: Update ct(X). Query a small set X: Sum up a values of elements in X. Add to this the sum of ct(Y)*|intersection(X,Y)| over all big sets Y. Query a large set X: Sum up ct(Y)*|intersection(X,Y)| over all big sets Y. Add to this sum(X).
 » 6 years ago, # |   0 Can someone tell me how to solve div1 B and div1 C? I have no idea.
•  » » 6 years ago, # ^ |   0 How about reading the comment just above for div1 C before you ask?div1 B: DFS the tree; the sum in a subtree of vertex i must be a multiple of some number M[i]; then, M[i]=LCM(M[all sons])*(number of sons of i), find the largest sum in subtree of a son satisfying that. Watch out for long long overflow.
•  » » » 6 years ago, # ^ |   +3 I am sorry I haven't seen the previous comment.Thanks for your reply :)
 » 6 years ago, # |   0 I hope someone can translate the editorial into English ! Thanks.
•  » » 6 years ago, # ^ |   0 Well, I have found the entry for English version. It may help me a lot.
•  » » » 6 years ago, # ^ |   +1 Can you give the link for the English Editorial??
•  » » » » 6 years ago, # ^ |   +1 You can check here :)
•  » » » » » 6 years ago, # ^ |   0 Thanks mate