Hello Codeforces!

I would like to invite you to Codeforces Round #417 that will take place tomorrow on June 1st, 2017 at 17:05 MSK.

This is my first round. Great thanks to KAN for his efforts and help in the round preparation, mike_live and 300iq for testing the problems, and MikeMirzayanov for the awesome Codeforces and Polygon platforms.

The round is rated for the second division. Participants from the first division can take part out of competition. As usual, the participants will be given 5 problems and two hours to solve them.

I hope you will find the problems challenging and interesting!

UPD 1: Scoring disrtibution: 500 — 1000 — 1500 — 2000 — 2500.

UPD 2: Due to a technical issue, the contest is delayed by 10 minutes.

UPD 3: Contest is over. Congratulations to the winners!

Div2 Winners:

Div1 Winners:

UPD 4: Editorial

• +361

 » 5 years ago, # |   -26 After JBMO TST (Junior Balkan Mathematics Olympiad Team Selection Test) I will participate in that contest. Hope short and interesting statements :DGood luck!
•  » » 5 years ago, # ^ |   0 Hey, i see you're from Azerbaijan, will you participate in EJOY this year? You're a junior right?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +3 as i am your suffix :D i wish you best of luck in both contests and happy coding
 » 5 years ago, # |   -6 Thank you for preparing the contest and I wish that it will be a nice contest with interesting problems.BTW I'm curious to know how the problem-setter is an Egyptian while the testers are Russians ? :D
•  » » 5 years ago, # ^ |   +190 Because this is Codeforces community :)
 » 5 years ago, # | ← Rev. 2 →   +2 Why this blog is not seen in the home page?
•  » » 5 years ago, # ^ |   +41 now it appears
 » 5 years ago, # |   +17 You did really well in the WF, so we must be expecting some interesting tasks :D
•  » » 5 years ago, # ^ |   +7 how well did he do?
•  » » » 5 years ago, # ^ |   +22 His team is the Africa and middle east region leader with 57th place solving 4 problems
 » 5 years ago, # |   +1 No character ? It seems to have short statements :DD
•  » » 5 years ago, # ^ |   +49 Hmmm. there is a character actually :D
•  » » » 5 years ago, # ^ |   +5 and what is her/his name ? :D
 » 5 years ago, # |   +57 That will be my birthday. Can I lose 6 points off my rating before the contest as a birthday gift? So that it can be rated for me. :D
•  » » 5 years ago, # ^ |   +53 You can participate unofficially, take the first place and that will be a better gift :D
•  » » » 5 years ago, # ^ |   +26 We both know that I can't get the first place in the unofficial round. :D
 » 5 years ago, # |   +22 By the way, the time link in your post is wrong, it says 5:05 am MSK (it should be pm).
•  » » 5 years ago, # ^ |   +8 fixed
 » 5 years ago, # | ← Rev. 8 →   0 What about a "Rated" Div 1 contest?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +2 Edit Due to Your Edit : it's only Div 2 Contest.
 » 5 years ago, # | ← Rev. 3 →   +1 The link for the time of the contest in the "Contests" tab redirects to World Clock instead of the actual event timer.
•  » » 5 years ago, # ^ |   0 I think it is fixed now.
 » 5 years ago, # |   +21 It seems that codeforces system automaticaly unregistered some people that had been registered earlier!
•  » » 5 years ago, # ^ |   +6 I've been unregistered twice already...
 » 5 years ago, # |   +9 Good luck everyone! Shameless Promotion: I have developed a cli tool to ease problem testing during contests (for newbies like me) you can read about it here. http://codeforces.com/blog/entry/52234
•  » » 5 years ago, # ^ | ← Rev. 4 →   +5 if you click on the time of the contest ... you will be redirected to this World Clock... there you can find your time zone
 » 5 years ago, # |   0 hey, it's 14.05 here and the contest is not live yet.I also got mail related to unusual start time .Why isn't it start yet?? Pls, fixx this problem ...I already miss two contest due to this:((
•  » » 5 years ago, # ^ |   0 Go to this link and check how much time left.
•  » » » 5 years ago, # ^ |   0 I know about how much time left. I was saying about mail from codeforces saying that contest start time 14.05
•  » » » » 5 years ago, # ^ |   +5 That is the time in UTC.
•  » » » » » 5 years ago, # ^ |   0 ohh..sorry I missed that info
 » 5 years ago, # |   -9 If you know what I mean "XOR" everything :D :""D
 » 5 years ago, # |   0 Proud of you man :D Ahmad_Elsagheer from the GUC.
 » 5 years ago, # |   0 Looking forward to it :)
 » 5 years ago, # |   0 Proud to hear that the Problems setter is an Arabe one and especialy Egyptian:D
 » 5 years ago, # |   +12 Is site working slow for all? or Is it just my network?
•  » » 5 years ago, # ^ |   0 I think site is slow now . :/
•  » » 5 years ago, # ^ |   +3 Hope that it's not slow during contest.
 » 5 years ago, # |   +9 Something weird things happens in Codeforces.. It unregistered me...
•  » » 5 years ago, # ^ |   +8 Please, check again.
•  » » » 5 years ago, # ^ |   +1 Thanks, it is fixed.
 » 5 years ago, # |   0 Delayed by 10 minutes :o
 » 5 years ago, # |   0 delayed by 10 mins :P
 » 5 years ago, # |   +51 It won't be a normal Codeforces round if it is not delayed :)
 » 5 years ago, # |   0 It's been so long since the last time I have seen the score distribution BEFORE the contest.GL & HF everyone.:)
 » 5 years ago, # |   -16 Due to a technical issue, the contest is delayed by 10 minutes.
 » 5 years ago, # |   +15 Please, Don't delay the contest more than 20 min because of maghreb Prayer " E7na saymen y3ne" :"D
•  » » 5 years ago, # ^ |   0 even no more than 10 minutes :(
•  » » 5 years ago, # ^ |   0 we already completed maghreb in Bangladesh. But it is very near to Esha prayer and tarabi. If anyone want to participate in contest,he will miss the both esha and tarabi prayer.
•  » » 5 years ago, # ^ |   -29 lsa bdri 3la elm8reb ya 3m :D
•  » » » 5 years ago, # ^ |   -20 mho kol 4wya y25roha kda m4 hnfter :"D
•  » » » » 5 years ago, # ^ |   -14 masri zaina y25rha zai mahwa 3ayez :D
•  » » » » » 5 years ago, # ^ |   -13 aywa mho m4 da5el el contest hyfter bra7to :"Dma4y Ya Sagher :"D
 » 5 years ago, # |   +1 It's very exciting!!! Good luck to myself
 » 5 years ago, # | ← Rev. 3 →   +1 I wish i had a time machine! Time+=10minutes
 » 5 years ago, # |   -10 It shows registration is completed still the number of users registered are increasing??
 » 5 years ago, # |   0 Time is delayed. I cannot compete for taraweeh. :(
 » 5 years ago, # |   0 Hope this round will be interesting!
 » 5 years ago, # | ← Rev. 2 →   -30 .
»
5 years ago, # |
-36

Polite Enquiry, Looks like after january , codeforces has lost it's original Rounds, after appointing KAN as the co-ordinator, CSAcadmey is doing good in preparing problems of homogenous/regular difficulties.

# CF ROUND GOING TOO IRREGULAR

•  » » 5 years ago, # ^ |   +10 I don't know if this fact is related to KAN becoming coordinator, but it is a fact indeed. We should have increasing scores to match increasing difficulties; and this rule hasn't been true recently...
 » 5 years ago, # |   +15 Very strange scoring distribution / problem ordering
 » 5 years ago, # |   +2 Many hacks in A
•  » » 5 years ago, # ^ |   +3 I know , right.I never did any hacks before, and in this contests, I hacked 4 times in this problem alone.Lucky that I have same way of thinking with the problem-setter :v
 » 5 years ago, # | ← Rev. 3 →   +5 I don't why for the 3rd question, I was solving a[xj]+(i*xj) where i is the index of the chosen array element in the k chosen element(i ranges from 1..k). Took me by surprise looking at the increasing number of submissions. Wasted so much time over it :( PS: Can anybody tell me how to solve the question i thought C was
•  » » 5 years ago, # ^ |   +1 binary search on k
•  » » » 5 years ago, # ^ |   0 Can you describe the solution, I am asking a question different from C here
•  » » 5 years ago, # ^ |   0 I solved it with binary search (binary search for k), but I'm also wondering if there's a nice(r) way of solving it. A lot of people solve it quickly but maybe I was just slow seeing binary search.
•  » » 5 years ago, # ^ |   +1 I thought that there is some clever DP, but it was a about simple binary search.We binary search k — the number of items we pick and recalculate all of the costs of all of the n items. Then we sort them and take k lowest items.The complexity is O(n·log2(n))
•  » » » 5 years ago, # ^ |   0 I eventually did solve using the same method. I am asking a different question. All the indexes are not multiplied by k. They are multiplied by 1..k depending on the position
•  » » » » 5 years ago, # ^ |   0 All the indexes are not multiplied by k. They are multiplied by 1..k depending on the position What? I don't understand.
•  » » » » » 5 years ago, # ^ |   0 You are selecting k indexes. Let the indexes be x1,x2,x3..xk and so on. The question asks (a[x1]+k*x1)+(a[x2]+k*x2)... I am asking (a[x1]+1*x1)+(a[x2]+2*x2)....
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +1 why O(n*log(n)*log(n))? i think that O(n*log(n)*log(1260))
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 If f(n) = n·log(n)·log(1260) then f(n)O(n·log2(n)) To be serious, I didn't bother with calculating upper bound for k. So, my algorithm depends on n in a logarithmic way. Otherwise you can freely consider this algorithm having a linear complexity — the nature of codeforces bounds tells us that logarithms will not exceed the value 30.
•  » » 5 years ago, # ^ |   0 I was solving problem same way)
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I think there's no really efficient way to solve it. Use this: http://codeforces.com/blog/entry/52240?#comment-363783. Using this, you need to prove that the cost of getting k elements disregarding the base cost is O(k^3) and then the maximum number of elements will be O(S^(1/3)), I think that the best way to get the elements on this problem is from the right to the left (you need to prove this as well). Now, do a dp (a simple knapsack with some modifications) and the complexity will be O(S^(1/3) * n), O(S^(1/3) + n) in memory. Tip for proving the first part: the minimum cost will use always the first k numbers, if you consider that the second part (right to left) is right, you start from 1 and from there onwards you'll sum the sum of the first k natural numbers, that sum is O(k^2) or k*(k + 1)/2, that results in the O(k^3) bound if the part of right to left is correct.The dp will also include numbers from right to left and then it will have the best answer if all that /\ is proved.
•  » » » 5 years ago, # ^ |   0 Thanks a lot.
 » 5 years ago, # |   +28 Me, reading problem D
 » 5 years ago, # | ← Rev. 2 →   +52 Problem E is just Staircase Nim. Nodes can be classified as two types, the "odd steps" and the "even steps" depending on the parity of their depth. The odd nodes are the ones having parity of depth same as that of leaves. The others are even nodes. Player 1 will lose iff the XOR value of all odd nodes is 0.So, if you swap the value of an even and an odd node, you need to ensure that the resulting XOR value of odd nodes becomes 0.Additionally, if the initial position is losing for player 1, then you can swap any 2 even nodes or any 2 odd nodes too. Code
 » 5 years ago, # |   0 Task A is very good problem for hacking. Task C is easier than B. Task B is above my strength. I thought about brute force, greed with bfs from every rooms where light is on, but it won't work... So, how to solve it?
•  » » 5 years ago, # ^ |   +4 u can use DPDP[x][entrance], minimum steps required to finish floor x..n if u enter floor x from entrance (0 if left, 1 if right)
•  » » 5 years ago, # ^ |   +3 dp
•  » » 5 years ago, # ^ |   +7 I did brute force...
•  » » » 5 years ago, # ^ |   0 1500 rooms makes O((nm)^2) possible. In fact it allows O(2^n*m). Is there an intuitive yet slow solution that is worse than O(mn)?
•  » » » » 5 years ago, # ^ |   0 After finishing a floor, either you take the same stairs or you switch to the other side of the building. 2^(floors-1) <= 2^14 = 16384 possibilities.
•  » » 5 years ago, # ^ |   +3 I used dp for each floor i took leftmost and rightmost position. and either you go to the leftmost part or the rightmost part at each floor till the last one. I am scared of corner cases.
•  » » 5 years ago, # ^ |   +4 I used DP on the minimum amount of time it takes to complete each row and ending in the . left staircase or the right staircase, but there are several annoying things to watch out for, namely the stopping floor (you don't need to continue the dp after this if there's no more lights at higher floors), and the case where there's only one floor.
•  » » 5 years ago, # ^ |   +3 No need to memorize. recursion will pass. Complexity O(3^n*m). It may be less, I am not sure.
•  » » 5 years ago, # ^ |   +3 i think you can just brute force on all the possible stairs combinations in every one of them do greedy in the floor you are in (if you are at the left stairs walk to the last room that is on and vice versa with the right stairs)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +4 I made a dp[i][2] where dp[i][0] is the min time taken when person starts from i^th floor from the left, dp[i][1] for when he starts from right.
•  » » 5 years ago, # ^ |   +3 I solved B by starting from the bottom and going up, and for each floor calculating the minimum number of seconds needed to get to the left stairs and the right stairs. Repeat until all lights are turned off.The minimum number of seconds to turn off all lights and end on the left stairs is equal to min(R+M+1, L+(rm*2)), where R is equal to the number of seconds to get to the right stairs on the floor below this one and L the number of seconds necessary to get to the left stairs below, and rm is equal to the rightmost turned on light, as we will have to walk to the rightmost lamp to turn it off and back to the left stairs. Similarly you can calculate the minimum number of seconds to get to the right stairs.Hope this helps
•  » » 5 years ago, # ^ |   0 I agree that the problem looks like TSP in the beginning, so one is inclined to think of exponential brute-force, but it was mentioned that you need to switch the lights of current floor off before moving up. Therefore you can think of a DP here, just make sure to end the walk on the last floor with lights on.
 » 5 years ago, # |   +18 It seems more like A-C-B-F-D !
 » 5 years ago, # |   0 how to solve C?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Binary search on answer. Put the modified costs of the items (arr[i]+mid*i) in min-priority queue and take top "mid" items to validate the "mid" of the binary search.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +5 Does it pass the TL ? In your solution, it is O(n·log2(n)).
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +6 Yeah, I got AC. O(n*log(n)*log(n)) passes for n = 1e5.Code
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I brute-forced it!! recursed through all the possible cases at all floors. edit:for problem B
•  » » » 5 years ago, # ^ |   +5 I think that this was meant for Problem B. For Problem C, if you brute force through all possible number of items, the algorithm will become O(n^2) and thus TLE.
•  » » » 5 years ago, # ^ |   +5 That's problem B not C.
•  » » 5 years ago, # ^ |   0 You can binary search for the answer. To check if you can solve the task from a given number of elements, calculate the cost of every item (with the given formula), sort them, summarize the smallest x (where x is the given number you are checking if it's possible) and check if the sum is smaller or equal than S. If it is, then answer will be >= x.
 » 5 years ago, # |   +11 @Ahmad_Elsagheer why such an irregular scoring distribution
•  » » 5 years ago, # ^ | ← Rev. 4 →   +17 The swap between B and C is strange a little bit. Regardless of implementation and easy greedy problems, I believe that brute force should always be the simplest among others, as you exert no effort thinking about the optimal solution, you just try everything in the search space. That is the first thing I learned in competitive programming "brute force". I found that people always underestimate brute force (specially backtracking) solutions, however, a participant who can solve B efficiently should be able to solve it (DP solutin is not intended of course so n ≤ 15). I think the main problem is that people who started their competitive journey from Codeforces problems only didn't face such brute force problems a lot, because most of the problems will need simple nested loops.Regarding D and E. If I found these two problems when I was Expert, I would have solved D only. In problem E, this variant is not an easy one to think about if you know only standard nim game. If you find it easy, then you are brilliant, but D should be easier. The point with problem D is the modelling part. It needs careful reading as it has many conditions. It's the deadlock problem but with conditions to make it on a tree not a general directed graph. People who gave it a try but didn't solve it told me they thought it was a DAG not a tree. Reading the statement over and over again, I found written "No child can request a toy while waiting for another". This implies that each node has at most one outgoing edge. So, the DAG now becomes a tree! If anyone could figure this out, it can be written in 10 mins.In conclusion, this is not the standard Codeforces problem style. You can go through the gym and check the problems there. Your find different regional contests and training camps. Each of those has its own style. However, knowledge and experience required to solve the problems at the end is the same.
•  » » 5 years ago, # ^ |   +11 As an author, you always try to make a good contest by making a gap between problems. However, this gap is not always clear when you write the problems yourself specially when it is a new experience. I hope next time it will be better. But you can't always make all people satisfied. It's life, man.
 » 5 years ago, # |   0 Is there short solution for B?
•  » » 5 years ago, # ^ |   0 I did Brute Force, u know, because of the small limitations. It's already quite short for me.I'm afraid if i use shorter algorithm (e.g. greedy), I might got WA :v
•  » » » 5 years ago, # ^ |   0 Maybe i've messed something up.. My brute force code was about 130 lines and it got WA...
•  » » » » 5 years ago, # ^ |   0 Well, I also got WA once from my first BF solution. I was just lucky to see what my mistake is before the contest ended. You already have the basic idea, it's a good start !
•  » » » 5 years ago, # ^ |   0 I thought that brute force would take longer to implement and I couldn't think of a case where O(n) approach would fail... got WA :(Guess I was just too greedy
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 DP[i][0/1]:Sagheer now at floor i's left/right stair, takes minimum time to close the lights from floor 1 to floor i. DP[i][0] = min(DP[i-1][0] + (distance from left stair to the rightmost light)*2, DP[i-1][1] + m+1); DP[i][0] = min(DP[i-1][0] + m+1, DP[i-1][1] + (distance from right stair to the leftmost light)*2);I passed the System Test.
•  » » 5 years ago, # ^ |   0 i thought it was a greedy problem. you should notice if a line is all zero, and there are lights need to turn off above it, in this case, just ignore this line, and move up by 1 step
•  » » » 5 years ago, # ^ |   0 I am wrong. B is a DP problem, not greedy.
 » 5 years ago, # |   -10 Ordering should be A — C — B — E — D!
 » 5 years ago, # |   +69 To me A was the hardest among A, B, C, E, as I still don't get what the problem is saying till now.......
•  » » 5 years ago, # ^ |   +27 I can't understand A too, I just submitted some shit looking at the picture and it got hacked :(
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +17 I got hacked twice and I still don't know whether my current submission is correct.UPD : Wow it passed.
•  » » » 5 years ago, # ^ |   +36 i submitted some shit and it got hacked then i added more shit and it passed
•  » » » » 5 years ago, # ^ |   0 And it's failed on system tests.
•  » » » » » 5 years ago, # ^ |   +73 I guess i should have added more shit
•  » » 5 years ago, # ^ |   0 I think say signal p for road 1 is green. So if opposite to it(road 3) signal straight is on accident will happen. If 2 left or 4 right is on accident. Also if any of the signals of street 1 is on it will be accident;
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Anyone who submitted 1st quickly and were happy and then got hacked?
•  » » 5 years ago, # ^ |   0 totally agreed
•  » » 5 years ago, # ^ |   0 hope my submission can help you ;) http://codeforces.com/contest/812/submission/27489624
 » 5 years ago, # |   +4 Will simple recursion without dp pass TL in B?
•  » » 5 years ago, # ^ |   0 I did it and it passed pretest. It runs in O(2^n) time, if you check every scenarios, and 2^15=32768 so it should pass without problem. On pretests it did 15 ms.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 I thought about this aproach but it seems to me it's not enough. Near the end you may want skip floor, go upstairs, go through whole floor, then go downstairs and turn off light in last room near that stairs. e.g. 1111111 1000001 
•  » » » » 5 years ago, # ^ |   0 No."He wants to turn all the lights off in such a way that he will not go upstairs until all lights in the floor he is standing at are off"
•  » » » » » 5 years ago, # ^ |   0 omg, I missed this statement. ******
•  » » » » » 5 years ago, # ^ |   0 Totally forgot about this thing.
•  » » » 5 years ago, # ^ |   +3 Yes, it passed! :)
 » 5 years ago, # |   0 For A,a guy in my room was printing "Yes" instead of "YES",did the same for "NO" too. Tried hacking and failed. Isn't printing "YES" and "Yes" different?
•  » » 5 years ago, # ^ |   +13 but since it passed the pretests, they probably allowed that too.
•  » » » 5 years ago, # ^ |   0 I don't see a reason to do that.
•  » » » » 5 years ago, # ^ |   +3 It's a feature of the default yes/no checker, the checker is case insensitive.
•  » » 5 years ago, # ^ |   0 If the problemsetter is using the standard yes/no-checker for the problem, they are the same.
•  » » 5 years ago, # ^ |   0 Depends on the checker
•  » » 5 years ago, # ^ |   +8 Maybe he redefine "Yes" to "YES" :).
•  » » 5 years ago, # ^ |   +5 When you try to hack someone, at the bottom there is a text above the "HACK" button with a text like this: Attention: The checker does not consider whitespaces and isn't casesensitive, so yes/YES, and no//NO is both accepted.
 » 5 years ago, # |   -8 Damn problem A is really my favorite problem of ALL time ! I did my really first hacks (4 hacks in this contest) in this problem alone.I'm really sorry for my friends in my room that got hacked by me.for me the problem explanation is really clear. Easy problem, but people might misread the explanation.
•  » » 5 years ago, # ^ |   +18 In case you don't hack them, them will fail system test instead. But if you hack them, you give them a chance to pass system test :)
•  » » » 5 years ago, # ^ |   +6 yea I thought that way, too. Hope the ones that got hacked have as positive thinking as you :v
•  » » 5 years ago, # ^ |   +3 Why sorry? you have saved them from failed system test, so they could submit again and get positive score instead of 0. :P
•  » » » 5 years ago, # ^ |   0 Well , I hacked them really in the ending of the contest (like around 10 minutes) before the contest ended. So, they might not get time to think :v (alas, frustration from hacks)anyway , positive thinking , right.
•  » » » » 5 years ago, # ^ |   +5 When I have been hacked in A, just few more second to fix that stupid mistake, so 10 min is too long since.
•  » » 5 years ago, # ^ |   0 Whoa, didn't expect that much downvotes. nonetheless, I believe the problemsetter had tried his best to make the problem explanation as clearly as possible.Well, everyone may have different opinions.
 » 5 years ago, # |   0 what was pretest 6 in C? :'(
•  » » 5 years ago, # ^ |   0 i got WA 3 times at this test
•  » » » 5 years ago, # ^ |   0 I got WA too on that test.
•  » » 5 years ago, # ^ |   0 Probably you were sorting the given array without taking care of the initial indices for each value I got 2 WA in that test before the Announcement with clarification :(
 » 5 years ago, # |   +4 That feeling when you submit A and get pretests passed and right after there's a sudden power outage... Bye bye rating.
 » 5 years ago, # |   +20 I'll maybe get downvotes for saying this but I really did not enjoy this contest. The problems were not interesting to solve — just extremely annoying.
 » 5 years ago, # |   0 test 6 in problem E ?
•  » » 5 years ago, # ^ |   +5 The case when the first player has a loosing strategy without any swapping.
 » 5 years ago, # |   +4 I understood problem A only after reading it 5-6 times...
•  » » 5 years ago, # ^ |   +1 me too , moved to C instead , but again ambiguity , very confusing this time!!
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 same here i moved to C instead
 » 5 years ago, # |   +9 The problems weren't ordered by their difficulty, were they ?
•  » » 5 years ago, # ^ |   0 I guess they should be because of the score distribution.
 » 5 years ago, # | ← Rev. 2 →   0 The queue of submissions in the end was long. I submitted 7 minutes before and the it was evaluated after the contest.
 » 5 years ago, # |   +11 Solving B first was an extremely costly decision for me. I should have rather started with C.
•  » » 5 years ago, # ^ |   0 Same here !! To add A got hacked
•  » » » 5 years ago, # ^ |   +9 Mine A got hacked too. It seems not only our handles, but our fates match too :P
•  » » » » 5 years ago, # ^ |   0 Too much I think
•  » » » » » 5 years ago, # ^ |   +3 I thought you were talking to yourself. lol.
 » 5 years ago, # |   +1 I solved C using greedy but failed in TC 6. Any Help please
•  » » 5 years ago, # ^ |   0 It is binary search on maximum number of souvenirs.
•  » » 5 years ago, # ^ |   0 You just calculate price for every souvenir for current k, sort all prices and check if sum of k smallest prices is less or greater than S.
•  » » 5 years ago, # ^ |   0 I think it works in O(nlog(n)log(MAX_NUM_OF_SOUVENIRS))
•  » » » 5 years ago, # ^ |   0 I guess MAX_NUM_OF_SOUVENIRS is n lol.
•  » » » » 5 years ago, # ^ |   0 It is about 1000 i think
•  » » » » » 5 years ago, # ^ | ← Rev. 3 →   0 sorry, I just got confused, and I think it is around sqrt(s).
•  » » » » 5 years ago, # ^ |   0 Minimum sum of k elements is arithmetic progression starting at k and ending at k*k + sum of given prices
•  » » 5 years ago, # ^ |   0 I did binary search but failed on 6.
•  » » » 5 years ago, # ^ |   0 Same was the case with me just check case 1 8 7 ans: 1 8 and 1 7 7 ans:0 0
•  » » » » 5 years ago, # ^ |   0 I was sorting input cost array instead of the calculated cost array. Fixing that got AC.
 » 5 years ago, # |   0 It was not a very good contest at all, though i think problem C is a really nice one.
 » 5 years ago, # |   +3 i think B is harder than C it was a waste of time not to start with C after A
 » 5 years ago, # |   0 What is the hack in problem A?
•  » » 5 years ago, # ^ |   0 some people didnt take union of both casessome thought that accident is dependent on the same road only
 » 5 years ago, # |   +1 It's hard to understand A and D. I guess I should practice English more.That aside, D looks really fun to solve. The other 4 are quite classic (I think), and yet I f*cked up really bad.
 » 5 years ago, # |   +32 812A - Сахир и перекресток worse statement ever !! It needs more description
 » 5 years ago, # |   0 What will be the answer of this test case in 'B' 1 11 01000000010Is it 9 or 4. From what I learnt from the problem statement is that we can move from one stair to another stair on the same floor?
•  » » 5 years ago, # ^ |   +6 Sagheer is standing at the ground floor at the left stairs
 » 5 years ago, # | ← Rev. 2 →   0 Does anyone know why I kept getting WA on Problem C pretest #11 with this code? My idea was to just binary search for the highest k value. On each iteration, I updated the array to the new costs and then sorted and took the k smallest elements.
•  » » 5 years ago, # ^ |   +1 Check line 28. arr[i].second * (k - prevk) can overflow.Replace it with something like arr[i].second * 1LL * (k - prevk).
•  » » » 5 years ago, # ^ |   0 Good catch, thanks!
 » 5 years ago, # |   +2 fainted from reading Problem D at mid night.. :D
 » 5 years ago, # |   +4 Wow , very fast judging :D
 » 5 years ago, # |   0 A bad round for me :( Problem A consumed too much of time, got two hacks! I hate Problem A :(
 » 5 years ago, # | ← Rev. 3 →   +1 By getting hacked on Problem A, I feel that if I (and many others ;) ) were to monitor the configuration of the traffic lights in the real world, so many people will get killed by accident XD On a serious note though, thanks for hacking my solution, cswyyv864. If I didn't get hacked I would've just gotten 0 for it at the end lol
•  » » 5 years ago, # ^ |   +3 good luck bro
•  » » » 5 years ago, # ^ |   0 You too!
 » 5 years ago, # | ← Rev. 2 →   +6 Problem A: ?????this problem destroyed your work on the other probs!!! Bad statement it should have been mentioned that each lane goes to what part -_- my solution got hacked coz I did not concentrate on how the cross road really work :v the rest of the probs are interesting, thanks.
 » 5 years ago, # |   +3 Systesting today is really fast
 » 5 years ago, # |   +25 very bad contest
 » 5 years ago, # |   +19 Sad to see that N^2 log(N) also passes for problem C :(Here, have a look!http://codeforces.com/contest/812/submission/27499338
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I think it is N * sqrt(s) * log(n).
•  » » » 5 years ago, # ^ |   0 Can explain how is it so? Cannot understand it.
•  » » » » 5 years ago, # ^ |   +10 Let's look at the max number of items we can take. In the worst case when every a[i] = 1 and s = 1e9, sum of k items will be k * (k + 1) / 2 ~= k^2, so it is sqrt(1e9) * N * log(N).
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Aha! That is a cheeky way out :P I tried to hack his soln with the same test case as you describe thinking TLE is counted as hack.Nice. Thanks a lot!
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 But shouldn't sqrt(10^9) * N * logN also fail?
•  » » » » » » 5 years ago, # ^ |   0 It's in c++ and it runs on edge(nearly 1800 ms).
•  » » » » » » » 5 years ago, # ^ |   0 Okay, that is sad. Thanks a lot anyway :)
•  » » » » » 5 years ago, # ^ | ← Rev. 3 →   +19 Actually its as ans will be > k*(k*(k+1)/2) for k valuesSo max value is atmost 1259. Still should exceed tle imo, but servers seems very fast.Edit: I tried generating some hacky cases and it looks like it should have tled on strong tests. 27505850 takes over 3000ms on custom invocation even if rand() calls are unaccounted forProbably all main tests having N = 10**5 have almost all values sorted. So sorting takes O(n) time only.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 nvm
•  » » » » 5 years ago, # ^ |   0 He is sorting the array for each array iteration.So, sort takes NlogN * (no. of iterations), which happens to be at max sqrt(N) for N = 10^5. So, its N*sqrt(N)*logN for larger N.
•  » » » » » 5 years ago, # ^ |   0 Yeah, you're right
•  » » 5 years ago, # ^ |   0 what's wrong with that complexity ? Log(100000)^2 x 100000 is barely over 25 Million and that passes in under a second!
•  » » » 5 years ago, # ^ |   0 It is not N (logN) (logN) I guess. It is N*N*logN
•  » » » » 5 years ago, # ^ |   0 Oh sorry i read your first comment wrong there for i didn't see the code :)
•  » » » 5 years ago, # ^ |   0 Yes,just as lohit_97 says,this code used iteration on the number of purchased goods instead of binary search.So it's not the intended solution.
•  » » 5 years ago, # ^ |   0 He used the fact that
•  » » » 5 years ago, # ^ |   0 Yes I understood that, but then that passes on edge time limit, I guess that was not the intended solution. But yeah, anyway, it passed.
 » 5 years ago, # |   +63 I swear I'll never underestimate Div2-A again...
 » 5 years ago, # |   +123 One of those contests where you think you want to ask for a clarification but don't even know where to start.
 » 5 years ago, # |   0 Compiled E, just 1 sec before contest ended. Hope I don't get AC later.
 » 5 years ago, # |   +40 This guy literally crushed all the pedestrians xD
•  » » 20 months ago, # ^ |   0 lmao
 » 5 years ago, # |   +54 you got this...
•  » » 5 years ago, # ^ |   +3 even after solving all !!! :P
 » 5 years ago, # |   +15 Problem statements were very unclear! One reading was not sufficient at all :(
 » 5 years ago, # |   +3 in C atleast one ex should be given to clearify which index is xi's. i spent 25 minutes figuring out what's wrong
 » 5 years ago, # |   0 Weak pretests for A :|
 » 5 years ago, # |   0 you don't actually need DP to solve B , it's overkill ..... the problem can easily be solved with straight forward Brute Force in a recursive function .... anyway ,thanks for the problem setter i think the problems were nice, keep up the good work!
•  » » 5 years ago, # ^ |   +10 in terms of code length, both approaches are equivalent, i guess. i dont think its overkill
•  » » » 5 years ago, # ^ |   0 sure , but i was talking about the difficultly of the solution because i noticed that C was solved more than B.
 » 5 years ago, # |   0 I couldn't submit any of my solution, either by uploading the code file or by pasting the code in submit window. Did anybody face a similar issue?p.s: the page would just keep on loading and didn't proceed further
 » 5 years ago, # | ← Rev. 3 →   +2 deleted , sorry my mistake :3
•  » » 5 years ago, # ^ |   -6 Input is invalid, should be 3 3 in first line.
•  » » 5 years ago, # ^ |   0 Such input is not possible, since m is the muber of rooms in each floor, so there should bem+2 columns in the input.
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 deleted
 » 5 years ago, # |   +7 Good contest.Although I think the statement for some problems is too long or unclear,the quick system test and quick editorial are worth appreciating.Thank you Ahmad_Elsagheer for preparing the wonderful contest!
 » 5 years ago, # |   0 Everything was simply awesome and superfast. Superfast editorials and superfast result declaration. Impressive and worth appreciation
 » 5 years ago, # |   +18 Solution to Problem D is wrong. Consider the following test case:4 7 9 3 4 5 4 6 4 7 1 1 1 2 2 1 3 2 4 1 4 2 1 5 2 6 3 7The solution gives 4 0 2 as result, which is obviously wrong.
•  » » 5 years ago, # ^ |   +15 this case is invalid because child 4 can't request toy 2 while waiting for toy 1
 » 5 years ago, # |   0 Goddamn, I got WA in B because i accidentally used && in bitmask instead of &, I hate such situations((
•  » » 5 years ago, # ^ |   0 How do you use a bitmask for B?
•  » » » 5 years ago, # ^ |   0 To enumarate binary strings of len n
•  » » » 5 years ago, # ^ |   +1 If in index i there is 0, than I use right ladder to get to floor i + 1, else i use left left one
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 If we encode 0 as choosing left staircase and 1 — right staircase, then we can encode all of the moves as a 15-bit number. for (int state = 0; state < (1 << 16); state++) { int floor = 7; if (state & (1 << floor)) { // Use right staircase on 7'th floor. } else { // Use left staircase on 7'th floor. } } 
•  » » » » 5 years ago, # ^ |   0 Yeah i did the same, but my code ended up to be more than 150 lines...
 » 5 years ago, # |   -31 MikeMirzayanov[user:MikeMirzayanov] please don't give another chance to this question setter
•  » » 5 years ago, # ^ |   +36 What the hell ???I mean this wasn't the greatest round of all time but don't you think you're being too harsh.You are right there were a few problems but the guy did his best and this is his first round cut him some slack will ya ?I think if the statements were clearer and the pretests for A were stronger this would have been a great contest it wasn't that bad.:)
 » 5 years ago, # |   +5 Only neverfirst solved all problems. This is great result!
•  » » 5 years ago, # ^ |   +43 His handle is justified :p Even after solving all problems, 2nd position! :p
 » 5 years ago, # | ← Rev. 2 →   +12 https://ibb.co/bZ5YJF Such proof! Much Wow. xD
 » 5 years ago, # |   0 Can someone explain, why in this test case 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 in problem A jury answer in "NO"?
 » 5 years ago, # |   0 Why does it say I am out of competition? PLEASE EXPLAIN? PLEASE!!!
 » 5 years ago, # |   +7 nice contest
 » 5 years ago, # |   0 I don't get the rating system. Can anyone explain how it works? I solved A task in 36 min and got -22 rating pts. Is it because my solution was sent too late?
•  » » 5 years ago, # ^ |   +5
•  » » » 5 years ago, # ^ |   +5 thanks, missed this
 » 5 years ago, # |   0 I think the statement for some problems is unclear problem A can't understand it till now and these probably be the easiest one corresponding to the Scoring
 » 5 years ago, # |   +24 Well, actually once I was first also alone solving all problems. Someone can post standings for this contest. If there will be +100 I will post it myself.
•  » » 5 years ago, # ^ |   +1 I wanna know why almost coders who's [personal handle/team handle] something like "Loser,neverfirst,..etc" always got high rank and actually becomes "winner,first,..etc"
•  » » » 5 years ago, # ^ |   0 That's the point that I never got first place at some valuable olympiad.
•  » » » » 5 years ago, # ^ |   0 Never means never.You should have a nickname SometimesNotFirst.
 » 5 years ago, # |   -14 Mike mirzayanovCF should follow csacademy in terms of problem statements.
 » 5 years ago, # |   0 Unable to submit any question during the contest . And even after contest ended not able to submit .Anyone experienced this ? Also couldn't see friends' submission 2nd page
 » 5 years ago, # | ← Rev. 6 →   0 please consider the following case in problem B 10 10 001110010110 000000000000 011000000010 000000011000 001010101010 000000000000 000000000000 000000000010 010000000000 000010000000 the code which you posted here http://codeforces.com/blog/entry/52318gives an answer of 73 while it could be just 61 using the above inputs you can check the code you wrote and it gives 73 using the following sequence by following the shortest path and using only stairs for moving up and down shows how it could be possible for just 61  0 0 (11) (12) (13) 0 0 (14) 0 (15) (16) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ( 9) (10) 0 0 0 0 0 0 0 (17) 0 0 0 0 0 0 0 0 (19) (18) 0 0 0 0 0 ( 8) 0 ( 7) 0 ( 6) 0 ( 5) 0 ( 4) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ( 3) 0 0 ( 1) 0 0 0 0 0 0 0 0 0 0 ( 0) 0 0 0 ( 2) 0 0 0 0 0 0 0 `this case i made randomly to check my algorithm and to check wether it provides a right answer like yours or not and please correct any pretest that have this mistake -If it was a mistake- and maybe I am wrong if so please enlighten me
•  » » 5 years ago, # ^ |   +6 "He wants to turn all the lights off in such a way that he will not go upstairs until all lights in the floor he is standing at are off."Your solution goes to the second floor before turning off all the lights on the first floor.
•  » » » 5 years ago, # ^ |   0 I think then i should delete my commentThank you very much :D
•  » » » » 5 years ago, # ^ |   0 Oh actually I can't delete my comment after 2 minutes :3 :3
 » 5 years ago, # |   0 Can't problem C be solved by using DP? my initial thought was that it can be !!
•  » » 5 years ago, # ^ |   0 I don't think it has a DP solution, because the costs used to find the optimal value depends on the optimal value itself.
 » 5 years ago, # |   -32 Hi, very nice post. Gmail Helpline Number UKGmail Contact Number UK
 » 5 years ago, # |   +1 and (( neverfirst )) won the second place :)
 » 5 years ago, # |   -23 Great post. Adobe Support Number UK
 » 5 years ago, # | ← Rev. 2 →   0 in binary search, I have this codehttp://ideone.com/w1wKtqI had an infinity loop at r=3, l=2, at this time, k=2 , suppose that temp<=s , l=2 , how can I avoid it , thanks first .
•  » » 5 years ago, # ^ |   0 programmers check us out\ very helpful for programmer's
 » 5 years ago, # |   0 Hi guys, a short question on B.Sagheer, the Hausmeister... should we provide some check/procedure which checks whether the user intentionally/by accident typed 1 in the position of the stairs and yields for an error/try again kind of scenario?
 » 8 months ago, # |   0 4 33 4 3 2 1the answer of this test case is 27 can any one explore it to me how it is not 24