### RetiredAmrMahmoud's blog

By RetiredAmrMahmoud, 7 years ago,

Hello Codeforces!

I'd like to invite you to Codeforces Round #312 (Div. 2). It'll be held on Tuesday, July 14th at 18:00 MSK.(notice the unusual starting time) and as usual Div. 1 participants can take part out of competition.

This is my second round after Codeforces Round #287 (Div. 2). :)

Great thanks to Maxim Akhmedov (Zlobober) for his great help in preparing the contest, Maria Belova (Delinur) for translating the statements into Russian, Mike Mirzayanov (MikeMirzayanov) for the great Polygon platform and Polygon's developers team for their hard work in enhancing Polygon system.

The scoring distribution will be announced later.

Good luck everyone and I hope you'll find the problems interesting. ;)

UPD1 Scoring distribution will be 500-1000-1500-2250-2500.

UPD2 Contest is delayed 10 mins. Sorry for inconvenience.

UPD3 Contest is finished. Thank you everyone!

UPD4 System testing finished. Congratulations to the winners.

You can find the editorial here.

• +288

 » 7 years ago, # | ← Rev. 2 →   +17 So Few Contest Now a Days. Hope this Contest Will love Everyone .
•  » » 7 years ago, # ^ |   +172
 » 7 years ago, # |   +21 your problems in last contest were awesome
•  » » 7 years ago, # ^ |   +6 Why? cause they were easy?
•  » » » 7 years ago, # ^ |   -10 Easy, but interesting ideas. :D
 » 7 years ago, # |   -10 I wish good luck and good scoring for everyone. :)
 » 7 years ago, # |   -7 The first round was awesome :)
 » 7 years ago, # |   -14 contest is coming :) finally !!!
•  » » 7 years ago, # ^ |   +1 You should brace yourself after contest, when system testing starts. But before just enjoy the contest
 » 7 years ago, # |   +23 I'm waiting for another fight in comments under blog... ^_^
•  » » 7 years ago, # ^ |   0 I think one is about to start http://codeforces.com/blog/entry/19173?#comment-240780
 » 7 years ago, # |   +49 Why no div1 :/
•  » » 7 years ago, # ^ |   -16 because no problems setters :/
 » 7 years ago, # |   -6 This is my second contest here at codeforces. I should see how I am going to perform
•  » » 7 years ago, # ^ | ← Rev. 2 →   -26 OK. I'll tell him.
 » 7 years ago, # | ← Rev. 2 →   0 Yeah !!!
 » 7 years ago, # |   0 finally new contest...
 » 7 years ago, # |   +49  Thank you AmrMahmoud. Eagerly Waiting for your interesting problems... ☺ 
 » 7 years ago, # |   -7 Чувствую будет классный контест!
•  » » 7 years ago, # ^ |   +10 Yes Yes...You're right :|
•  » » 7 years ago, # ^ |   0 -
 » 7 years ago, # |   -51 I wish you all good luck, but the 1st place is for me!!!!!!
•  » » 7 years ago, # ^ |   +34 It's not funny nor interesting to participate in a div2 contest and solve all problems and prove yourself, do that in div1!!
•  » » » 7 years ago, # ^ |   +5 yea this is getting pretty ridiculous.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +5 Bro, who cares about that? Do your best work and that's it!!!
•  » » 7 years ago, # ^ |   0 good luck!
 » 7 years ago, # |   0 after a long time :/ .hope contest's will be frequent as before.it's interesting .....
 » 7 years ago, # |   0 Why new rounds start at an unusual time?
 » 7 years ago, # |   +7 contest after two long week , hope short and simple problem description with explanation of test cases :)
•  » » 7 years ago, # ^ |   0 Agree with short problems not like this :|||
•  » » » 7 years ago, # ^ |   +12 I'm still a noob but I feel as if how long a description is should not be very imporant. Although I do think the Clarity of the statement is very important.
 » 7 years ago, # |   0 I thought it'd be nice to participate in contest who put it egyptian coder :)
 » 7 years ago, # |   +58 we want div.1 contests
 » 7 years ago, # | ← Rev. 2 →   +4 after long waiting! finally we have contest
 » 7 years ago, # |   0 Will the scoring be dynamic?
•  » » 7 years ago, # ^ |   +2 Scoring is not published yet.
•  » » 7 years ago, # ^ |   0 I think they just write "The scoring distribution will be announced later" and then they forgot to announce :/
•  » » 7 years ago, # ^ |   0 Why they do not decide their scoring system and then post? ;(
•  » » » 7 years ago, # ^ |   +10 Do you think that it's easy to determine the difficulty of the problems?
•  » » » » 7 years ago, # ^ |   0 What is the relation between difficulty of the problems and scoring system ?
•  » » » » 7 years ago, # ^ |   +13 It's not easy, but I don't understand why authors always publish the scoring 5 minutes before the start of the contest? why not sooner?
 » 7 years ago, # |   +5 Writing from Japan this time round ... where are you all writing from? :)
•  » » 7 years ago, # ^ |   -7 Bangladesh :)
•  » » 7 years ago, # ^ |   +5 i am writing from my home. (my home is in iran btw xD)
•  » » » 7 years ago, # ^ |   -9 i am writing from your home too
•  » » » » 7 years ago, # ^ |   0 Hey... i thought i didn't give you internet :|
•  » » » » » 7 years ago, # ^ |   0 but she gave me . you know her ;)
•  » » » » » » 7 years ago, # ^ |   +13 -.-' i didn't give your sister any internet either
•  » » » » » » » 7 years ago, # ^ |   +1 dont be rude :((
•  » » » » » » » » 7 years ago, # ^ |   0 please stop annoying me man -.-' you fight with me on different accounts xD and its really annoying
•  » » » » » » » » » 7 years ago, # ^ |   0 I dont have multi accounts like you :D ( Bell-sama )
•  » » » » » » » » » 7 years ago, # ^ |   +9 Oh...I missed the fight :/
•  » » » » » » » » » 7 years ago, # ^ |   0 are you sure he is bell sama?
•  » » 7 years ago, # ^ |   +1 russia, siberia, yakutsk.
•  » » 7 years ago, # ^ |   0 It's Syria :D
•  » » 7 years ago, # ^ |   +2 US, from work, lol!
 » 7 years ago, # | ← Rev. 2 →   +5 Rise of unrated s !!!
•  » » 7 years ago, # ^ |   +11 Your picture is very good ;)
•  » » » 7 years ago, # ^ |   0 so his/her user name :D
 » 7 years ago, # |   +3 Delayed...
 » 7 years ago, # |   0 Delayed again!
•  » » 7 years ago, # ^ |   0 It has become daily(contest) routine for CF :(
•  » » » 7 years ago, # ^ |   +7 CF doesn't have contests every day...
 » 7 years ago, # |   0 Delay again! Unhappy( ˇˍˇ )
 » 7 years ago, # |   0 10 min delay again !!
•  » » 7 years ago, # ^ |   0 Very original post http://codeforces.com/blog/entry/18896#comment-238419
•  » » » 7 years ago, # ^ |   0 IKR
 » 7 years ago, # |   0 Thanks for delaying! Only now I am online :} .
 » 7 years ago, # | ← Rev. 2 →   +17 UPD
 » 7 years ago, # | ← Rev. 2 →   0 The comment is hidden because of too negative feedback, click here to view it.
•  » » 7 years ago, # ^ |   0 Very funny -_-
 » 7 years ago, # |   +2 Thanks for delay. If there is no delay, I could not register.
•  » » 7 years ago, # ^ |   0 Haha, me too, registered in the last 30 seconds.
 » 7 years ago, # |   +9 It will be my first online round on CF, so I wish that it wouldnt be so bad... Good luck!
 » 7 years ago, # |   0 good luck everyone
•  » » 7 years ago, # ^ |   0 Thanks.
 » 7 years ago, # |   +7 More than three years ago, in April 2012, the same problem as E was created on my polygon account...
 » 7 years ago, # |   -43 НАСКОЛЬКО же уёбищный контест.
•  » » 7 years ago, # ^ |   +4 Бомбит ? ))
 » 7 years ago, # |   +3 What is pretest 4 in problem B? How to solve C?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +12 C. We need to make all numbers to be equal to some FIXED value. FIXED is always <= max(a[1..n]). We can get only log^2(x) unique states from some number x, by dividing and multiplying it by two. Summary O(N * log^2(x))
•  » » » 7 years ago, # ^ |   0 Same logic, but didn't submit
•  » » » 7 years ago, # ^ |   0 Why FIXED is always <= max(a[1..n]) ? Thanks in advance!
•  » » » » 7 years ago, # ^ |   +3 If FIXED is bigger than maximum, then last operation for all numbers is multiply, so we can just divide all numbers.
•  » » » 7 years ago, # ^ |   +4 You get log^2 states for some number, but how for any other number you calculate the minimum number of ops to get to a particular state? I mean the straightforward approach is log^4 which is obviously TL, I used some sorting on log^2 (so O(log^2 * loglog)) and it also TL'ed — on my laptop it was 1.6 sec on max test.
•  » » » » 7 years ago, # ^ |   0 I have array cnt[] and sum[]. cnt[x] is how many numbers of a[] can get the state x, and sum[x] is sum of all minimum number of operations.For the current number a[i], I get all possible states and update cnt[] & sum[].
•  » » » » » 7 years ago, # ^ |   0 For the current number a[i], I get all possible states and update cnt[] & sum[]. This could not be done with simple two "for" loops? I mean for each state you need to know the minimal number of operations to reach it.
•  » » » » 7 years ago, # ^ |   +5
•  » » » » » 7 years ago, # ^ |   0 Ah I see, the "timer" trick to reuse array allows to avoid using map! cool
•  » » » » » 7 years ago, # ^ |   0 Thanks, that really helped. This is by far my favorite problem so far in codeforces (I've only competed 5 times), I was thinking for it for an hour and I made a lot of progress but never enough to make something implementable.
•  » » » » » 7 years ago, # ^ |   0 That's really nice solution. I've tried to do something similar during contest, but couldn't :-(. Thanks!
•  » » 7 years ago, # ^ | ← Rev. 2 →   +7 I solved C this way:1) Converted all A to binary representation (e.g. 111000111)2) Found maximum prefix that is the same for all A (e.g. if we have 10100 101000 1010000 max prefix would be 101)3) Tested all possible solutions and find the min result:step 1. Take prefix, test it as a possible solutionstep 2. Add zero to the right, test it as a possible solution. Repeat until max possible length reached (=max lenght from all A)step 3. Cut prefix by one number from the right (if it was 101 it becomes 10). Go to step 1. Repeat until prefix is goneProbably there are a proof that one of these possible solutions is minimal, but is it ok to test them all.
•  » » » 7 years ago, # ^ |   0 Complexity is O(N * log^3(max(a))), so no more than 0.5 * 10^9 operations.
•  » » 7 years ago, # ^ |   0 My approach was to find the largest number in the array, and looping over how many divisions I applied to it(from 0 until the number equaled 1). Then I found the "distance" from that divided number to every number in the array. My distance function found the minimum number of changes needed to reach b from a by first finding all possible divisions of a(exactly the same as in the first part), and then applying multiplications until it equaled b. For example, if we had 23 to 10: 11, 5, 2, and 1 are candidate solutions, so we try each one. Keep applying multiplications by 2 to each candidate until you pass 10. 11 is already past 10, so just ignore it. Multiplying 5 by 2, we get 10, so the solution would be 3(two divisions and one multiplication).So just for each division of the highest number in the array, calculate the sum of the distances from each array element to this division. Return the minimum of these sums.Nevertheless, I got WA on test case 7 :P
•  » » 7 years ago, # ^ |   +2 Alternative nlogn solution for C:Keep two arrays for each number x=1,...,10^6 — the number of original a[i] that can reach it (num[x]), and the minimum total number of steps required (req[x]).Then, first only consider the "divide by 2" operation, and for each a[i] update the values accordingly.To account for the "multiply by 2" operation, iterate up from x=1,...,10^6. First do check if this number works — num[x]=n — and update the answer. Then, "multiply" every number here by 2 — look at num[x*2], and we get req[x*2]+=(n-num[x*2]) + (req[x]-(req[x*2]+num[x*2])).Total O(nlogn)+O(n)=O(nlogn).
•  » » 7 years ago, # ^ | ← Rev. 3 →   +14 Here's another O(N log(N)) solution for C (which can be made O(N) with a simple modification).Let ans[i] be the number of moves to reach the state where all numbers are equal to i.Also, notice that any minimal sequence of moves for one number consists of some number of divisions, followed by some number of multiplications.Now suppose that we have ans[k / 2] and want to find ans[k].Case 1: k is even.Every number i that cannot reach k with only divisions must end its sequence of moves i -  > ... -  > k with a multiplication k / 2 -  > 2 * (k / 2) = k, so it requires one more move to reach k than to reach k/2.Every number i that can reach k with only divisions must pass through k on any minimal sequence i -  > ... -  > k / 2, so it requires one less move to reach k than to reach k/2.Case 2: k is odd. By the above logic, the final number can only be k if every i can reach k with only divisions: a multiplication by 2 can never end up at k. If this condition is satisfied, we proceed as above; if not, we mark k as impossible to reach.Thus if we pre-compute in O(N) the array nreach[i] = number of numbers which can reach i with only divisions, and pre-compute in O(N log(N)) or O(N) ans[1], we can calculate ans[k] for all values of k in O(N) with the formula ans[k] = ans[k / 2] + (N - nreach[k]) - nreach[k].O(N log(N)) code: 12059157 O(N) code: 12060248
•  » » » 7 years ago, # ^ |   0 I think you meant ans[k] = ans[k / 2] + (N - nreach[k]) - nreach[k] for the last formula right?
•  » » » » 7 years ago, # ^ |   0 Thanks, fixed.
 » 7 years ago, # |   0 How did you solved E ? I think there must have been a lot of different solutions.
 » 7 years ago, # |   0 E is sqrt decomposition?
•  » » 7 years ago, # ^ |   0 Yes. And counting sort.
•  » » » 7 years ago, # ^ |   +22 Or segment tree with lazy propagation:)
•  » » » » 7 years ago, # ^ |   0 Could you elaborate?
•  » » » 7 years ago, # ^ |   0 I got stuck on the part on how you merge the buckets to get the final array. How did you do it?
•  » » » 7 years ago, # ^ |   0 yes,i'm the method with you..(i caculate the range to 2e17),but the judge result is always wrong answer on pretest 7 , but i really do not know why there is a mistake , can you help me?
•  » » » 7 years ago, # ^ |   0 That was way simpler than lazy propagation segment tree.
•  » » 7 years ago, # ^ |   +3 I solved it using a lazy segment tree.
•  » » 7 years ago, # ^ |   +21 I used a set that keeps contiguous segments that are all the same letter. For a query I possibly create two new segments (on the border), then sort the segments within the range and combine, so I have at most 26 segments in that range afterwards (one for each letter). Nothing complicated :)
•  » » 7 years ago, # ^ | ← Rev. 2 →   +17 When I attempted to challenge others, I found a quite easy method. We can record sorted list of all occurred positions for all lowercase letters. Then for each query, we binary search to find which range of positions will changed for each letter and change them to new positions. The complexity is O(nq). It's quite safe to c++ in limit of 5 seconds. (x)Note: After I did some experience, some O(nq) algorithm such as counting sort is not easy to pass...(still get TLE)
•  » » » 7 years ago, # ^ |   +25 It means that once again we have a problemset where hardest problem can be easily solved with brute-force...
•  » » » 7 years ago, # ^ |   0 Did you try worst case on this solution? I am surprised that an O(nq) solution will work with n=100000 and q=50000.
•  » » » » 7 years ago, # ^ |   0 I tried this case:n = 100000 q = 50000s[i]: i%26 + 'a'all queries: 1 n 0Runtime: 2854 ms
•  » » » 7 years ago, # ^ |   +21 Note: After I did some experience, some O(nq) algorithm such as counting sort is not easy to pass...(still get TLE) Easy =)
•  » » » » 7 years ago, # ^ |   0 Wow, That’s impressive! I can't do it yesterday :(
 » 7 years ago, # |   +6 what is the testcase 7 in problem C it failed for me
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 3540 540 541the answer is 2
•  » » » 7 years ago, # ^ |   0 It's not this one. My program outputs 2 but still wa7
•  » » » 7 years ago, # ^ |   0 answer will be 3 for this test case
•  » » » » 7 years ago, # ^ |   0 nope! 541/2 then *2
•  » » » » 7 years ago, # ^ |   0 No, answer is 2:540; 540; 541 -> 540; 540; 270 -> 540; 540; 540
•  » » » » 7 years ago, # ^ |   +3 holy molly .. didn't think of that sorry :(
•  » » 7 years ago, # ^ |   +2 Missed the same testcase :P
 » 7 years ago, # |   0 it's so bad felling when you find bug 1 minute before end
•  » » 7 years ago, # ^ |   +1 bad feeling if you can't fix it in 1 minute(before end)
•  » » » 7 years ago, # ^ |   0 more bad when you fix it and it still doesn't go and then you find it after 8 seconds(after contest).
 » 7 years ago, # |   0 Contest started time is not word If there are several possible answers you may output any of them. Why?
•  » » 7 years ago, # ^ |   0 Problem B. Contest started time is not word. If there are several possible answers you may output any of them. Why???
 » 7 years ago, # |   0 At least allow me to submit!!!!!!!!!
 » 7 years ago, # |   +1 Nice contest. Task D is very nice. Haven't solved it — first failed on pretest 6, then 7, then 8 lol. Right after contest finish found one more stupid error in my Cut method. Anyway, it is a nice problem and overall nice contest, thanks.
•  » » 7 years ago, # ^ |   0 Huh, it fails now on pretest 10. Still not there.
 » 7 years ago, # |   +31 E without sqrt decomposition and without lazy propagation:For every letter let's keep intervals in a word with this letter. How? I did it with c++ set. For word abaab letter 'a' has intervals [0,0] and [2,3]. How to process a query with range [low, high]? For every letter let's remove its occurrences in [low, high] and count how many occurrences of this letter did we remove. Note: for some intervals we only cut them, not remove. Then for every letter in increasing or decreasing order we add one interval (e.g. for 'a' interval from low to low+count['a']). We add O(26) intervals in each query so number of removed intervals in previous part will be amortized O(26*q). Total complexity is O((q+n)*26*log(n)). Log because I use set.
 » 7 years ago, # | ← Rev. 2 →   0 Why does my lazy propagation get TL? :(12055344
•  » » 7 years ago, # ^ |   0 12060842 the correct one. Your lazy propagation is wrong somehow.
•  » » » 7 years ago, # ^ |   +5 It isn't wrong, it is just slower by a constant factor...Here is original version with small optimization which gets AC: 12059185Anyway, thanks for help, I like your simplier version! Didn't realize that it is only assignment on the segment, not assignment + addition.
 » 7 years ago, # | ← Rev. 2 →   0 Why i cant hack solutions with test with size over 256kb... I must decrease test twice, because of this limit, and solution passed my test, but timelimits on maximum test.... Now instead of i hacked 5-6 solution using STL on B problem, i have one unsuccessful challenge...
•  » » 7 years ago, # ^ |   0 you could create 196 KB test size100000{1 1 1 ... 1 1}
•  » » » 7 years ago, # ^ |   0 Its not the same.. Numbers should be different.
•  » » » » 7 years ago, # ^ |   0 you can use generatorlike this
 » 7 years ago, # |   0 i don't know why my code is wrong????? http://codeforces.com/contest/558/submission/12058908
 » 7 years ago, # |   0 What's wrong with my code for Prob A? Getting unexpected behaviour :( Code
•  » » 7 years ago, # ^ |   0 your code prints two extra lines before answer remove these lines: cout<apples<apples<
•  » » » 7 years ago, # ^ |   0 That was for debugging(myself), it crashes on test case two, the iterator does not stop at the end(), rather it continues on :(
 » 7 years ago, # |   +5 What about rating?
 » 7 years ago, # |   +17 What order is calculating Ratings? N^3 would be finished until now.
 » 7 years ago, # |   0 How to solve C with DP?
 » 7 years ago, # |   0 it's a good contest although i can't solve d and e :)
 » 7 years ago, # |   0 After contest, I solved C with BFS. :D Damm, y couldn't I figure it during contest time.
 » 7 years ago, # |   0 I don't like participating when it is only div 2 without div 1 because all those unranked users always distort the rankings.
 » 7 years ago, # |   0 I am not able to get where I am doing wrong in solution for problem A. Here is my solution. Can anybody please help me. http://codeforces.com/contest/558/submission/12052565
•  » » 7 years ago, # ^ |   0 sort the arrays and calculate ,then it will work definitely :)
•  » » » 7 years ago, # ^ |   0 oh..I see!! Thnx a lot. :)
 » 7 years ago, # |   0 Could anyone tell me that why all my submissions are skipped? Although they passed all the system tests
•  » » 7 years ago, # ^ |   0
 » 7 years ago, # |   0 Is anyone one help me for find my bug in problem C.I got lot of wa... and lastly got TLE.But i don't understand why ???My code: CodeBy the way.. Nice problem , thanks =D
•  » » 7 years ago, # ^ |   0 Got Ac :)
 » 7 years ago, # |   0 thank you for sharing such an amazing article. By the way, when it comes to PHP Deployment tools, Office deployment tools, etc. I only trust Pharaoh Tools. Check their website at http://www.pharaohtools.com/deploy and see for yourself by just watching their free online tutorials how informative they are.
 » 6 years ago, # |   +8 مبروك
 » 2 years ago, # |   0 For Div2C, (another $O(n\times m^2)$ solution):Observation: We can never add a set bit by these operations. The number of set bits in a number can remain the same, (left shift), or decrease (in case of a right shift). So we should look at the numbers that have the minimum number of set bits in them. We can use __builtin_popcount` for that. We do so, because in the end all the numbers must have equal value. So the bits must be equal too. So, since you can't increase the number of bits, the numbers generated by the numbers that have the minimum number of bits are the ones which are needed to be checked. Amongst the numbers which have the minimum number of set bits, we take the one which has the minimum value (rightmost MSB). Let's call it $j$ This is selected because it is easiest to decrease the number of set bits from it.Now you generate every number from every number, and count the total number of operations needed to generate it, plus a check, whether the number is generatable from every number in our array. Now, we check every number $K$ generated by $j$, if $K$ is generatable from every number in our array. The minimum number of operations are output as the answer.Here is my submission