### Bugman's blog

By Bugman, 8 years ago, translation,

Hello everybody!

Today will be Codeforces Round #276, which take place in both divisions. Start time is 19:30 in moscow time (follow this link to see time in others zones). For preparing contest i say thanks to Zlobober, for translating to Delinur, and to MikeMirzayanov for project Codeforces.

Good luck to all, hope you will enjoy problems :)

UPD Score distribution will be dynamic (see more information here). Problems will be sorted in increasing order of difficulty, however, do not forget to read all problems before the end of the contest.

UPD The contest is over! Thanks to everyone who solved the problems despite everything. Analysis will be published later.

UPD Editorial can be found here.

• +276

 » 8 years ago, # |   -86 Please short explanation for problems. --> Because read story of problems is too tedious.Also explanation of sample tests. For better understand problems." THANKS FOR READING
 » 8 years ago, # | ← Rev. 3 →   -164 Please give me '-' till my contribution reaches 0 and then stop.
•  » » 8 years ago, # ^ |   -46 you what?
 » 8 years ago, # |   -53 Now I know the reason behind late , Bug Bugman
 » 8 years ago, # |   +29 1 hour later is not good for me
•  » » 8 years ago, # ^ |   0 Daylight saving time.
 » 8 years ago, # |   +3 I am new to code forces.What is div 1 and div 2 in round #276?I could not register in div 1 so have registered in div 2 .May i know how div 1 and div 2 users are distinguished
•  » » 8 years ago, # ^ |   +6 Div 1 users must have more than 1700 points
•  » » » 8 years ago, # ^ |   +22 or equal to 1700
•  » » 8 years ago, # ^ |   +9 MikeMirzayanov's post on Rating System: http://codeforces.com/blog/entry/102
•  » » 8 years ago, # ^ |   0 Div1 is more advanced level than div2
 » 8 years ago, # |   0 your last contest(#256) has nice problem.thanks~
 » 8 years ago, # |   +3 What's a good tool to visualise the call graph of my code as it solves a sample test case? And that won't take much time overhead to use during a contest? (For Python or C++.)
•  » » 8 years ago, # ^ |   +3 so for simple: foo() { bar(); } main() { for ( int i = 0; i < 10; ++i ) foo(); } you want to see what? main foo bar foo bar foo bar foo bar foo bar foo bar foo bar foo bar foo bar foo bar ?
•  » » 8 years ago, # ^ | ← Rev. 2 →   +23 In Visual Studio you can see good visualisation (screenshot is in previous edit) Is it what you want?
•  » » » 8 years ago, # ^ |   +3 I cannot see the screenshot (in Rev. 1)...
•  » » » 8 years ago, # ^ |   0 Something like that. But also a bit different: it should be a graphic so I can take one look at it and know what went wrong. I think I'll have to write my own. It would be easy to parse the output such as what appears in your screenshot or of a profiler for either Python or C++.
 » 8 years ago, # |   -9 StoneCold_ wt??
 » 8 years ago, # |   +5 Hope short and simple problem description just like the announcement :)
 » 8 years ago, # |   +25 Very bad time for Asian participants
•  » » 8 years ago, # ^ |   0 What time it is for you? Because in Europe (let say Central Europe) time was not changed, probably because of summer time...
•  » » » 8 years ago, # ^ | ← Rev. 3 →   0 10.00 PM or somewhat near in South Asia
•  » » 8 years ago, # ^ |   +2 You are right...It's 0:20 AM in China...
•  » » 8 years ago, # ^ |   +17 Not in Iran ( 8:00 PM ) :D
 » 8 years ago, # |   0 not able to wait..
 » 8 years ago, # |   +12 1 hour later is very bad for China. It is 0:30 for us, what a sad story!
•  » » 8 years ago, # ^ |   +22 I have to move to China, quite good time for me...
•  » » 8 years ago, # ^ |   +17 And it is 1:30 for Japanese...
•  » » 8 years ago, # ^ |   +3 It was 3:30am here when the contest started. These coding events remind me how much I like to work in the peace of the night.
 » 8 years ago, # |   +4 I hata the start time, it's too late in our country
•  » » 8 years ago, # ^ |   0 It's 10.30Pm in Bangladesh. Quite a good time.
 » 8 years ago, # |   0 Hi, I keep receiving emails in Russian for the contest announcements. Can I switch this to English somehow?
 » 8 years ago, # |   -10 I'm Unlucky in dynamic score :(
 » 8 years ago, # |   -55 Please unlike me :) Plz
•  » » 8 years ago, # ^ |   +6 As you wish
 » 8 years ago, # |   +44 I am always curious to know why do the authors declare the score distributions at the last moments. Has it anything to do with the number of registrants??
•  » » 8 years ago, # ^ |   +41 I am always curious to know why do the participants care about score distribution before the last moments
 » 8 years ago, # |   0 Hope to see a nice problem-set and +ve rating growth.. Dynamic-Scoring has always haunted me :P
 » 8 years ago, # |   +19 Server is too busy and can't open any of the problems, is it only me?
•  » » 8 years ago, # ^ |   +2 Nope.The server is very busy, it's impossible to submit or even access to the statements !
•  » » 8 years ago, # ^ |   +1 Server is stuck (
•  » » » 8 years ago, # ^ |   0 As always when contest is running and lot of participants...
•  » » 8 years ago, # ^ |   0 me too
•  » » 8 years ago, # ^ |   0 same here
 » 8 years ago, # |   0 I don't know what happened, but there are more than 1000 submissions waiting for judging.
 » 8 years ago, # |   +3 Nice problems but server is always busy!!! I submitted the code for A-Bits 10 minutes ago and it's still in queue
 » 8 years ago, # |   +8 I can't send any problem. Is the round going to be rated?
 » 8 years ago, # |   +18 Is it rated today?
•  » » 8 years ago, # ^ |   0 In my opinion, it shouldn't be...
 » 8 years ago, # |   +2 In queue
 » 8 years ago, # |   0 It's 11 p.m. I tired to wait. And I'm going to sleep.
 » 8 years ago, # |   0 Nice set of problems, but the system is making it almost impossible to compete.
•  » » 8 years ago, # ^ |   0 Agreed, the last 3 problems look equally challenging.
•  » » 8 years ago, # ^ |   0 Yes. 30 minutes to send the solution, waiting the submit page opens..
 » 8 years ago, # |   +8 Good short statements ;)
 » 8 years ago, # |   +8 seems round will be unrated ;( ... anyway, keep solving!
 » 8 years ago, # |   +9 unrated :)
 » 8 years ago, # | ← Rev. 2 →   +117 "This round will be unrated due to technical issues."
 » 8 years ago, # |   0 if contest rated , I will up rating, but it is unrated. I am very sad !
 » 8 years ago, # |   +15 How about providing the problems in pdf, as in the gym, along with the online version, so that if server is getting overloaded then people can do with them (download that file initially as a back up)
•  » » 8 years ago, # ^ |   +17 Open all the problems as soon as the contest starts.. Works for me everytime..
 » 8 years ago, # |   +16 After the contest started I thought, "Awesome problems, awesome statements. I really hope I everything goes well today! :)" An hour later... "Long queue, contest is unrated for technical issues". Now I'm thinking, "Why did I have to jinx it?! :(("
 » 8 years ago, # |   +27 this round is like BAYAN contest ... great problemset but ...
 » 8 years ago, # |   -11 And a buggy round by Bugman :(Waited long for a DIV2 round and got this :/
•  » » 8 years ago, # ^ |   +57 I don't think that it's Bugman's fault
•  » » » 8 years ago, # ^ |   +43 No, but the irony in his handle :D
•  » » » 8 years ago, # ^ | ← Rev. 2 →   -38 I know it's more like a server fault. But I noticed that Div2A points were changed twice. First it was rated 1000, then 500 and now 1000 again. So, I do suspect that some way or the other, Bugman is at fault, if not majorly.Update: It's 500 point problem again.
•  » » » » 8 years ago, # ^ |   +3 The points are changing only because the score distribution is dynamic. If C is solved by many people by the end of the round, it will probably bring only 500 points.
•  » » » » » 8 years ago, # ^ |   -15 I know its dynamic. The guy in the top of my room had 900+ point in problem A. Now he has 480 points. The score of an individual changes after correct submission too? I'm sorry, I didnt knew about it.
•  » » » » » » 8 years ago, # ^ |   0 I don't think you know the correct meaning of dynamic scoring. The scores change based on the number of correct submissions on a problem. The lower correct solutions, the harder the problem is thus higher the score and vice versa.
•  » » » » 8 years ago, # ^ |   +3 this is normal to happen in dynamic score, first the score is 1000 then more people solved the problem makes it 500 then more people make wrong submission as a first submission(or solved another problem) which increase number of participants making the points of the problem back to 1000
•  » » » » » 8 years ago, # ^ |   +3 Oh thanks. I didnt knew about it. I take my criticism back :P
•  » » » » » » 8 years ago, # ^ |   +3 In Soviet Codeforces, you can't take it back.Aren't you aware of the Russian proverb: "a word ain't a sparrow: once released — it can't be recaptured"!
•  » » 8 years ago, # ^ |   +1 Such a pain, when there's finally div1 contest where you can participate... and clar says it's unrated :'(
•  » » 8 years ago, # ^ |   -6 Congratulations!
 » 8 years ago, # |   0 If only I can punch person to death I will punch myself. Such a waste of precious sleeptime.
 » 8 years ago, # |   +2 contest is unrated . . . keep calm and . . start self mutilation. . . :-"
 » 8 years ago, # |   +2 Solves div2 C in 5 minutes -> unrated round.Tough luck =(Is anyone having trouble locking problems? i want to try to hack some solutions, but i can't seem to find the button to lock a problem.
•  » » 8 years ago, # ^ |   0 Congratulations!
 » 8 years ago, # |   0 Well, I decided to improve my ranking. Not destiny :)
 » 8 years ago, # |   0 5th November of 2k14... the day that Codeforces died...http://i.imgur.com/LN2DJZV.png
•  » » 8 years ago, # ^ |   +23 "Remember, remember, the fifth of November" Codeforces Edition
•  » » » 8 years ago, # ^ |   +21 Keep calm friends. I know codeforces is not doing well today, but instead of backfiring at it why dont you try to solve the problems, or even go to sleep, than blaming contest writers, platform etc. Remember, the joys the platform has given you, the job you got by practicing at this platform, the money, fame so many things. And one day it is bad and you show this attitude towards it. I am sorry If I sound harsh, but it preety much shows people's character.
•  » » » » 8 years ago, # ^ |   0 It was just a joke m80 (matey)
•  » » » » » 8 years ago, # ^ |   0 It was not directed particularly to you mate, but to all such comments above.
•  » » 8 years ago, # ^ |   +10 Somehow it reminds me about Black Day of Codeforces
 » 8 years ago, # |   0 Ow God knows when the next contest will be ... :(
•  » » 8 years ago, # ^ |   +5 In 5 days actually: http://codeforces.com/contests/486And in 2 weeks for Div 1: http://codeforces.com/contests/487
 » 8 years ago, # |   +3 ridam to contest :) tnx
 » 8 years ago, # |   +76 Remember, remember the fifth of November, the Gunpowder treason and plot; I know of no reason why the Gunpowder treason should ever be forgot! I guess Codeforces system blew up in the spirit of Guy Fawkes Day!But in serious matter, there were 5000+ competitors and this is the 276th round. One would expect the system to be more stable by now. I personally feel sad for Bugman because that was one good problemset and I think he deserves some credit and I'm quite sure that it wasn't his fault at all. And about changing problem scores mentioned above, scores are dynamic, of course they will change!Well, anyway I liked the problems so thanks for the good problemset :)
 » 8 years ago, # |   0 it is my worst contests always "Busy Server" or "in queue"
 » 8 years ago, # | ← Rev. 3 →   +2 Im so sorry but I have to give up this contest for many reasons:-( Expecting next competition ! :)
 » 8 years ago, # |   0 rating would have improved if the server didn't hangup :\ sad day!!
 » 8 years ago, # |   0 Is hacking disabled due to the contest being unrated? I cannot lock my problems
 » 8 years ago, # |   -29 There are still 40 minutes remaining, but I'm very sleepy. I will sleep now.
•  » » 8 years ago, # ^ |   0 congratulations
 » 8 years ago, # |   +170 Sorry, guys. It seems that it was my fault. I don't know all the reasons why everything happened bad. The main reasons are: ext4 partition on one server switched to read-only mode because of unknown reasons (I will try to diagnose this), judging code used old version of our http-wrapper library with resource-leak. Sorry again about it. I apologize to the writer Bugman he did his job great. Be sure, some sleepless nights are waiting for me!P.S. Fefer_Ivan, it is hard without you...
•  » » 8 years ago, # ^ |   +122 I also want to say thank you for those who didn't stop participating just because of contest being unrated and who continued solving nice tasks that Bugman prepared.I hope that we will see new contests set up by him again!
•  » » » 8 years ago, # ^ |   +21 You didn't answered me personally, but again — where is Gerald ?)
•  » » 8 years ago, # ^ |   0 no problem at all
•  » » 8 years ago, # ^ |   +6 Nothing to sorrow. At least I learned something by trying the problems. Just it will be nice if we have the upcoming contest soon. Thanks! :)
•  » » 8 years ago, # ^ |   +30 ext4 partition on one server switched to read-only mode because of unknown reasonsThe kernel remounts a filesystem read-only if it encounters an I/O error on the underlying device. If this is what happened, then the kernel log should contain the details.
•  » » » 8 years ago, # ^ |   +5 MikeMirzayanov, can you confirm if what andreyv said is what happened? me curious!
 » 8 years ago, # |   +17 how to solve div-1 d .
•  » » 8 years ago, # ^ |   +3 You want to partition the sequence in subsequences each of which will be "going up" or "going down". Solution is a DP where you state is (position, down or up).
•  » » 8 years ago, # ^ |   -13 My solution (possible solution, I don't know if it's the correct one) was the following: - You can build a DP like dp[i] = min j < i(dp[j] + maxValue(j + 1, i) — minValue(j + 1, i) - The solution above is too slow O(N²), but you can notice that maxValue(j + 1,i) — minValue(j + 1, i) is increasing as we decrease 'j' and that dp[j] is increasing as we decrease 'j'. The sum of one increasing function with one decreasing function is a function that increases and then decreases. - Given that fact we can actually do a ternary search on the maximum 'j', so now we reduced our solution to O(N log N)
•  » » » 8 years ago, # ^ |   +3 "The sum of one increasing function with one decreasing function is a function that increases and then decreases."Are you sure?
•  » » » » 8 years ago, # ^ |   -6 Not so sure, that's why I don't know if my solution is actually right. My intuition was telling me to assume that dp + max — min is a function that can be ternary searched.
•  » » » » » 8 years ago, # ^ |   0 It's actually false: Sum 1 3 7 9 and 9 8 3 2yields 10 11 10 11 which increases, then decreases and finally increases again.
•  » » » » » » 8 years ago, # ^ |   -6 Yeah, you're right. I guess the lesson is not to trust your gut at all times, they may be wrong!
•  » » » 8 years ago, # ^ |   0 The sum of one increasing function with one decreasing function is a function that increases and then decreases Nope , you're wrong take this example: A= 10 20 30 40 B= 50 45 25 20 Sum= 60 65 55 60 
•  » » 8 years ago, # ^ | ← Rev. 2 →   +4 DP. Sequence rises up and down.And the key-point is you will never separate a continuous sub-sequence into more than one sub-sequences if this sub-sequence is straight up or down.For example:-2 4 5 1 -7 3 6you should divide them into :-2 45 1-7 3 6or -2 4 51 -73 6or something like that.You can figure out that the only thing you need to handle is which part should the peak and the bottom of the sequence belong. Turns out a DP problem.You can check my code.Hope that helps.:D
•  » » 8 years ago, # ^ | ← Rev. 3 →   +19 Also it has simple O(N) solution: x = -a[0]; y = a[0]; ans = 0; for (int i = 0; i < n; ++i){ ans = max(x + a[i], y - a[i]); x = max(x, ans - a[i + 1]); y = max(y, ans + a[i + 1]); } cout << ans << endl; 
•  » » » 8 years ago, # ^ |   +6 Could you please explain why this works? I looked at it for a long time, but I can't figure out what x and y represent. Thanks in advance.
•  » » » » 8 years ago, # ^ |   +21 In optimal answer any segment that making a group contains their minimum and maximum values on borders. So, we can write following dynamic solution, which find answer on each prefix of array:orTherefore it is sufficient to remember and update the maximum values of ansj + aj + 1 (y in my code) and ansj - aj + 1 (x in my code) at each step.
 » 8 years ago, # |   +4 When will system testing begin?
 » 8 years ago, # | ← Rev. 3 →   +1 i really loved the C Problem, i'm not sure why, but i just loved it :D
 » 8 years ago, # |   +1 No rating is not bad for mee, round was difficult... waiting system test...
 » 8 years ago, # |   +7 How I solve problem D?
 » 8 years ago, # |   -18 Thanks for the Nice problemset Bugman , I just wanted to tell you that I enjoyed the round despite the technical difficulties that were being caused by codeforces . PS:If you like what I have said above then give it a '-' .
 » 8 years ago, # |   0 Is there some tricky case for Div1 A/ Div2 C?I solved it as follows: let the answer be stored in res. go through the bits of the 2 numbers(from left to right). If the current bit is 1 in both then set that bit in res. If it is 1 in r only then set it to 0 in res and make all next bits 1. In the end count the number of 1s in res and the number of 1s in r. output the one with the max.What's wrong with that?
•  » » 8 years ago, # ^ |   0 So... I have finally seen the test that failed me and it seems to work fine locally but outputs a wrong answer in Custom Test... Can anyone tell me what could've gone wrong here? Submission
•  » » 8 years ago, # ^ |   0 i had the same problem but i fixed it, you must think what happens when you have a case like this:Left = 6 ; Right = 76 is written in binary like 110 7 is written in binray like 111following with your approach you will go to the last bit and set it as 0 then all the remaining bits as 1, but in this case you will return 6 and the correct answer is 7. So, you must care the case when it is the last bit, if they only differ in the last bit you must return Right
•  » » » 8 years ago, # ^ |   0 Actually not... As I said, at the end I count the number of 1s in r and the number of 1s in res and print the one with more 1s... In this case, I'd print 7 :D
 » 8 years ago, # |   0 contest had many bugs bugman! :)
 » 8 years ago, # | ← Rev. 2 →   +21 All problems are very interesting. Thanks to Bugman.
 » 8 years ago, # | ← Rev. 4 →   +1 still waiting for my first hack attempt :D
•  » » 8 years ago, # ^ |   0
 » 8 years ago, # |   +5 When you are as bad a coder as me then technical difficulties are not such a big problem for you! :P My only submission was Div2 C at 2 hours 7 minutes past the start of the contest and it got tested without any delay.
•  » » 8 years ago, # ^ |   0 My only submission was Div1 A at 0 hours 6 minutes past the start of the contest and it got tested without any delay :D
 » 8 years ago, # |   +1 Div1 D:We can prove that each groups must be increasing or decreasing. So we can solve it in O(N) with using ordinary DP.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +14 Or the problem is just asking to traverse the array from left to right choose some numbers and add to solution and some other numbers and subtract it from solution such that at any time during the traverse number of numbers that you added to solution differs from number of numbers that you subtract from solution by at most 1 but at the end the two numbers should be equal , this can be solved by very simple dp my code 8576807
•  » » » 8 years ago, # ^ |   +8 Lol, how simple. Reminds me of 383D - Antimatter with a long explanation for the official solution and a short one for the one most people found.(It's not like DEGwer's version is much harder — you just need to think when it's better to split/merge a group and it follows almost immediately.)
•  » » 8 years ago, # ^ | ← Rev. 3 →   +7 I like D , I tried to solve it ( but got TL ) with DP , ternary search and segment trees.
 » 8 years ago, # |   +4 I have seen Div1 B in a Japanese high school programming contest.http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0270
 » 8 years ago, # |   0 Nice problem at all, thanks for the contest. Btw, someone can describe the solution of problem Div2C/Div1A? Please)
•  » » 8 years ago, # ^ | ← Rev. 2 →   +1 greedy will work :). let b = number of bit in R (upper bound).now start from res = (1<
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +1 Thank you man!) I will try to solve it, later.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +1 go from li to ri increasing the number of ones in his binary representation :for exampleli = 0010001 -> 0010011 -> 0010111 -> ...... until it reach some number equal or greater than riri = 1010101when I say increase number of 1s , I mean add 1s in the 0-positions from right to left, every time you add an 1 digit the result number is the minimun number with 's' 1 digits ( s = current number of 1 digits in the result number ) greater than ri , you can prove it.
 » 8 years ago, # |   +10 Good problems. Bad network.
 » 8 years ago, # |   +5 How is Div2-D / Div1-B to be solved?
•  » » 8 years ago, # ^ |   -9 huh!, Codeforces community is busy with up-voting instead helping the guy.
•  » » » 8 years ago, # ^ |   0 Tutorial already published, you know...
 » 8 years ago, # |   +5 Thank you Bugman for this amazing round. I took the best place I ever had, and that gave me faith. My self esteem is in your debt.
 » 8 years ago, # |   0 Why do we need to run the loop 'm' times in Problem A of Div-2?..
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 I have the same question can someone please explain?
•  » » 8 years ago, # ^ |   +1 in case we have 65535 65536, Answer is "Yes". so , we must check until m or else we may get a wrong answer in this brute force method .
 » 8 years ago, # |   +1 Thanks Bugman for great problems. I was sad when I read announcement but I was happy after system testing (because my solution A failed) :)
 » 8 years ago, # |   +10 Thank you Bugman for such an awesome problemset! If the servers didn't have issues during the contest and ran smoothly I think it would've been an even better one. I hope we'll see more rounds from you in the future! :)
 » 8 years ago, # |   +5 Quite a nice contest :) My first hack ever! Thank you Bugman.
 » 8 years ago, # |   0 nice contest and fast editorial
 » 8 years ago, # |   0 Why rating system is too slow? Or is it a unrated contest??
•  » » 8 years ago, # ^ |   +3 Yes, due to technical reasons round is unrated.
•  » » » 8 years ago, # ^ |   0 ohhh..but thanx for an excellent problemset
 » 8 years ago, # |   +19 Just wondering, is this the first time for a contest being unrated? Anyway the div2 problems are as good as your last contest. Thanks, Bugman.
•  » » 8 years ago, # ^ |   0 No, unfortunately this is not the first time.
 » 8 years ago, # |   0 The problems was really nice. But frankly saying, The English description of problem A was quite bad.
 » 8 years ago, # |   +33 8573331 Output qertwy qtewry qetyrw Answer qertwy qtewry qetyrw Checker comment wrong answer 1st lines differ - expected: 'qertwy', found: 'qertwy' `
•  » » 8 years ago, # ^ |   +3 hint: check the length of s
•  » » » 8 years ago, # ^ |   0 If check visually, seems that checker printed both string of length 6, no more symbols, spaces or newlines.
•  » » » 8 years ago, # ^ |   0 Already changed that yesterday, but either way I got TLE :P. Too much copying vectors :(
•  » » 8 years ago, # ^ |   0 I don't get it. Why is it WA?
•  » » » 8 years ago, # ^ |   +1 I didn't expect that it can be a reason of WA, but it's caused by zero byte.
 » 8 years ago, # |   -7 My rating didn't change after the contest...
•  » » 8 years ago, # ^ |   0 Really? My changed as I expected...
 » 8 years ago, # |   +9 Country wise rankings have been updated for this contest. Although I know many people left the contest half way, including me, but still had to update the site.
•  » » 8 years ago, # ^ |   +3 I like the link, thanks ;-)
 » 8 years ago, # |   +3 next div 1 contest after two weeks...
 » 8 years ago, # |   0 when will the ratings be updated?
•  » » 8 years ago, # ^ |   0 After the next contest ends XD