### KaiZeR's blog

By KaiZeR, 5 years ago, translation, ,

Hi Codeforces!

We would like to invite you to participate in Codeforces Round #266 Div2, which will be held this Friday, September 12th at 19:30 MSK. As usual, Div1 participants can take part out of the competition.

Problems have been prepared by Antoniuk and me. It's the second round prepared by us, and we still hope it won't be the last.

We want to thank Gerald for helping to prepare this round, Delinur for translating the statements, and also MikeMirzayanov for Codeforces and Polygon.

It will be used a standart scoring: 500-1000-1500-2000-2500.

Gl & hf!

UPD. Round has finished. Thanks for participating.
UPD2 Congratulations to top-5 participants:

1) dominator_hza
2) Final_Battle
3) free_pascal
4) vanhanh.pham
5) fzmh

UPD3. Editorial .

•
• +152
•

 » 5 years ago, # |   +1 I really liked k-tree! Hope to see some more problems like that!
 » 5 years ago, # | ← Rev. 2 →   +2 Brazil's ACM/ICPC First Phase will be held this Saturday, this contest came in a good time for a last preparation. Thank you.
 » 5 years ago, # |   -7 it won't be 500-1000-1500-2000-2500?
•  » » 5 years ago, # ^ |   0 no it will be :D
•  » » » 5 years ago, # ^ |   0 just a moment ago KaiZeR haven't show score...
 » 5 years ago, # |   +3 i really shocked when see only 4 comments :D usualy it's in order of 50-100
•  » » 5 years ago, # ^ |   0 how will be destiny of worse ?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +7 He discovered a white color under the grey wow :Dbut i don't think there is a negative rating he will just stop at zero :D[UPD] He got negative rating now i'm surprised :D
•  » » » » 5 years ago, # ^ |   +7 No!! He has broken all the barriers!Even before tourist could reach 3300, he has splurged to -37 ! Unbelievable!
•  » » » » 5 years ago, # ^ |   0 [Rating graph of worse... ]
•  » » » 5 years ago, # ^ |   0 He/She has registered In the last contest his/her rating changes was -48. tourist missed rating 3300 for a single point in his last contest. Will worse touch the 0 rating ???
•  » » » 5 years ago, # ^ |   0 I don't think he uses Russian version
•  » » » » 5 years ago, # ^ |   0 But he does speak Russian, you can see this from his comments
•  » » 5 years ago, # ^ |   0 I think users didn't find any specific problem in the text of the blog entry or ... to talk! Everything was ok :)
 » 5 years ago, # |   +37 Wow! tourist just finished in 22 minutes!
•  » » 5 years ago, # ^ |   0 Where is scoreboard for out of competition participants?
•  » » » 5 years ago, # ^ |   0 There should be a check box to toggle on/off for unofficial.
 » 5 years ago, # | ← Rev. 2 →   0 Is there any problem in java compiler? Runtime error for me even in custom invocation, working fine in my computer. UPD- BigInteger function nextProbablePrime() giving runtime error on codeforces.
 » 5 years ago, # | ← Rev. 2 →   -16 .
•  » » 5 years ago, # ^ | ← Rev. 2 →   +13 Really?UPD. same in G++ 4.7 w/o C++0x
 » 5 years ago, # |   0 hard math contest !!!
 » 5 years ago, # | ← Rev. 2 →   +13 sometimes easy math is very hard , how to solve B?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +9 If you'll increase both numbers by more than 1e5, then product will increase by more than 1e10. But it is clear that you can get better answer, so you may check only all possibilities of increasing one of numbers by 0..1e5, and for every such possibility calculate required increasing of second number.
•  » » » 5 years ago, # ^ |   -9 i did increase to sqrt(6*n), it's correct
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Maybe I'm misinterpreting, but how would this method work for something like 1000000000 1 3000000001?EDIT: Never mind, indeed misinterpreted.
•  » » » » 5 years ago, # ^ |   0 2 3000000001
 » 5 years ago, # |   0 how to solve D??
•  » » 5 years ago, # ^ | ← Rev. 2 →   +18 DP[i][j] — how many ways to solve first i points while having j open segments.You have following moves at position i: close some of previous segments, don't open new (j+1 ways to choose segment to close) close some of previous segments, open new (j ways to choose segment to close) open segment and close it in same cell (1 way) open segment and don't close anything here (1 way) neither open nor close segment here (1 way) And for every possibility you should check that number of segments covering position i after such move is h-a[i];Answer will be in DP[n][0] (you solved all points, all segments were closed).
•  » » » 5 years ago, # ^ |   +30 Also there is an O(n) solution 7772910
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Yes, and you can also improve naive DP[i][j] to something similar to your solution, that will also work in O(N), noticing that we should care about only few values of j for some fixed i (if jh-ar[i] then it makes no sense).
•  » » » 5 years ago, # ^ |   0 Thanks very clear explanation
•  » » 5 years ago, # ^ |   +8 A simple linear solution. Consider the sequence bi = h - ai. If some two bi, bi + 1 differ by more than one, the answer is 0, since some two blocks begin or end in the same position.Otherwise the answer is the product of values val(i, i + 1): if bi - 1 = bi + 1, then we must end one of the bi - 1 blocks. This can be chosen in bi - 1, so val(i, i + 1) = bi; if bi - 1 = bi, then we can end any of bi - 1 blocks that still continue at position i - 1, and start a new block at position i. Or we can continue all of the blocks. So val(i, i + 1) = bi + 1; if bi - 1 = bi - 1, we should begin a new block, so val(i, i + 1) = 1;
•  » » » 5 years ago, # ^ |   0 What does Val mean?
 » 5 years ago, # |   +8 I think this time problem B was one of the hardest problem B's I have ever solved...
•  » » 5 years ago, # ^ |   +1 Yeah, I was confused about how to solve (a + x)(b + y) ≥ 6n where x and y are the number by which a and b are incremented. I tried to solve this for most of the time and I couldn't concentrate on problem C because I couldn't solve B!
•  » » » 5 years ago, # ^ |   0 Either x or y is small: just check all values up to million
•  » » 5 years ago, # ^ |   0 A lot of us tried a greedy approach or maths, making it seem tough, but a brute force approach would have solved this. As pointed out by LeBron and AvadaKedavra_____ColdFan in the comments, both numbers cannot exceed 1e5 (LeBron's idea) or sqrt(6*n) (AvadaKedavra's idea). You just check a or b for all possibilities from 0 to 1e5 or sqrt(6*n) and calculate the required increase of the second number.
•  » » 5 years ago, # ^ |   +2 I think this time problem B was one of the hardest problem B's I have ever not solved...
 » 5 years ago, # |   +2 Ironically, though there were few solves, the tests for B seem to be pretty weak — my submission 7762305 was accepted despite failing on many many tests (any of the lines in http://pastebin.com/rP0u5f4t would result in WA) due to having > rather than >=. The actual problem was pretty nice itself though — proving that the solution will run in time is not too simple or obvious.
 » 5 years ago, # |   +5 Seems like there was some miscalculation of the problems' complexities :D
•  » » 5 years ago, # ^ |   +1 Thanks for this. I should not be happy for solving the C question for the first time. :(
 » 5 years ago, # |   +4 Hard but nice problems!
 » 5 years ago, # |   +6 Rank: 235 , best performance so far. :)Biggest mistake that I made was locking all solutions when I did not have any intention of spending much time on hacking.Solution B got hacked. Could not resubmit. :(Probably will remain EXPERT for some time.
•  » » 5 years ago, # ^ |   0 Congrats, I too had my best performance so far today! Solved E for first time! :)
 » 5 years ago, # |   0 can anyone tell me why this solution gives WA while it works for that case on my pc http://codeforces.com/contest/466/submission/7772471
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Not sure if that's the cause but a thing I notice is you do not return 0 in the end of the function, so I suppose the returned value is undefined, therefore it may return true at some moment?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 i donot get it can u plz explain more how can it return true?
•  » » » » 5 years ago, # ^ |   0 Well you don't return 0 if the function doesn't find an answer? You know, a function must always return a value. Since you don't tell it to return 0 (false) it may return whatever it likes in theory :D
•  » » » » » 5 years ago, # ^ |   0 yes right but in that case i donot call the function
•  » » » » » » 5 years ago, # ^ |   0 but that was the bug weired
•  » » » » » » » 5 years ago, # ^ |   0 That bug was the difference between me and div 1
•  » » » » » » 5 years ago, # ^ |   0 You do call it. 6*11=66, while 7*7=49, so n>a*b, therefore you do call the function.
•  » » » » » » » 5 years ago, # ^ |   0 the contest effect sorry
 » 5 years ago, # |   +27 Finally worse did it.
 » 5 years ago, # |   +31 Congrats to worse for becoming the first ever white coder on codeforces !
 » 5 years ago, # |   +6 Even though ratings have been updated, colors have not. I am a specialist with rating 1553. :P
•  » » 5 years ago, # ^ |   +36 I guess they are struggling with assigning white color to worse.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +1 Looks like Exception in thread "RatingUpdater" :Dworse has broken the system :)
 » 5 years ago, # |   +7 What happened to my account rating ? http://screencast.com/t/pdEJQN5CZu
•  » » 5 years ago, # ^ |   +9 Probably worse's today achievement completely distorted the global rating update system.
•  » » 5 years ago, # ^ |   0
 » 5 years ago, # |   +9 I solved nothing but A this contest.I've actually solved E(for the first time in my life) but made a simple mistake. In one of the lines, I used the variable which I use to count the number of tasks received till now instead of the variable that holds the number of task that is in question... Passed pretests but got WA in system tests :( I suspected that I'd get TLE in system tests but when I corrected that line I got AC...Anyways... Let's look at the bright side.. I've solved my first E even though it's not official.
 » 5 years ago, # | ← Rev. 3 →   0 This is first time I solved problem E! :D And became candidate master! :D :DAt first I got many WA 3 times on problem 1, I thought that for sure I will become Specialist again (got Expert only in previous contest).After A passed pretests, I tried C and again got WA 2 times... tried E and got TLE. Finally I tried different method and E worked, then turned out I had to use long long int in C and that passed pretests as well.Edit: I previously asked about other solutions to E, but I found a very simple one now.
 » 5 years ago, # |   0 I am unable to guess why my code gives WA plz can someone help me find the bug .Here's my submission http://codeforces.com/contest/466/submission/7774444
•  » » 5 years ago, # ^ |   +6 Wow , nice submission id 7774444
•  » » » 5 years ago, # ^ |   +3 It's a lucky number according to Codeforces Beta Round #84 (Div. 2 Only) :D
•  » » » » 5 years ago, # ^ |   +3 though, his submission unluckily got WA
•  » » » » » 5 years ago, # ^ |   0 It must have only been nearly lucky :(
•  » » » » 5 years ago, # ^ |   0 Why is that so? I mean lucky !
 » 5 years ago, # |   +6 So, apparently E had weak testdata. Or else, How did this solution pass? http://codeforces.com/contest/466/submission/7765318 I can break this solution with very easy testcase.
•  » » 5 years ago, # ^ |   +3 there are many question like this with weak tests... anyway after this time if i cant solve a problem efficent i will send a naive solution :|
•  » » 5 years ago, # ^ |   0 Can you give one?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 I think an input of the following type would work: 50001 100000 1 2 1 1 3 2 1 4 3 1 5 4 ... 1 50001 50000 2 50001 3 1 1 2 50001 3 1 2 2 50001 3 1 3 ... 2 50001 3 1 25000 Basically, the idea is that we have a chain of bosses 50,000 employees long, with 500001=>50000=>...=>1, so 1 is the boss of everyone. Then, we have 25,000 documents. Each document we give to employee 50,001 and we ask if it reached employee 1. It seems like you're doing a linear search for each document. So your running time will be on the order of 50,000*25,000 = 1.25 billion operations.
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 Ah, you are correct. For some reason I assumed maximum height of tree as log(N + M).
 » 5 years ago, # | ← Rev. 2 →   +4 I jumped to exactly 1700 in this contest. Now it appears that I am in some sort of bizarre limbo... [UPD: Fixed now, as add1ctus said.]
•  » » 5 years ago, # ^ |   +6 You are a candidate master, but it seems that worse broke the rating system by getting negative rating (thus not fitting into the 0 — 1199 gray rank, but in a new color — white). Hopefully once it gets fixed you will be promoted to candidate master.
•  » » » 5 years ago, # ^ |   0 I see, thanks!
 » 5 years ago, # |   +8 It seems, there is a bug in standings table: purple participant is impossible for Div.2.
•  » » 5 years ago, # ^ |   0 There is a bug with the rating/rank system. He had 1472 rating before Round #266 and got promoted to purple after the competition. Check his profile.
 » 5 years ago, # |   +4 What happened to phantom11's country-wise standings?
 » 5 years ago, # |   0 I couldnt understand the concept to B. Anyone?
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 If a >= sqrt(6n) and b >= sqrt(6n), then a*b >= 6n; in this case, do nothing. Let a be the smaller of the two input numbers, and b be the larger of the two.One trivial solution is to increase b until the room is big enough. E.g. if a = 10, b = 11, 6n = 1001 (somehow): then the trivial solution is 10*101 = 1010. Then your "overflow" is at most a, which as we said was <= sqrt(6n). Let TRIVIAL be the value of this trivial solution, i.e. in this case, 1010.Therefore, the optimal solution has "overflow" at most a. Suppose that the optimal solution is x*y, with x <= y (WLOG). Then x <= sqrt(6n) + 1, because otherwise, x*y > (sqrt(6n)+1)*(sqrt(6n)+1) >= 6n + 2sqrt(6n) > 6n + a >= TRIVIAL, therefore the solution was non-optimal.What we have shown is: you are guaranteed that an optimal solution exists with at least the smaller number being less than sqrt(6n). It is possible that one of the two is larger, though, e.g. 1*6n = 6n. However, your goal is only to find the smaller number, through the following method.Fix w between 1 and sqrt(6n). For every w, let h be the smallest integer s.t. w*h >= 6n, i.e. h = ceil(6n/w). Keep track of the best value you've found so far. Then, you iterate through sqrt(6n) < 10^5 possible values of w, and for every such w, your computation is constant time, so your algorithm is linear in sqrt(6n).
 » 5 years ago, # |   0 Here is my code : http://codeforces.ru/contest/466/submission/7796449 In my computer and ideone.com http://ideone.com/6lt8wR it runned test 1 and give me 4 but on codeforces it give me 0 ??? Who can explain me ??
•  » » 4 years ago, # ^ |   0 Similar is happening with me too. My submission gives answer as 2041 for input test case 2. However on ideone and my local compiler, answer is 1.