### AndreySergunin's blog

By AndreySergunin, 7 years ago, translation,

Hello, Codeforces.

Soon, on 27 june at 17:00 MSK regular, 310-th Codeforces round will take place. Problems have been prepared by me, Andrey Sergunin, and Egor Shcherbin (Lord_F).

We want to thank Max Akhmedov (Zlobober) for helping us preparing the contest, Maria Belova (Delinur) for translating statements in English and Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon systems.

Participants will be given five problems and two hours to solve them. Scoring will be announced later.

Good luck everyone!

This round will use the dynamic scoring.

UPD: Due to technical reasons round is delayed by 10 minutes.

UPD: The preliminary version of an editorial was posted.

UPD: Congratulation to the winners:

Div 1

Div 2

• +392

 » 7 years ago, # |   +47 Thanks for the schedule change!Looks like my ranting served its purpose :)
•  » » 7 years ago, # ^ |   +34 Hey! Why the downvotes ?????????I'm happy because we'll have another contest tomorrow and it's at a different time than usual. The other day I was complaining because contests are always 19:30 MST, so now I'm thanking for the schedule change.
•  » » » 7 years ago, # ^ |   +1 I assumed the time was as usual and couldn't compete. I guess I'm going to have to check each time now.
 » 7 years ago, # |   +14 Your curve is very inspiring :))
•  » » 7 years ago, # ^ |   -14 Yes, how do they do this !
•  » » » 7 years ago, # ^ |   -6 By practicing everyday and not wasting your life for something unimportant.
 » 7 years ago, # | ← Rev. 2 →   -42 Consecutive Div1 + Div2 Contest :D
 » 7 years ago, # |   0 Good luck all, hope a good rating for all.
 » 7 years ago, # |   +10 Finally a contest on a day off from work! There isn't a better way to enjoy my free time! Great ratings for all!
 » 7 years ago, # |   +34 I have been waiting for an early contest (10pm in my timezone) for so long, thank you very much XD
•  » » 7 years ago, # ^ |   +6 +1. It's my timezone too. As well as 24% of the world's population. Here, recent Codeforces rounds typically start at 00:30 and end at 2:30 am. I find that in the middle of the night I can write code reasonably well, but seeing the solution to a problem is very hard, even for problems I find easy in the daytime.I'm not complaining, because I think it's exactly right that Codeforces should optimise contest timing for the western Russia community, as a first priority. 19:30 in Moscow seems good if it encourages having an early supper, which is healthy :) For some odd reason, however, TopCoder contests don't cater for Americans very well, because they also run most frequently in the middle of the night in my timezone. It might be because (a) there are some cultural differences, or (b) empirically this time maximises participation.
 » 7 years ago, # |   -23 please provide link to ur past problems if u have written any.
 » 7 years ago, # |   +22 Not a great time for some muslim coders that keep post. Contest is intersecting with iftar time:( In Tajikistan we can enjoy only one hour of contest.
•  » » 7 years ago, # ^ |   +5 i'm agree with you
•  » » 7 years ago, # ^ | ← Rev. 2 →   +30 for me this time is just perfect, before three days because of the round #309 I had to delay my iftar time(eating time after fasting) by 1 hour and a half in order to participate in that round.and also as clearly we can see most comments in this blog liked this time change so I think administrators really need to consider using various usual times instead of one usual time, that helped a lot of coders even if the times are not far from each other (like this one it's only 2 hours and a half different from the usual time)
•  » » » 7 years ago, # ^ |   +6 Same here from Jordan, Ramadan Kareem :D
•  » » » 7 years ago, # ^ |   0 Same here in Egypt :D
•  » » 7 years ago, # ^ |   0 I agree with you brother.
 » 7 years ago, # |   +46 Great time for Korea! It used to be 01:30-03:30, but today it's 23:00-01:00. I(and many) always wanted this...
 » 7 years ago, # | ← Rev. 16 →   -33 i wish all of you have great contest
•  » » 7 years ago, # ^ |   0 Good for some, not good for others. This will always be the case.But at least it's different than usual, which means a chance to participate for coders who usually can't take part in contests due to intersection with work/school/etc..With varied schedules, if you can't take a particular context, you may be able to take the next one.
•  » » » 7 years ago, # ^ |   -10 yes i did't think about other timezone sorry!!! :)
•  » » 7 years ago, # ^ | ← Rev. 2 →   +8 why downvotes ...
 » 7 years ago, # |   +4 It clashes with Challenge24...
•  » » 7 years ago, # ^ |   +14 I think we all know where is must to participate. :)
 » 7 years ago, # |   -63 مینداختی بعد افطار دیگه
•  » » 7 years ago, # ^ |   -9 time is not good
 » 7 years ago, # |   +6 it will be my 6th contest as a Div — 1 contestant . All my previous five attempt was so pleasant that i kick out to Div — 2 everytime :p i hope this time i will survive :D
•  » » 7 years ago, # ^ |   +2 just solve first problem quickly(or at least not very late) and your rating will raise
•  » » » 7 years ago, # ^ |   +1 Easier said than done (For new candidate masters!) :D
•  » » 7 years ago, # ^ |   +2 shakil_AUST your graph is really inspiring. :) Best of Luck
•  » » 7 years ago, # ^ |   +1 Well i hope if i able to come Div — 1 again that time i will try my best to survive Div — 1 :D thank you for supporting :D
 » 7 years ago, # |   -8 It's a good time to start the competition.
 » 7 years ago, # |   -53 It's a bad time for muslim users
•  » » 7 years ago, # ^ |   -21 it's not too bad for us ... and it's not bad to changing schedule because previous time is not good for all timezone and diversity is good :-)
 » 7 years ago, # | ← Rev. 3 →   +6 01010100011010000110000101101110011010110010000001111001011011110111010100100000001100010011011000100000
 » 7 years ago, # |   -54 Previous time is better .... plz re-schedule the time if possible
•  » » 7 years ago, # ^ | ← Rev. 3 →   -24 sometime change is good I guess.
 » 7 years ago, # |   -71 don't want a maths contest this time :P
 » 7 years ago, # |   0 I think it's better time than last contest because of Iranian Users can have better concentration for contest and have better performance. 21:00 in Iran or 19:30 in Russia is in Iran time for eating. thanks for time and person who changed the time of contest. good luck>
 » 7 years ago, # | ← Rev. 2 →   -18 So any body know wich kind of problems AndreySergunin usually gives (graph , math , dp ... ) ??
•  » » 7 years ago, # ^ |   +65 Usually he doesn't give problems cuz it's his first round, btw. Let's wish AndreySergunin and Lord_F good luck!
•  » » » 7 years ago, # ^ |   -20 Thank you mister sherlock . Btw Lewin prepared his first round last time but he was preapring problems in topcoder so peoples have previous idea about what he post .
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 U r welcome, Dr.Watson :) I can almost certainly say that they didn't prepare TC rounds either
 » 7 years ago, # | ← Rev. 5 →   -22 Waiting for the contest.
•  » » 7 years ago, # ^ |   -8 First image has the best size :-|
•  » » » 7 years ago, # ^ | ← Rev. 2 →   -9 Oh i see.
 » 7 years ago, # |   -47 I hope there aren't math problems.
•  » » 7 years ago, # ^ | ← Rev. 3 →   -22 :-|Why?All of computer engineer love math problem .
•  » » » 7 years ago, # ^ |   +14 it is not because i dont like math, i just like data structures, sqrt decomposition , graph theory more.
•  » » » 7 years ago, # ^ |   -14 嗨
•  » » 7 years ago, # ^ |   +13 Maths problems is sometimes interesting(brainstorm). But too many maths problems will make my brain feel tired.
•  » » » 7 years ago, # ^ |   -13 i think that the best programming contest are those wich involve lots of math !
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +26 But you are mathlover D: D:
•  » » » 7 years ago, # ^ |   +8 I with Kronecker made math-only contest, but Zlobober unfortunately rejected it.
•  » » » » 7 years ago, # ^ |   0 Because most of people don't like maths problems, which seems boring in their eyes.
•  » » » 7 years ago, # ^ |   +3 Math makes mathlover Tired.
•  » » » » 7 years ago, # ^ |   0 During this contest, I am struggled with div1C. I tried to solve it with two segment trees... However, I have never played with segment trees for months... At last I failed... I think I should train my data structure skill.
 » 7 years ago, # |   -13 I wish I will have a better rating,Thank you very much.
 » 7 years ago, # |   +3 nice time，Hope I can go to div1
•  » » 7 years ago, # ^ |   -16 bad time , Hope I can return to div2
•  » » » 7 years ago, # ^ |   0 if You want you can ...
•  » » » 7 years ago, # ^ |   +2 is this a joke???
•  » » » » 7 years ago, # ^ |   0 ooom myabe
•  » » » » 7 years ago, # ^ |   0 nope!!! i believe it
•  » » » » » 7 years ago, # ^ |   0 You are crazy
•  » » » » » » 7 years ago, # ^ |   0 TNX :)
 » 7 years ago, # |   0 Do you guys use information from the scoring?
•  » » 7 years ago, # ^ |   0 No，I don't use it,I only sovle problem by their order
 » 7 years ago, # |   +5 delayed by 10 mins :(
 » 7 years ago, # |   0 It's delayed for 10 mins ):
 » 7 years ago, # |   +61 10 min delay again
 » 7 years ago, # |   -42 tired of being last in contribution; upvote me plz
•  » » 7 years ago, # ^ |   0 You have some really very funny blogs :) I can't stop laughing :D :DBut 1-2 blogs are really nice :)
 » 7 years ago, # |   +87
 » 7 years ago, # |   -13 scoring ??!
•  » » 7 years ago, # ^ |   0 Dynamic
•  » » » 7 years ago, # ^ |   -8 thanks
 » 7 years ago, # |   +10 This Time Is Better For Contests ..
•  » » 7 years ago, # ^ |   0 Yes
 » 7 years ago, # |   +3 UPD: Due to technical reasons round is delayed by 10 minutes. it seems that another chance for authors to delay score distribution :D
•  » » 7 years ago, # ^ |   +11 Even though there is nothing about score distribution in English version of the post, the Russian version of it says that the score distribution will be dynamic.
 » 7 years ago, # |   0 When will the score distribution be announced? I believe it will be before the contest starts.
•  » » 7 years ago, # ^ |   0 It's dynamic
•  » » » 7 years ago, # ^ |   +6 Oh, thank you very much.
 » 7 years ago, # |   +78 I've got nothing against dynamic scoring, but damn those penalties on 250pt problem are harsh..
 » 7 years ago, # |   +37
•  » » 7 years ago, # ^ |   0 what are system tests ?
•  » » » 7 years ago, # ^ |   +4 The test cases that your program executes on after the coding phase is over.
 » 7 years ago, # |   +3 Oh God! Save me from the wrath of system tests...
 » 7 years ago, # |   +101 Changing of description of Div1A was too critical
•  » » 7 years ago, # ^ |   +11 But it was kinda obvious from the start because you can't put A into B if B is in something else in real life too.
•  » » » 7 years ago, # ^ |   +69 By the same argument, it was obvious that you can't take A out of B if B is in something else, but this was explicitly stated in BOLD LETTERS in the statement for some reason.
•  » » » » 7 years ago, # ^ |   0 Well, you're right. I didn't notice that.
•  » » » » 7 years ago, # ^ |   +43 My personal sorry for that place. Using the bold letters here and hoping for a participant's common sence was a huge mistake that led to a such situation that even Russian-speaking contests were confused how the matryoshkas work.
•  » » » 7 years ago, # ^ |   +8
•  » » » » 7 years ago, # ^ |   +19 This is interesting! Aside from that, I know that you know what I meant by saying obvious. This is definitely not something that come to mind first (at least for me).
•  » » » » » 7 years ago, # ^ |   +4 If I know how Matryoshka works, it could be obvious. Unfortunately, I wasn't. In point of view of you, I can understand what you mean saying 'obvious'.
•  » » » » » » 7 years ago, # ^ |   +5 For some reason, I thought it's like different size of cups or buckets, so I was really confused with the restriction. Now that I googled it, it's actually really obvious.
•  » » » 7 years ago, # ^ | ← Rev. 3 →   +9 Don't think it's obvious.When I was thinking about matryoshkas I didn't imagine closed ones, only bottom halves of them. If you're messing around with these toys in real life that way, you definitely can put A into B even if B is already in C, but it is kinda hard to pry out A from B if B is already in C. Pretty consistent with the first version of the problem, isn't?
 » 7 years ago, # |   +56 The Codeforces system is so fair! I tried submitting E at 01:59 and I got no response from the server!
•  » » 7 years ago, # ^ |   +18 D: I submitted mine at 1:59:40, nearly broke my shoulder while running back to my laptop when I realized what a stupid mistake I made.
•  » » » 7 years ago, # ^ |   -11 "nearly broke my shoulder while running back to my laptop" LOL
•  » » » 7 years ago, # ^ |   +3 All that for WA 54 =(
•  » » 7 years ago, # ^ |   0 Me too :/ soo unfair
 » 7 years ago, # | ← Rev. 4 →   +2 Any suggestions on how to solve Div2 D / Div1 B?EDIT: I sorted the bridges in ascending order. I did the same with distance between each adjacent island, keeping track of the minimum and maximum length allowed.
•  » » 7 years ago, # ^ |   0 I think this will be the approach though i got runtime error while submitting First store the max and min length required between each island . Sort according to min length . Start in reverse order that is take largest min length first . Find a suitable bridge using lower_bound .
•  » » » 7 years ago, # ^ |   0 Ah, ok. I simply iterated from the beginning of both arrays. If the length of the current bridge was not in between the current min and max, then I moved on to the next available bridge.
•  » » » » 7 years ago, # ^ |   0 This looks like TLE, accorting to the 10^5 bounds.
•  » » » » » 7 years ago, # ^ |   0 I apologize. I didn't finish elaborating.In my code, once I found a valid match, I would start looking for the next match considering only the bridges that came after the current one.However, this idea fails with the test case given by Bluespeck.
•  » » » 7 years ago, # ^ |   +3 My approach is somewhat different. I store all bridges in a set, because you can use a bridge only once, so with the set, you can easily erase the bridge from the set. I sorted all max (r_(i+1) — l_i) and min (l_(i + 1) — r_i) lengths by the maximum length. Then you try to fit the smallest bridge in the gap. If there is no bridge, or your lower_bound gives a bigger bridge, it's not possible.
•  » » » 7 years ago, # ^ |   0 I wonder if this is correct. You will find a "suitable" bridge — I assume the shortest bridge that is greater or equal than current min. How can you know that you shouldn't take a greater because it is too large to cover other islands?
 » 7 years ago, # | ← Rev. 3 →   0 Div 2 problem B description was a bit confusing. I was under the impression that a gear can move both clockwise and anticlockwise and that we had a choice. Therefore I was trying a DFS kind of approach will would obviously time out. Later I figured out that a gear can only move in one direction.
 » 7 years ago, # |   +3 I have a question. IF the problem is worth 250 points and you make 5 wrong submissions of it, at the end of the round, will you get negative score or still 30% of that problem's value (or whatever the minimum point value for the problem is)?
•  » » 7 years ago, # ^ |   0 you get at least 30% of the problem points which is equal to 75 ,so if your penalties (time + wrong submissions) make the problem less than 75 you will take 75 points
•  » » » 7 years ago, # ^ |   +19 Thanks. Howevr I think that wrong submission penalty should be dynamic. Especially with a dynamic scoring.
 » 7 years ago, # |   0 I thought very hard but couldn't find a way to solve div 2 D . How to solve it?
 » 7 years ago, # | ← Rev. 2 →   0 What's wrong with the Div2. D greedy solution? Sorting bridges and sorting island pairs (with their maximum value and minimum possible value) + binary search (some kind of lower_bound in bridges).
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I had something similar, but there will be cases where this fails.
•  » » » 7 years ago, # ^ |   0 Here's my code. It may be too complex. It didn't pass the 6'th test. http://ideone.com/kFJqP5
•  » » » 7 years ago, # ^ |   0 It's like you sort the islands pairs looking at minimum possible bridge and then at maximum possible bridge it fits. Then, for each pair you search in the sorted bridges array for the shortest possible bridge.
•  » » » » 7 years ago, # ^ |   0 what if the min/max pairs are like these: 2 6 2 9 4 5 and bridges are these: 4 6 9
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 CrazzyBeer i didnt understand your method.would you explain more clearly Thanks
•  » » 7 years ago, # ^ |   0 Greedy solution is the right one, something is wrong with your "greediness".
•  » » » 7 years ago, # ^ |   0 Explain your greedy.
•  » » 7 years ago, # ^ |   +4 Not sure... I took a greedy solution too and got stuck on pretest 10.
•  » » » 7 years ago, # ^ |   0 Well, the thing is that you put the next bridge in the interval that isn't already used and ends first.
•  » » » » 7 years ago, # ^ |   0 Could you explain your solution? I checked your profile and it says you didn't submit for that question.
•  » » 7 years ago, # ^ |   0 the same here, this is my code
•  » » 7 years ago, # ^ |   0 i think binary search don't help in this case, i pass pretests with set in which i store bridges lengths(and you can also do lower_bound in set in log time)
•  » » 7 years ago, # ^ |   0 try it: 3 2 1 3 4 5 7 7 3 4
•  » » » 7 years ago, # ^ |   0 bridges must not intersect right ??
•  » » » » 7 years ago, # ^ |   0 Seems there is no such limit
•  » » » 7 years ago, # ^ |   0 Yes 2 1, if I sort islands in ascending order and in other case I get a "No"
•  » » » 7 years ago, # ^ |   0 what is the answer for this case ?? I got: Yes 2 1
•  » » » » 7 years ago, # ^ |   0 Yes.But in the code given by CrazzyBeer I get a "No"
•  » » 7 years ago, # ^ |   0 Here is my approach , for each GAP , find the min and max value it can take. Let it be ai and bi. Now sort the GAPS with respect to the DIFFERENCE (bi-ai) , so lowest difference gets first. Now , sort the bridges too with smallest first.Now , iterate over the GAPS , try to match it with the smallest bridge.For the Example , the (min,max) for the gaps are (3,7) ,(1,3) and (2,5) . After sorting we get (1,3) ,(2,5) and (3,7) . Now , we first put smallest bridge 3 to (1,3) , then next one 4 to (2,5) and the third one 5 to (3,7). But I am stuck at case 10. 11805605
•  » » » 7 years ago, # ^ |   0 That one failed test 1? I think you mean http://codeforces.com/contest/556/submission/11805830I also got stuck on test 10.
•  » » » 7 years ago, # ^ |   0 I stuck at test case 10 with this approach too. It would really appreciated if someone smarter guy or girl could give a short example, why this strategy is bad :-)11805791
•  » » » » 7 years ago, # ^ |   0 Consider two gaps, [1,3] (i.e. 3 is max, 1 is min value it can take) and [3,4].You have two bridges of length 3 and 4.The greedy sol'n above results in using the smaller bridge of length 3 for the second gap, and leaves no bridge left for the first gap, when you could have satisfied both gaps.The difference in ai and bi is not a good metric; having smaller range of values doesn't imply it should be satisfied first.
 » 7 years ago, # |   +4 The statement for Div1.A/Div2.C can be more clear.
 » 7 years ago, # |   +102 I think submission penalties for Div1 A should be cancelled for people who got WA on pretest 6 prior to the clarification.Full disclosure: I am one of those people
•  » » 7 years ago, # ^ |   +19 not only submission penalties , extra time penalty because of resubmit should be removed too.
•  » » 7 years ago, # ^ |   0 What is pretest 6 on Div1 A/ Div2 C? I did not see the clarification because I started at min 40.
 » 7 years ago, # |   0 I've read Div1.A task. Thought that its too easy for Div1. Read again. And again — trying to find something tricky. Spent 10 mins, surrender on that. Coded this simple solution for simple task and it passed pretests o_O.
 » 7 years ago, # |   +30 I misread the statement of Div1-A twice and lost nearly 1 hour on that...
•  » » 7 years ago, # ^ |   +8 I lost a lotta time on that too... Maybe could've figured out the bug in my DIV1-B if they had a clearer statement from the start! :(
 » 7 years ago, # |   0 For me today was the day for WA on pretest 6 (8 WA on 6th pretest ) . Any tricky case for div1 B ?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 3 21 23 35 51 2
•  » » 7 years ago, # ^ |   0 Maybe something like this.This case hacked my friend's solution :) 3 2 1 10 11 12 14 15 2 10 
 » 7 years ago, # |   +16 I found out that my Div1D solution was right before AC, but I made a silly mistake :(So, I hope lot's of TL in Div1D! kekekekeke
 » 7 years ago, # |   +20 Back to div2.. see you guys ^_^
•  » » 7 years ago, # ^ |   0 Huh, me too probably, only solved A :)
•  » » » 7 years ago, # ^ |   0 high five ;) :D
•  » » » » 7 years ago, # ^ |   +9 I'd rather say low five lol :D
•  » » » » » 7 years ago, # ^ |   +3 Wait, wait, wait for me guys!
•  » » 7 years ago, # ^ |   +3 Don't worry, I won't leave you alone <3
•  » » » 7 years ago, # ^ |   0 it's not a big deal, we will have round #311 in 3 days, and we will all be back guys! ;)
•  » » » » 7 years ago, # ^ | ← Rev. 3 →   0 ...and I like blue color more than purple anyway.
•  » » » » » 7 years ago, # ^ |   +5 yeah, I agree. :D that would be good if this color were removed and replaced by some other
•  » » 7 years ago, # ^ |   0 Same here :p !! If only the first problem's clarification was made earlier!!! Well, who knows now? I will just try to improve myself and come back! :D
 » 7 years ago, # | ← Rev. 5 →   -14 The contest was great !!!
 » 7 years ago, # |   0 Problem B div 2 is O(n^2) ?????
•  » » 7 years ago, # ^ |   0 My solution have O(2*N)
•  » » » 7 years ago, # ^ |   0 can you explain?
•  » » » 7 years ago, # ^ |   0 can you explain your approach?
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 Just check for index 0 that how many steps counter clockwise you need to rotate to make its value 0. perform those number of steps in every other array index and check at last if it matches then "Yes" else "No". Complexity O(n).
•  » » 7 years ago, # ^ |   0 No, my solution works for O(n)
•  » » 7 years ago, # ^ |   0 You check if it's strictly ordered (like 0,1,2,3,4,5..n-1). If not — iterate through the array and do all the changes. I have done that exactly 2000 times.
•  » » 7 years ago, # ^ |   0
•  » » » 7 years ago, # ^ |   0 Great !
•  » » 7 years ago, # ^ |   0 11790948 O (N log N) can be O(N)
•  » » 7 years ago, # ^ |   0 My solution also run approximately O(N).At first I calculate how many time I need to push the button, then I cheek for all i (in range).
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 I believed that the solution exists and if there is a loop then solution doesn't exist.My AC submission 11794840
 » 7 years ago, # |   0 problem D of div2 is hard fo me.
 » 7 years ago, # |   0 Can somebody please explain why this solution gets TLE, it's linear — http://codeforces.com/contest/555/submission/11791988.I tried scanf/printf and I wrote it in C too but the outcome was the same. Then I deleted everything and wrote it again and it passed but why it didn't pass at the beginning?
•  » » 7 years ago, # ^ |   +45 cin>>n>>k; for(i=1;i<=n;i++) { How did this pass 14 pretests?
•  » » » 7 years ago, # ^ |   +13 lol thanks... I looked at the code more than 10 times and didn't notice that FACEPALM
 » 7 years ago, # |   0 I am going to learn SET
 » 7 years ago, # |   0 WTH I registered for the contest 24 hours ago !! Why cant I submit any solution ?
 » 7 years ago, # |   0 Div2A: Time limit exceeded on pretest 12 Wasn't expecting time limit errors on A task... anyone else hit by that?
•  » » 7 years ago, # ^ |   0 Me but i resolved it by another way and get pretest passed
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 Same thing, but still surprised to have an TLE on O(n^2) solution for n<10^5
 » 7 years ago, # |   +18 Scoring system is dynamic. But points deduction is absolute(-50) .. and when the score keeps decreasing, -100 pushes the score like hundreds of places behind. Please take a look Mike
•  » » 7 years ago, # ^ |   0 It will be the same as if the task have static 250, no? If so, nothing changed.
•  » » » 7 years ago, # ^ |   +6 It kind of discourages hacking and not much value for speed is given either. Difference of +100 initally due to early submission time is now like +10 or +20. But 2 faults in hacking gives -100 difference direct.
•  » » » 7 years ago, # ^ |   +1 In my case, I solved problem A in 30 mins, which has 171 points (after conversion to 250). I missed 2 hacks , which reduces score to 71 points and puts me at the fag end of the leaderboard
•  » » » » 7 years ago, # ^ |   0 Imo, its pretty fair. You should hack only if sure it succeed.
•  » » » » » 7 years ago, # ^ |   0 Hacking is my mistake, okay. But still, if 2 hacks make my score less than someone whose submission time is ages(people who submitted near end have higher points) after me, I feel there is an imbalance somewhere.
•  » » » » » » 7 years ago, # ^ |   0 Well you know, its balanced with task complexity — if you try to hack on e.g. task E it won't be the same.Also If you succeed these two hacks you get more scores than some ppl who solved A+B. Is it fair from your point? Its the opposite side of this hacking thing. Just not your one this time :)
 » 7 years ago, # |   +31 After this round, I think learning Russian is more important than English .
•  » » 7 years ago, # ^ |   0 Which problem makes you think this way?
 » 7 years ago, # | ← Rev. 3 →   -11 Contest time on early night truly affects my performance (at least for me)
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 i mean affects in positive by the way
 » 7 years ago, # |   0 Somebody explain me problem C in simple langugage
•  » » 7 years ago, # ^ |   0 Problem statement or solution?
•  » » » 7 years ago, # ^ |   0 problem statement . what exactly do we have to do. I am having really hard time with words like contained and nested .
•  » » 7 years ago, # ^ |   0 just imagine the dolls and how can you remove one, or put a doll inside another.first, you need a minimum of k-1 seconds to reassemble the chain from initial configuration.this is clear with a case like this:4 4 1 1 1 2 1 3 1 4here you only need to put 1->2, 2->3, 3->4then you need to test all chains, if you find a chain of size 'S' and has elements '1, 2, 3, 4, .. ,S'then this chain is consistent and there is no need to reassemble it.other wise you will need to disassemble all elements from the point of inconsistency.e.g.: a chain with: 1, 2, 4, 5you need to extract element 2 by removing 5 then 4hope this help's
•  » » » 7 years ago, # ^ |   +3 Can 2 chains be attached together ? suppose 1->2 and other 3->4 can these 2 be combined in a single step?
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 No, read the correction statement you have break 3,4 and then combine 1->2,3,4
•  » » » » » 7 years ago, # ^ |   +1 ok! thank you
 » 7 years ago, # |   0 Good time! Wish more contests like this.
 » 7 years ago, # |   +39 for(auto& v: adj[u]) if(v!=p) (WA 51) into for(auto& v: adj2[u]) if(v!=p) (AC)Copy paste why...
•  » » 7 years ago, # ^ |   -22 how can adj[u] changes to adj2[u] if copy paste?
•  » » » 7 years ago, # ^ |   +14 Yeah, I copy pasted two dfses, but I only changed one instead of both lists after I copy pasted. I was afraid I was going to run out of time if I didn't copy paste, but looks like I should've taken the extra 5 seconds to check it over.For reference:WA: 11804870AC: 11805918
•  » » 7 years ago, # ^ |   +31 for(auto it:M) WAfor(auto &it:M) AC:)
•  » » 7 years ago, # ^ | ← Rev. 2 →   +8 I ended up debugging my B during the contest. Found bug after the contest. Bug : Have to do sort(diff, diff + m) rather than sort(diff, diff + n). :'(
 » 7 years ago, # |   +1 please god don't let them take as long as the system test to publish the editorial
•  » » 7 years ago, # ^ |   0 Behold the bug in thy prayer! Repeat after me and be wise:Please gcd let not my integers overflow today.
 » 7 years ago, # |   -8 You have to normalize the coordonates on C div1 because QlogQ gets AC but QlogN doesn't, very very smart.
•  » » 7 years ago, # ^ |   +13 I've got AC with O(Qlog2Q) in upsolving. So I think O(QlogN) can pass.
 » 7 years ago, # |   0 Div 1 B.I saw people using similar approach like mine,and solved this problem using set.But I've time limit,can anyone offer optimizations or tell me the reason why my solution fails while other's don't? code
 » 7 years ago, # | ← Rev. 3 →   +10 The contest ended 1.5 hour ago. He solved all the problems 0.5 hour before the end.He visited 3 hours ago.Am I the only one confused??
•  » » 7 years ago, # ^ |   +3 "Last visit" doesn't mean he has beel left this site 3 hours ago, this is mean he last time entered site 3 hours ago.He just solved all problems and left.
•  » » » 7 years ago, # ^ |   +1 Oh, I see... too many gods coding here...
•  » » 7 years ago, # ^ |   0 probably it's the time when the person last logged in.
•  » » » 7 years ago, # ^ |   0 Yes, it seems like.
•  » » » 7 years ago, # ^ |   0 Nein. You're wrong :P
•  » » » » 7 years ago, # ^ |   +7 Nein, no one named 'wrong' here.
•  » » » » » 7 years ago, # ^ |   0 lol
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 That feature does not work at all :) I told MikeMirzayanov about it long time ago, but I think they have other things to do :)Sometimes it shows time from moment when you entered site, not when you left it; sometimes if you entered for a short period of time only — it does not update at all. Sometimes value randomly updates to older — you see "3 hours ago" there, press f5 and it becomes "9 hours ago".
•  » » » 7 years ago, # ^ |   0 Personally I like the last one. The next weekend will be earlier, right?
 » 7 years ago, # | ← Rev. 2 →   -8 Hi, Java fans.Trying to solve div1B using TreeSet I found out that I can't use the structure if there are duplicate keys.Here you can find why."For example, if one adds two keys a and b such that (!a.equals(b) && a.compareTo(b) == 0) to a sorted set that does not use an explicit comparator, the second add operation returns false (and the size of the sorted set does not increase) because a and b are equivalent from the sorted set's perspective".How to solve the problem then? Well, one could use TreeMap instead.http://codeforces.com/contest/555/submission/11800486http://codeforces.com/contest/555/submission/11805972
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 I solved it with TreeSet and TreeMaps. Have a look: http://codeforces.com/contest/556/submission/11840779
•  » » 7 years ago, # ^ | ← Rev. 6 →   0 If you have duplicate elements, try storing them in the form of objects where each object has a unique 'Differentiating Key' class Node { int element,int key; Node(int element, int key) { this.element=element; this.key=key; } } //Somewhere in main TreeSetd=new TreeSet(new Comparator() { @Override public int compare(Node o1, Node o2) { if(o1.ul!=o2.ul) { return o1.l-o2.l } return o1.diff-o2.diff; } }); //now passing values for(int i=0;i
 » 7 years ago, # |   0 Didn't like the MemoryLimitExceeded in Problem Div1C. It was too easy to get MLE if you focused in solving it on time. Good problems but either memory limit should be higher or N limited to 100,000 instead of 200,000 :(
 » 7 years ago, # |   +21 If the input would have been sorted in Div. 1 D I would have 100% solved for the first time. With unsorted input I was late for 2 minutes.
 » 7 years ago, # |   +11 I really wonder what 'technical reasons' are in Codeforces Round #307 (Div. 2), Codeforces Round #307 (Div. 2), Codeforces Round #305 (Div. 1), and others.
 » 7 years ago, # | ← Rev. 2 →   +27 Finally.P.S. I changed my avatar to red. One should always have a target. Hope I become red, as my avatar this year.
•  » » 7 years ago, # ^ |   +13 Contest : 310 Rank : 310 :)
•  » » 7 years ago, # ^ |   0 Ramadan has brought you great gift sir :)
 » 7 years ago, # | ← Rev. 3 →   0 Hi all,In Div 2 C/Div 1 A, I have submitted this solution which got WA: Solution1 And after the contest I checked the test case on which it was failing(Test case 8) and tried it on my ubuntu machine it gave me 33(which is the correct answer but it gave Wrong Answer on Codeforces). Then I submitted another solution: CorrectSolution it got accepted. In this I just have cleared the boolean array "khali". Can please anybody tell me why my same solution gave 33 on ubuntu machine and 27 on Codeforces on test case 8? This is the test case-> 20 6 3 8 9 13 3 4 14 20 2 15 17 3 2 5 11 5 7 10 12 18 19 4 1 3 6 16 
•  » » 7 years ago, # ^ |   0 the same here in test case 2 !!!i have compiled it at visual studio , jetbrains , ideaone . correct answer except at codeforces
•  » » » 7 years ago, # ^ |   +5 Try clearing some array that you have initialized. I am not getting that why linux machine result(having the same gcc compiler) differs from codeforces compiler result?
•  » » » » 7 years ago, # ^ |   +5 i am not in linux , i am on windows still WA
•  » » 7 years ago, # ^ |   +5 From Stack Overflow- " There is no automatic initialization in C++. Your new bool will be "initialized" to whatever was in memory at that moment, which is more likely to be true (since any non-zero value is true), but there is no guarantee either way. You might get lucky and use a compiler that plays nice with you and will always assign a false value to a new bool, but that would be compiler dependent and not based on any language standard. You should always initialize your variables."Same happened with me:P
•  » » » 7 years ago, # ^ |   +5 What a luck..!! That all of my n sized boolean array took 0 value(false value) by default even though I didn't initialized it and I wasted around 45 minutes + 2 Wrong submissions..
 » 7 years ago, # |   +10 Got screwed over by the MinGW C++ compiler: int n = 5; n = n--; cout << n;It turns out this code gives different results for GCC and MinGW. :( Shouldn't have coded that in the first place, but I was sleepy so I didn't notice it.
•  » » 7 years ago, # ^ |   +8 Instead of n=n--; n-- would have sufficed. It actually decrements the content of the register in which n is stored, so we would have our desired result. The line you wrote performs unexpectedly in different situations
 » 7 years ago, # |   0 Can somebody tell me why my code for Div1B http://codeforces.com/contest/555/submission/11803847 TLEs ?I sort every pair of islands by their maximum distance ascendingly (Sorting the indices actually) and then I insert the bridges in a set and looper over the pair of islands, and find the minimum possible bridge that fits then erase it it found. Complexity should be O(N lgN)
•  » » 7 years ago, # ^ |   +21 Know your libraries. std::lower_bound is O(n) for a set, not O(log n).You probably wanted b.lower_bound() instead.
•  » » » 7 years ago, # ^ |   0 Thanks, Now it's accepted, I definitely have to take note of this!
•  » » 7 years ago, # ^ | ← Rev. 2 →   +6 lower_bound(set.begin(), set.end(), x) works in O(N).set.lower_bound(x) works in O(logN)
 » 7 years ago, # | ← Rev. 2 →   0 The Tutorial link in problems of this round opens Codeforces Round 309's Editorial.Is Round 310's Editorial published?
•  » » 7 years ago, # ^ |   0 Nope, it's not published yet.
 » 7 years ago, # |   +39 Don't you think posting 1 to 5 ranked coders is motivating? :D
 » 7 years ago, # |   +2 When The editorial of round 310 will be available ?
•  » » 7 years ago, # ^ | ← Rev. 4 →   +4 Editorial: http://codeforces.com/blog/entry/18919
 » 7 years ago, # | ← Rev. 2 →   +2 Can anybody help me with the logic of Div 2 problem D? Plz elaborate in detail.
•  » » 7 years ago, # ^ |   +3 I don't think the editorial is coming up any time soon, so here goes. Given that we have to connect two islands with co-ordinates (a,b) (c,d) with some bridge of length l such that l<=(d-a) and l>=(c-b), since all islands lie on a straight line.Now we are going to implement a greedy solution, ie we sort all islands by their smaller distance(c-b) and try to assign the smallest bridge possible to the bridge.This solution will however fail in cases where although the smaller distance between the islands (c-b) is the minimum among all islands, but the larger distance is greater than the rest of the islands. You can think of it in terms of flexibility of an island defined as the range of accepting lengths of bridges from [c-b,d-a].Consider 3 islands as :1 5 (I1)6 7 (I2)8 9 (I3)Bridges are of length : 3,5Our initial greedy algorithm will assign bridge of length 3 to connect I1 and I2 and then would be unable to connect I2 and I3, but clearly switching the bridges gives us a solution.Therefore, we sort all islands by their larger distance(d-a) and then try to assign a bridge to it that is as close as possible to (c-b), ie we give highest priority to island with lowest flexibility and try to assign a bridge to it that just connects the island.code
 » 7 years ago, # |   0 Can anybody help me with my runtime error for Div.2 D at test case 11 (11810093). Every test case passed until the big one with 100000 islands and bridges.
 » 7 years ago, # | ← Rev. 2 →   +10 This time sorry_dreamoon-(qwerty787788) has beaten Haghani :)
 » 7 years ago, # |   +1 looks like the editorial is going to take forever !! please any body, what is wrong with my approach for problem Div2 D.
•  » » 7 years ago, # ^ |   0 Firstly sorting w.r.t minimum possible length of bridge is wrong. Simple test case: 3 2 1 4 5 6 8 9 3 5
•  » » 7 years ago, # ^ |   +5 wtf!! debug your code yourself.
 » 7 years ago, # | ← Rev. 2 →   0 Nice contest!
 » 7 years ago, # |   0 in general,my friend and I have a very tired contest......As I said -> DeaphetS he is the most hansome boy in our school .
 » 7 years ago, # |   +5 Can someone please explain me why my all 3 submitted solutions were skipped in yesterday's contest 11804905 ,11800557 and 11788258 ?
•  » » 7 years ago, # ^ |   +3 Solutions usually get skipped when they are found to be similar to someone's code. Did you ideone?
 » 7 years ago, # |   0 I didn't find the tutorial for this contest, somebody give me the link .
•  » » 7 years ago, # ^ | ← Rev. 4 →   +4 Here is this: http://codeforces.com/blog/entry/18919
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 this link redirects to editorials of the previous round (309).*edit* now the link works perfectly fine .thanks a lot.
 » 7 years ago, # |   0 Div 1D is very intuitive and easy! Comparatively div2D was tricky imo.
•  » » 7 years ago, # ^ |   0 It maybe your illusion......
•  » » » 7 years ago, # ^ |   0 that's what I thought, but after looking at someone's accepted code, it was the same as my logic. complexity= n*logn*logl in worst case.
 » 7 years ago, # |   0 Finaly solve problem Div.2 D (11818401): Let represent an island as pair ii = (li, ri). You have to sort all island pairs (ii, ii + 1) after their maximum distance in ascending order. The bridges can be save in a set. Than we start at the beginning of the sorted island pairs and perform for the minimum distance dmini = li + 1 - ri the operation lower_bound(dmini) on the set. We have to check if the resulting bridge fulfill the requirements and erase the bridge from set otherwise print "No" and exit. We repeat the procedure for each island pair. Note that we have to put a little work on the datastructure since the output requires the indicies of the bridges.
 » 7 years ago, # |   0 where can I find the editorial ? (the contest material is linked to the wrong page)
•  » » 7 years ago, # ^ |   0
•  » » 7 years ago, # ^ |   0 Official editorial is almost ready.
•  » » » 7 years ago, # ^ |   0 in div2C, shouldn't the final formula be 2n - k - 2l + 1
•  » » » » 7 years ago, # ^ |   0 Fixed
•  » » 7 years ago, # ^ |   0 thanks !!
 » 7 years ago, # | ← Rev. 2 →   0 Can anyone please help me out with a TLE in Div2 D/Div1 B? TLE on case 12Here's what I did: Take input of all the co-ordinates of the islands. Simultaneously, store the gaps in the form of an object which takes in co-ords of adjacent islands(Li,Ri,Li+1,Ri+1) and stores [Li + 1 - Ri;Ri + 1 - Li]. All of these gaps are sorted in ascending order on the basis of the above formula. If value of any gap is the same, then there is an extra unique key, 'diff', which separates them. This condition has been met in the Comparator in the TreeSet which sorts the keys, as mentioned in ascending order. Take input of all the lengths of the bridges and store them in a HashMap which stores the length of the bridge as the key and maintains a TreeSet for each key which stores the indices at which this bridge length has been found at. Now finally, Iterate through all the gaps stored in the TreeSet and obtain [Li + 1 - Ri] and [Ri + 1 - Li] which has already been stored in the custom datatype. Iterate through this closed interval in ascending order and keep checking if the Map contains any value in this interval. The first value it finds, assign this index to the gap which is stored in an array. 0th entry stores the index for the gap 1 between bridges 1 and 2 etc. If no value exists in any interval, break and print No. Else, print Yes and print the indices stored in the array for each gap.
 » 7 years ago, # |   0 Can anyone explain Haghani's solution of problem DIV 2E/1C ? Its so simple and elegant but i don't get how it works.
 » 7 years ago, # |   -21 This Problem and Case of Matryoshkas (Div2) are exactly same problems.
 » 7 years ago, # |   0 I'm sorry for necroposting and pedantry, but the first picture in the note for problem D (Div. 1) isn't consistent with the sample test -- the coordinates there are 0, 5, 8, while in the sample test they are 0, 3, 5. It confused me (while upsolving), and can confuse someone else. Supposing that the picture was made in MetaPost, it's a matter of several minutes for the authors to correct this.
•  » » 7 years ago, # ^ |   +5 Yeah, thank you for reminding of that. Actually, only coordinates are wrong while the overall illustration is kinda correct. But you're right and it should've been corrected. Your supposition is wrong and it might take some time to fix it.