Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### komendart's blog

By komendart, history, 4 years ago, translation, ,

Hello, everyone!

Codeforces Round #353 (Div. 2) will take place tomorrow on the 16th of May at 19:35 MSK. I tried to make interesting problems, hope you enjoy them.

I'd like to thank GlebsHP for his help in preparing problems and MikeMirzayanov for Codeforces and Polygon.

Good luck!

UPD Scoring 500-1000-1500-2000-2500

UPD Editorial

UPD Congratulations to winners!

Div. 2

Div. 1

• +363

 » 4 years ago, # |   +34 Good luck and have fun
•  » » 4 years ago, # ^ |   -6 haha good luck
•  » » » 4 years ago, # ^ |   -17 DIV 2冠军就是我!!!!!!!!!!!!!!!!!战斗吧jibancanyang
•  » » 4 years ago, # ^ |   +3 i'm looking forward to join contest . i hope i will be succesfull
•  » » 4 years ago, # ^ |   0 Yes, I'm agree
•  » » » 4 years ago, # ^ |   +52 Hello agree
•  » » » » 4 years ago, # ^ |   +4 Nice reply :)
•  » » » » 4 years ago, # ^ |   0 :)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -7 1
 » 4 years ago, # |   -210 Is it rated?First!!!
•  » » 4 years ago, # ^ |   +135 My congratulations!
•  » » 4 years ago, # ^ |   +12 finally ,there he is
•  » » 4 years ago, # ^ |   -41 مبروك
•  » » » 4 years ago, # ^ |   +45 Can you speak english? PLS!
•  » » » » 4 years ago, # ^ |   -46 write to google translate and learn it
•  » » » » 4 years ago, # ^ |   +39 مبروك :P
•  » » » » » 4 years ago, # ^ |   -18 "Congratulations" (Google Translate)
•  » » » » » » 4 years ago, # ^ |   -20 I can write in a language that you do not translate into google translate (-_^)
•  » » » » » » » 4 years ago, # ^ |   +43 Congratulations,you must be a real genius.You can write in a language that google translate cant translate.
•  » » » » » » » » 4 years ago, # ^ |   +1 karekterli I مبروك you
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Hazillashmudim! (It means "i didn't joke")
•  » » » » » » » » 4 years ago, # ^ |   +9 Haha!
•  » » » » » » » » 4 years ago, # ^ |   +21 ()
•  » » » » » » » » » 4 years ago, # ^ |   +14 :)
•  » » » » » » » » » 4 years ago, # ^ |   0 wrong answer :) But very near!
•  » » 4 years ago, # ^ |   +6 What does rated mean? Excuse me but I'm new to this website.
•  » » » 4 years ago, # ^ |   +9 Welcome the CodeForces!
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +7 It means that you get positive or negative points depending upon your performance in the contest and your rank changes to Newbie, Pupil, Master, Grand Master ... etcCurrently you're unrated, when you participate for the first time your score is assumed to be 1500, and the points you earn will be added to itLater contests will add to your actual score
•  » » » » 4 years ago, # ^ |   0 OK I got it. Thank you :)
•  » » 4 years ago, # ^ |   0 seems like no one likes you Mr Tweety :3
 » 4 years ago, # |   +11 wow. short and good description. hope to see some interesting problems :)
 » 4 years ago, # |   +16 The least words with the most clarity is the best form of expression.
 » 4 years ago, # |   -36 Good Luck... We hopefully, we will enjoy this Round..
 » 4 years ago, # |   0 komendart and his short announcements
 » 4 years ago, # |   -110 Will Codeforces Round 366 (Div 2) be yours?)
•  » » 4 years ago, # ^ |   -112 Stop downvoting! I don't want to have negative contribution.
•  » » » 4 years ago, # ^ |   +49 You don't want, but you will have.
 » 4 years ago, # | ← Rev. 2 →   -63 .
•  » » 4 years ago, # ^ |   +12 What is misleading about his response?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -20 .
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   -13 deleted
•  » » » » 4 years ago, # ^ |   +17 He said that for a valid solution, there has to be at least one nut. This means that if there is no nut, there is no solution. It doesn't mean it is guaranteed that there is at least one nut. His response was clear, so you should blame yourself for misunderstanding what he said. :)
•  » » 4 years ago, # ^ |   +12 "Please note, that if Bob doesn't make any breaks, all the bar will form one piece and it still has to have exactly one nut."I don't find it misleading. This sentence means that it's invalid way if we don't make any breaks and bar hasn't nuts. And this sentence would be excess if it was guaranteed that bar has at least one nut.Everyone who asked similar question got this sentence as response. By the way, it can be with the same probability my or GlebsHP's response.
•  » » 4 years ago, # ^ |   0 I also failed system tests because I was mislead by the exact same answer you got. I'm still not quite sure what I think about it, it would've been easy enough to just answer yes or no to the question, since people were confused and asking directly, but I guess I just also learnt from it, and from now on will always include an if statement for special case like that if I'm in doubt whether it's in the test cases or not.
 » 4 years ago, # |   +26 Best Wishes to All World Final teams. Hope this contest will be warm-up contest for Them.
 » 4 years ago, # |   0 Simple and clean description :)
 » 4 years ago, # |   +1 I really enjoyed your last contest! Thanks for setting this contest.
 » 4 years ago, # |   +1 Hope for doing much better.
•  » » 4 years ago, # ^ |   0 I hope so too
 » 4 years ago, # |   -11 As the description is short and simple , so I think the problem will become very short and simple :)
 » 4 years ago, # |   +16 my first time here , hope to see some interesting problems
•  » » 4 years ago, # ^ |   +5 I hope you will be successful in this contest
 » 4 years ago, # |   -68 Give me Downvote.........
•  » » 4 years ago, # ^ |   +4 Here you go!
 » 4 years ago, # |   +15 Hope to pass Div2/C for first time :)
•  » » 4 years ago, # ^ |   0 The same thing. Never passed it before :D
 » 4 years ago, # |   0 Interesting...
 » 4 years ago, # |   +88 I don't have internet connection and electricity in my house, had to travel to another city 3 hours away because of contest. Hope the problems are really interesting please.
•  » » 4 years ago, # ^ |   -24 You must be really excited about Codeforces :)It's only a minor contest for most people
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +10 If it's minor contest for you, keep it to yourself. Do not discourage others by posting such illiterate statements. It's major contest for all Div 2 contestants who have a chance to increase their rating and eventually end up in Div one one fine day after performing well. !
•  » » » » 4 years ago, # ^ |   +7 How can he be so neglectful...
•  » » » 4 years ago, # ^ |   +22 Well, I'm sorry you feel this way. But codeforces is more than a minor contest. It is a community of dedicated and hard working programmers some of which work for some of the best companies in the world.Before joining codeforces, I had did not know about many concepts in programming but thanks to codeforces I now do and am learning and improving daily.I made a lot of cool friends here on codeforces and have even been contacted a recruiter through due to my blogging about codeforces.So no its not just a minor contest for me. It is a chance to train with different programmers from all around the world and enjoy doing it at the same time.Thank you.
•  » » » 4 years ago, # ^ |   -7 šupak(azzhole)
 » 4 years ago, # |   +10 What is the most important of it? "Interesting!" I hope I can enjoy it with my friends then, though I am a green hand.
 » 4 years ago, # |   +3 Nice and short announcement....fine. :-)Hope , closing ceremony time will also be as short as the announcement ...... plz
 » 4 years ago, # |   0 We will rise !
 » 4 years ago, # |   +3 Auto comment: topic has been updated by komendart (previous revision, new revision, compare).
 » 4 years ago, # |   +10 My first contest. Feeling Exticed
 » 4 years ago, # |   0 I think one of the problems is about shortest statement :D Have a nice contest ;)
 » 4 years ago, # |   -22 The comment removed because of Codeforces rules violation
 » 4 years ago, # |   +48 Scoring should be 500-1000-25000-500-2500 :)
•  » » 4 years ago, # ^ |   +2 500 — 1000 — 2500 — 1500 — 2500
•  » » 4 years ago, # ^ |   0 I think it depends on perspective. I took 18 minutes to solve C, but 50 minutes to solve D. Mainly due to my inexperience with STL. While the idea for C is a bit less intuitive than D, the implementation is relatively more simple.
 » 4 years ago, # |   +38 How to solve problem C ?
•  » » 4 years ago, # ^ |   +32 Let us note by T[i] the transfer from i to i + 1 in some solution. Then the following equations must be satisfied: A[i] + T[i - 1] - T[i] = 0. for i = 0, 1, ..., n - 1. Suppose that we know T[0] = x then T[i] = A[i] + A[i - 1] + ... + A[1] + x.We can manipulate x and we want the maximum possible number of T[i] to be 0. The best choice for x is the opossite of the most frequent number in the pref_sum table.So the answer is n - k where k is the frequency of the most frequent number in the sequence A[1], A[1] + A[2], ..., A[1] + A[2] + ... + A[n].
•  » » » 4 years ago, # ^ |   0 Wow! Nice solution!
•  » » » 4 years ago, # ^ |   0 What's the value of T[i]? what does transfer from _i_ to _i+1_ in some solution mean?
 » 4 years ago, # |   0 How to solve C? I was finding maximum consecutive zeros(taking circular queue in consideration) and then subtracting it from n — 1. It gave WA on pretest 5.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +4 incorect:90 0 0 0 1 -1 0 1 -1correct ans: 2your ans: 4
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 i looked for consecutive zeroes that have the same prefix sum and got the best score from: n — number of zeroes with that prefix — number of consecutive intervals. Didn't work, but it does work on this test :(.
•  » » » » 4 years ago, # ^ |   0 cycle array is given. Did you count it?
•  » » 4 years ago, # ^ |   0 consider all zeroes
•  » » 4 years ago, # ^ |   0 test:1 -1 0 0 1 -1 0 0 0answer is 2
•  » » 4 years ago, # ^ |   0 Did you see that it was a circular array? :)
•  » » 4 years ago, # ^ |   +4 Well, I passed pretest, though I don't know if my answer is correct or not. Here, at first we take cumulative sum in another array, say, cum[i], where cum[i]=summation of initial array from 1 to i. Then, we check for the number which has maximum occurence in the cumulative array.Let the number of times it has occured be max. The answer is n-max.
•  » » 4 years ago, # ^ |   0 same here!
 » 4 years ago, # |   0 what is 4th input in E?
•  » » 4 years ago, # ^ |   +20 We know as much as you!
 » 4 years ago, # |   0 I'm wondering if there is something very simple we can do for C, or if it was truly as hard as it seemed. Harder than D anyway.
 » 4 years ago, # |   +70 My heart was broken. Unsuccessful hacking attempt -50
•  » » 4 years ago, # ^ |   +28 Welcome to Codeforces, land of the trolls.
 » 4 years ago, # |   0 Very nice problem set!!
 » 4 years ago, # |   0 Auto comment: topic has been updated by komendart (previous revision, new revision, compare).
 » 4 years ago, # |   0 Wow system testing started just after the contest finished! so fast! wonderful! :)
 » 4 years ago, # |   0 why I am always forgetting to use long long :'(
•  » » 4 years ago, # ^ |   +6 You maybe are so excited that you have found the solution, that you don't think about tricky test cases. You just go strait into the code. It's a common mistake. Just make sure you spend 10 seconds thinking about data types that you are going to use in your code when you solve a problem. Spending very little time double-checking your solution is worth getting wrong answer, specially in CF that tricky test cases are not usually included in pretests.
 » 4 years ago, # |   0 I'm curious, as to what your strategies were for C. D seemed more straightforward but C was so interesting I couldn't leave! Mine assumed that there are four optimal starting positions, and I just looped manually. Most likely my assumption is false; anyway what were your ideas?
 » 4 years ago, # | ← Rev. 2 →   0 I am getting Time limit exceeded on Pretest 6 on Problem D although my approach is nlogn: http://codeforces.com/submissions/Ishan.nitj
•  » » 4 years ago, # ^ |   +3 Your solution is N^2 in worst case (e.g. sequence 1 2 3 4 5 ... N)
•  » » » 4 years ago, # ^ |   +3 thnks
 » 4 years ago, # |   0 Very nice contest, the problems were great, especially problem D. I don't know if I have the right solution though (I didn't send a source :( ), I have a solution involving Segment Trees with Lazy Propagation. What was your solution to D?
 » 4 years ago, # |   0 Hacked 3 times in Div2 A by the same guy... really? Link
•  » » 4 years ago, # ^ |   +12 :'( It was my fault -_-
 » 4 years ago, # |   0 How to solve D at all? Treap? How to build BST in O(N)? Or some kind of completely another solution?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +4 No treapmake map of intervals (l; r) -> value at parent list. Initial (0 10^9 + 1) -> -1; 1) read num a;2) find interval (l; r) -> ans for which: l < a < r;3) if ans > 0 print ans;4) add interval (l; a) -> a and (a; r) -> a
•  » » 4 years ago, # ^ |   +10 Suppose you're adding x. Find a = smallest number bigger than x, b = biggest number smaller than x (between numbers added until now). Now the answer is the one (of a and b) that was added more recently. You can find a and b with a set.
 » 4 years ago, # |   +15 System testing was very fast !!!
•  » » 4 years ago, # ^ |   +7 Yes, the bad news come very fast :P
 » 4 years ago, # |   0 Time complexity for 10^9 passed in codeforces judge when I tried to hack the solution in problem A by giving a=1,b=1000000000,c=1 his code was if(c>0){ while(a
•  » » 4 years ago, # ^ |   +3 on servers 10^9 fast operations go for ~0.8 seconds
•  » » 4 years ago, # ^ |   0 I also hacked a solution for TLE, but before doing so I used the Custom Test Tab and saw, that 1 1000000000 1 gives Used: 561 ms, 2036 KB, whereas -1000000000 1000000000 1 gives Used: 1123 ms, 2036 KB and since time limit was 1 second, just the larger test case is valid for a hack.
 » 4 years ago, # |   +4 Problem C looks very similar to SRM683 Div1 Easy, O(n) Solution for that problem can be found here. The solution for this problem is also similar
 » 4 years ago, # | ← Rev. 6 →   +10 Problem D was minor change from a recent HackerRank contest problem, which in turn also appeared in India IOITC 2015 Test 1, and also in some iteration of the COCI(saw it on PEG Judge, not sure which olympiad).EDIT:COCI, not CCC, my bad.
 » 4 years ago, # |   -6 Is the contest unrated or we just have to wait some time for the system to update?
 » 4 years ago, # | ← Rev. 2 →   0 Why does this code doesn't give RE on 10 10 0?
•  » » 4 years ago, # ^ |   0 Division by zero (temp % c)
•  » » 4 years ago, # ^ |   0 Maybe after seeing that temp is zero (temp%c), the rest is ignored, in the same way while(!q.empty() && q.front()==0) doesn't give RTE because if q.empty() is true, the check q.front()==0 is ignored :)
•  » » » 4 years ago, # ^ |   0 But it doesn't give RE on test 0 1 0 also!
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 You may not write ( number % zero )
 » 4 years ago, # | ← Rev. 2 →   0 I tried to hack but couldn't because this feature needed flash player. Seriously? Who uses flash player anymore?? Other than that very nice contest. The problems were challenging, and I really enjoyed it although I didn't have time to even read E :D
 » 4 years ago, # |   0 Is the contest rated or unrated
•  » » 4 years ago, # ^ |   0 It is rated. I think they are finding the cheaters, my rank just decreased by 2.
 » 4 years ago, # |   +1 My hacking attempt on http://codeforces.com/contest/675/submission/17938245 failed for testcase 1 1000000000 1 because the solution produced correct answer in 826ms. So close but yet so far. -1000000000 1000000000 1 took 1450ms. Should have tried the largest testcase.
 » 4 years ago, # |   0 When do colors change?
•  » » 4 years ago, # ^ |   0 It's already done
 » 4 years ago, # |   0 Hi Friends I am sure this a trivial question, but it would be really nice if someone could look into this. I gave these two submissions 17956219 and 17953624 for problem B div 2. Both are identical except using long long and long data type. But the solution with long gave wrong answer for 100000 2 2 2 2 Output 1410065408 Answer 10000000000 What could be the reason for this?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 long = from -2 147 483 648 to 2 147 483 647 long long = from -9 223 372 036 854 775 808 to 9 223 372 036 854 775 807 I made one hack using this
•  » » 4 years ago, # ^ |   0 Overflow is the reason. The answer may be 10**10 if sum=10*5 and the number of number that can be used is 10*5. Long data type stores 4 bytes of data whereas long long data type stores 8 bytes of data and 10**10 doesnt lie in the range of long data type. Thus an overflow occured and thus your answer was wrong.
•  » » 4 years ago, # ^ |   0 the variable is long long ，but you define int.
 » 4 years ago, # |   0 What a TLE! I used the generic upper_bound instead of the class specific 17957229 vs 17957298To have into account in future implementations.
•  » » 4 years ago, # ^ |   0 Generic upper_bound on non sorted random access containers takes O(n) time. Protip: google C++ upper_bound.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +3 Yes. In fact I found that reason after google a little bit, then I corrected it. I wasn't aware of that.
 » 4 years ago, # | ← Rev. 2 →   0 why in the result table some cells have a color background? http://prntscr.com/b4vv80
•  » » 4 years ago, # ^ |   0 and others are red http://prntscr.com/b4vw4r
•  » » » 4 years ago, # ^ |   +3 Because. You was be in the same room with them and you looked their solutions to hack. So green color shows that you look this solution and maybe red color means that it is the last solution you check for hacking.
•  » » » » 4 years ago, # ^ |   0 Yes, I check and they are both at the same room with me. Looks like you're right, thanks!
 » 4 years ago, # |   +12 Thanks a lot for your efforts and interesting problems :)
 » 4 years ago, # | ← Rev. 2 →   0 Why ALL my AC code was skipped?The solution gets accepted after resubmitting! Since I didn't use other accounts to submit the same solution or copy others code, how can I ask to retest my code.
 » 4 years ago, # |   +3
 » 4 years ago, # |   0 Great DP in Problem E. It makes proper use of Greedy Algorithm!
 » 4 years ago, # |   +3 A splendid round!!!But why not have some weekend round like before?It's really difficult for those students in other regions to get up after 12 during workdays.All in all,just suggestions.
 » 4 years ago, # |   0 Can someone tell me why using array to build BST causes Runtime Error?I feel a little confused,and my submission was hereI watch others code which use the similar way and find that they also got RE in test4input:10 991309218 517452607 870021923 978357992 136426010 10601767 302627526 883615372 163475700 600546765`
•  » » 4 years ago, # ^ |   +3 Eh, I have not studied BST nicely(one more reason to concentrate in classes :P) but I think you are trying to make a tree using array which will require 2^n space(here n<=100000).
 » 4 years ago, # |   +8 The use of unordered_map in problem C leads to a TLE . Why is that ?
•  » » 4 years ago, # ^ |   +3 Hashmaps have the worst case runtime of O(n) when elements get hashed to the same value multiple times.
 » 4 years ago, # |   0 Please post the Editorial.
•  » » 4 years ago, # ^ |   0 Look at the post) http://codeforces.com/blog/entry/44902