Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### fcspartakm's blog

By fcspartakm, history, 4 years ago, translation, ,

Hello, Codeforces! It's me again=)

I'd like to invite you to Codeforces Round #387 (Div. 2). It'll be held on Monday, December 19 at 05:05 MSK and Div. 1 participants can join out of competition.

This round is held on the tasks of the second day of the municipal stage All-Russian Olympiad of Informatics 2016/2017 year in city Saratov. They were prepared by Olympiad center of programmers of Saratov SU.

Great thanks to Nikolay Kalinin (KAN) for helping me preparing the contest, to Tatiana Semenova (Tatiana_S) for translating the statements into English, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon platform and to Vladimir Petrov (P1kachu), Alexey Ripinen (Perforator), Mikhail Levshunov (Levshunovma), Mikhail Piklyaev (PikMike), Aleksey Slutskiy (ferc), Ivan Androsov (BledDest), Oleg Smirnov (Oleg_Smirnov) and Roman Kireev (RoKi) for writing solutions and editorials.

You will be given six problems and two hours to solve them. The scoring distribution will be announced later. Good luck everyone!

UPD The scoring distribution 500-1000-1500-2000-2000-2500

UPD2 Editorial

UPD3 Congratulations to the winners!

• +131

 » 4 years ago, # |   +147 Now this is what I call unusual time :D
 » 4 years ago, # |   +25 5:30AM here...It's cool :D...I'll try to join the contest...
•  » » 4 years ago, # ^ |   +12 You are lucky, It's 4:00 AM here :D
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +14 But I'm gonna stay awake till the contest starts :)PN. Of course it's just an excuse, I think I'll watch some movies and when the contest starts, I'll sleep :)
 » 4 years ago, # |   -9 Why at this time?
•  » » 4 years ago, # ^ |   +45 Bocause some people have day at that time.
•  » » » 4 years ago, # ^ |   -56 What people? ;)
•  » » » » 4 years ago, # ^ |   +43 Half of the world
•  » » » » » 4 years ago, # ^ |   0 What is the number of people from the selected regions are registered on codeforces? I am not trolling or something — I am really curious.
•  » » » » » » 4 years ago, # ^ |   +8 It's hard to tell, Russia and China alone has over 10k users combined, but that also accounts for the western part of the country. (Western China should have much less competitive programmers AFAIK, but I have no idea about Russia)
 » 4 years ago, # | ← Rev. 2 →   +45 Deleted
•  » » 4 years ago, # ^ |   +3 That's the spirit!
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +26 Deleted
•  » » » » 4 years ago, # ^ |   +17 Well u already have positive rating
•  » » 4 years ago, # ^ |   0 Good luck and have fun:D
 » 4 years ago, # |   0 iam gonna wait whole night for this contest !!! lets hope this contest bring positive rating change to all of us... good luck everyone :)
 » 4 years ago, # | ← Rev. 4 →   -11 I would like to participate, but the desire to sleep is stronger than my goal hah5a it will be 3:00 AM here man!
 » 4 years ago, # |   -9 I would like to participate, but the desire to sleep is stronger than my goal hah5a it's at 3:00 AM here man!
 » 4 years ago, # |   +1 Its 05:11 AM here in India. I randomly opened codeforces to check editorials and I am surprised by this highly unusual timing.hope to get + ratings. :D
 » 4 years ago, # | ← Rev. 3 →   +23 Contest==> 7:35 am to 9:35 am (IST)Exam==> 10:00 am to 12:00 pm (IST)But gotta do it, coz cant miss a codeforces round!
•  » » 4 years ago, # ^ |   +4 me too bro , I hope to increase my rating and and get full marks .
•  » » 4 years ago, # ^ |   +12 10am to 12am ? That's a quite long exam!
 » 4 years ago, # | ← Rev. 2 →   +31 I think that this is the time, you Europeans and Asians, in which you'll know what people in America suffer. Regular codeforces rounds are at 10:35 here in Mexico, and I always have to skip classes to take them. But not today. Today is at the perfect timing of 20:05
•  » » 4 years ago, # ^ |   +1 So，good time，wish you good luck！
•  » » » 4 years ago, # ^ |   +3 Thanks! Good luck to you too!!!
•  » » 4 years ago, # ^ |   0 Amen
 » 4 years ago, # |   +9 Never awake early for college first time only for CF.
 » 4 years ago, # |   +40 8:30 PM, on a Sunday night? This has to be the most convenient time for a contest ever for NA people. Can we do this at least once every two months?
•  » » 4 years ago, # ^ |   +8 Completely support that motion
 » 4 years ago, # |   +5 I can't believe that I have just left my pillow and blanket to participate in this Round I haven't done that before, even to watch GOT
 » 4 years ago, # |   +4 This round timing reminds me of TopCoder SRMs timing.Most TopCoder SRMs were hold at time like this and I had to wake up after the mid-night to take it.But I think it deserves.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 This reminds me of Google Code Jam Round 1A, actually.
 » 4 years ago, # |   +4 i hope the round will deserve stay awaking for 4 am
 » 4 years ago, # |   +6 Hopefully I can gain ~300 ratings from these two rounds so that I could rush a purple before the year ends.Just 110 more to go =]
•  » » 4 years ago, # ^ |   +5 Congratulation！ U achieve it
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 Thanks! I think this is my first time that I don't fail any system tests, usually I look cool pre-system test then suck hard.PURPLE HERE I COMEEEEEdit: Woahh, 2000+ rating? That was unexpected!
•  » » » » 4 years ago, # ^ |   0 congratulation!
•  » » 4 years ago, # ^ |   0 Congrats, I guess I'll lose a few due to that cheap mistake
 » 4 years ago, # |   +3 It's 18:35 here. But I think it's a little early?
•  » » 4 years ago, # ^ |   +3 Sorry, it takes some mistakes...I thought it was #386
 » 4 years ago, # |   0 Can anyone explain how to do D? Is it dp (I was using a 3D dp table but couldn't implement it properly)?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 No need of DP, you can do it with a min heap. Store the difference(number of summer days) between two consecutive winter intervals and process them from lowest to highest.
•  » » » 4 years ago, # ^ |   0 Ah that's a lot simpler than I thought it would be. And it makes sense when I think about it.
•  » » 4 years ago, # ^ |   +3 No, greedy works. Split the array into segments of negative values. Sort the distances between consecutive all-negative segments in increasing order and just keep using winter tires to join them.
•  » » 4 years ago, # ^ |   0 the given test case in D , third one answer shouldn't be 2. If he wants minimum tire changes then he must club summer days with winter , if possible . According to that ans can be reduced to 2.
•  » » » 4 years ago, # ^ |   0 But then he would have used more than k days which he's allowed for winter tires.
•  » » » » 4 years ago, # ^ |   0 cool .
•  » » 4 years ago, # ^ |   0 I believe greedy works: on all the negative days you have to use winter tires. Pick the smallest interval (non-empty) that is bounded by two consecutive winter days, and fill use winter tires over that interval. Of course you have to account for the corner cases and whatnot.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Mine was a greedy one. I just kept cancelling any swapping between the two days with negative temperatures and the distance between them is the smallest until I run out of Winter tears. But I am still not sure that this solution is correct. :DUPDATE : mine is incorrect :D
•  » » 4 years ago, # ^ |   +3 Greedy works just as other comments have stated, remember to always consider the final segment of non-negative temperature AT THE VERY LAST. Now I thought it a bit more I just missed a hacking opportunity on someone who sorted the final segment with the others.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 hey haleyk can you help me in test case 31 . I think i covered all the edge cases still missing by 1 . don't know which one now!http://codeforces.com/contest/747/submission/23128267
 » 4 years ago, # |   +3 Nice Contest.
 » 4 years ago, # |   0 Almost no hacking in this contest. There were literally no hacks in my room :o
•  » » 4 years ago, # ^ |   +2 I'm just gonna hope that means the pretests were decent.
•  » » » 4 years ago, # ^ |   0 :)
•  » » » 4 years ago, # ^ |   0 I also think its because the solutions to the test cases were explained clearly. Also most tricky cases seemed to be given there too.
 » 4 years ago, # |   0 My idea around D was something like this:Let's assign Winter Tyres W to all negative temperatures and Summer Tyres S to others. Let initial answer be the worst case of exchanges required.Now, if we convert a segment which is of the form: WSSS...SW to WWWW...WW then we reduce 2 exchanges. So, we try to cover the smallest segment first and greedily try to reduce exchanges this way.My implementation gave segfault on Pretest 3. Dunno if this would work — can someone point out where this could go wrong?
•  » » 4 years ago, # ^ |   0 this was my idea too and got ac after contest. just remember to add first exchange and last exchange(which if happens, both will be 1).
•  » » 4 years ago, # ^ |   0 If you have the last few days covered by S, consider replacing it with W to save one switch. Since you only save one, which is less than the normal two, check this case at the very end.
 » 4 years ago, # |   -6 TFW you know that problem F is a problem about binary search and combinations but you suck hard at combinations... WITH 90 MINS LEFT.void recursion(struct me, int remainingTime){ if(remaingingTime) remainingTime -= 0.1;}I thought I was stuck forever.
•  » » 4 years ago, # ^ |   0 Can you give an outline of your approach?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Use binary search to find the answer, and count the combinations of non-interesting numbers smaller than var(mid).I didn't manage to find the combination formula though.Use a vector of decimal based numbers will help during processing.Edit: Whoops I was wrong. Seeing the tutorial reminds me that using dp to count the combinations is a common technique which I learnt in other round's tutorial...
 » 4 years ago, # |   0 How to approach E? I made a recursive function but could find no way to optimize it.
•  » » 4 years ago, # ^ |   +1 Use a stack to keep track the amount of children comments already posted for a comment, thus managing the depth of each comment.
•  » » 4 years ago, # ^ |   +1 a recursion solution may be helpful http://codeforces.com/contest/747/submission/23126041
 » 4 years ago, # |   +6 Greedy... greedy everywhere
 » 4 years ago, # |   0 Bye expert! Just I was some hours blue
•  » » 4 years ago, # ^ |   0 Just compete tomorrow and get it back!
 » 4 years ago, # |   0 I hope there will not be another contests at this time again.
•  » » 4 years ago, # ^ |   +7 I think it is a cool time during semester break. It's morning in eastern Asia so I could join the contest with a fresh brain instead of a tired one on the usual time. The amount of people available on this time slot is really low though...
•  » » » 4 years ago, # ^ |   0 I agree with you about participating with a fresh brain but it's not a semester break for everyone. I'm working on semester projects now and it's 10 days away from the beginning of the semester exams.I don't know if it's a good time for many members or not. but I didn't see anybody upset from the usual time.
•  » » 4 years ago, # ^ |   0 What time is it now in your country?
•  » » » 4 years ago, # ^ |   0 It's 6:30 AM now.
 » 4 years ago, # | ← Rev. 2 →   0 C failed systest y tho bro? opens the code after 10 secs aaah, f***, I forgot to ignore the one with insufficient number of servers...
 » 4 years ago, # |   +4 Such quick system testing !!!
 » 4 years ago, # |   +2 What is problem D test 31? Any ideas?
•  » » 4 years ago, # ^ |   +3 I think it's some thing like this :  8 7 -1 -1 -1 0 0 -1 -1 0  Considering segment [4, 5] gives optimal answer even though it's length is greater than segment [8, 8].
 » 4 years ago, # | ← Rev. 2 →   0 Wohooo! First place in my room for the first time! ...and I got WA on problem A because of uninitialised variables, how embarrassing :P
•  » » 4 years ago, # ^ |   0 A reversed case for me. I saw someone's code could possibility cause RE since it could check out-of-bounds values, but I didn't have the courage to hack that guy.He coded something like this:int d[4], z = 0;while(d[z] == 0) z++;
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Thanks for reminding me to think twice. Congrats on the rating change.
 » 4 years ago, # |   0 why my source is runtime error in Problem E? http://codeforces.com/contest/747/submission/23126016
 » 4 years ago, # |   0 An unusual timing for the contest, the number of problems, and system checking was so fast! I like this contest
 » 4 years ago, # |   +9 Last ACC in the Round :D
•  » » 4 years ago, # ^ |   +4 wow nice one! hope you become purple =))
•  » » » 4 years ago, # ^ |   0 I wish too :D
 » 4 years ago, # | ← Rev. 2 →   0 Is here anybody who solved D with binary search? :D
 » 4 years ago, # |   0 you know it was a greedy contest when nearly 400 solutions fail system test for D. wasted whole time on D in search for a O(n) dp solution. :(
•  » » 4 years ago, # ^ |   0 It's so hard to set a question which denies O(nlogn) while accepting O(n) though.
•  » » » 4 years ago, # ^ |   0 haleyk100198 you did very great today.How did you solved D and E so fast?
•  » » » » 4 years ago, # ^ |   +1 For problem D I got a little bit lucky to notice the greedy approach, so I only have to spend some time on refining the code to handle the corner cases.For problem E, managing a file tree is a quite common practice problem. (I am surprised that it showed up as a regular round problem E)Whenever I see such a problem I just go straight for stack, and there's no other tricks needed so I got it almost instantly.
 » 4 years ago, # |   0 Good morning! can anyone explain D for me? is it DP? i wanted to do this with 3x dp2D but i can't!
•  » » 4 years ago, # ^ |   0 Check the comments above, there is a populated comment above which should guide you how to solve it with greedy.
 » 4 years ago, # |   +15 So excited about being a Candidate Master!!!
 » 4 years ago, # |   0 although i solved 2 questions ,_ better than every time_, my rating points decreased ! could anyone explain to me the rating process and why i decreased please ?
•  » » 4 years ago, # ^ |   0 hereI think your rating dropped because there were less number of participants.
•  » » 4 years ago, # ^ |   0 This should explain how the rating system works: http://codeforces.com/blog/entry/102Note that at this date, the division line is drawn at 1900, and you start with a rating around 1500.
 » 4 years ago, # |   0 Can anyone help me why 23126693 got WA?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 You made a mistake to consider the final segment of non-negative days with other segments.For example:10 80 -1 0 0 -1 0 0 0 -1 0Your code considers to use the winter tire on segments : [2, 5] and [9, 10] (1-based), as it recognises the last non-negative segment [10] has the best greedy value, but the correct answer should be [2, 9] as using winter tire on [6, 8] further reduces the result.
•  » » » 4 years ago, # ^ |   0 thank you for helping!
•  » » 4 years ago, # ^ |   0 try this case:  8 7 -1 -1 -1 0 0 -1 -1 0  Answer should be 2 instead of 3.
 » 4 years ago, # |   +11 In problem 747E - Comments, my code receive TLE in maintest 9. However, when I resubmit the same code, it get TLE in test 29. Here is my code in the contest: 23123300.And here is my resubmitted code after the contest: 23128262.You can use compare button to check whether they are same.I so worry that may people could fail system test because it (not me because I still fail with test 29)
•  » » 4 years ago, # ^ |   +4 I don't think this should be a concern as your code was very close to TLE on test case 9 in both submissions. It is known that CF running time has a delta of around 30ms, which should not cause problems to most submissions. (As always, you run a risk of submitting non-optimal solutions)
•  » » » 4 years ago, # ^ |   0 Thank you very much.
 » 4 years ago, # |   0 http://codeforces.com/contest/747/submission/23124311Can someone help me find out the mistake i made in problem C .
•  » » 4 years ago, # ^ |   0 You should prioritise using the unoccupied machines with smaller ids, instead of the ones who were released earlier.
•  » » 4 years ago, # ^ |   +1 I think your mistake is that you do this (servs[i].f=(t+(d-1));). If only x (x
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Thanks!
•  » » » 4 years ago, # ^ |   0 I solved problem C with O(q*n).. can be solved less than that!!!
 » 4 years ago, # | ← Rev. 3 →   +5 I woke up early for the round 386, waited for this round and will wake up early tomorrow again for next round, hopefully there are more often 'daily' rounds
 » 4 years ago, # | ← Rev. 4 →   0 why for this input: 10 5 1 1 1 2 1 3 3 2 3 4 1 1 5 2 1 answer is : 1 1 5 4 5, but not 1 1 5 4 7 ?at second 1, there're 10 unoccupied servers and we need to occupy 1 sever for 1 second , sum -> 1;at second 2, there're 10 unoccupied servers and we need to occupy 1 server for 3 seconds(sec. 2,3,4), sum -> 1;at second 3, there're 9 unoccupied servers and we need to occupy 2 server for 3 seconds(sec. 3,4,5), sum -> 2 + 3 -> 5;at second 4, there're 7 unoccupied servers and we need to occupy 1 server for 1 second, sum -> 4; at second 5, there're 8 unoccupied servers and we need to occupy 2 servers for 1 second, sum 3 + 4 ??
•  » » 4 years ago, # ^ |   0 Notice that you should use server 1 and 4 for the final task.
•  » » » 4 years ago, # ^ |   0 this is, thanks. : (
 » 4 years ago, # | ← Rev. 2 →   0 For problem E, I traversed the string once and stored the strings at the index of its level in a vector and later displayed the contents of vector level wise. The total memory taken by the vector will then be equal to the memory taken by the string.But I am receiving a runtime error on system test 26.http://codeforces.com/contest/747/submission/23129959Is there something fundamental I'm missing out? Thanks for any help in advance.
•  » » 4 years ago, # ^ |   +1 I am not sure about this, but line 105 seems to cause out of bounds problems.
•  » » 4 years ago, # ^ |   +1 Its due to out of bounds.Use this while condition instead- while(i
•  » » » 4 years ago, # ^ |   0 Yes it is. Thankyou very much!
 » 4 years ago, # |   0 Hello, I have a small doubt regarding problem E. My submission 23125639. The code for converting string to integer is ` for(int i=0; i
•  » » 4 years ago, # ^ |   0 The power function returns a double type value which on conversion to an integer might cause some precision issues. Use a custom power function instead.
•  » » » 4 years ago, # ^ |   0 For powers of 10, I don't think there is any problem with precision. If there is an error, it'll occur in the decimal places and it'll be ignored. Is there any case where a this conversion won't work? Thank you for your reply
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 pow(int, int) actually calls pow(float,float) (or pow(double,double)). There are two problems:1)float can represent correctly (with no error) only integers with less than 6 digits.2)int(0.99) is 0 and pow() gives us only estimated value. It might give you 9999.99999 when you ask for pow(10,4). And it will be rounded as 9999.
•  » » » 4 years ago, # ^ |   0 I forgot that pow can return a number slightly lesser than the number. Thank you for the clarification.
•  » » 4 years ago, # ^ |   +1 Besides the precision problems, I think you should also learn the stoi (and stoll, stod etc.) functions, that helps a lot with converting string to numerical values. That saves a lot of time for coding a function that does the same thing.
•  » » » 4 years ago, # ^ |   0 Thank you for the advice
 » 4 years ago, # |   +13 thx a lot for these consecutive contests (#387,#386,#385,#384)...it helps our ACM team for ICPC-Tehran Region
 » 4 years ago, # |   0 This is our contest week!
 » 4 years ago, # |   0 Doesn't the problem B statement says coordinates to be lie between -1000 and 1000. But the output of the judge is considering the coordinates outside this range.
•  » » 4 years ago, # ^ |   0 I assume that you are talking about 749B instead of 748B.The range of x, y coordinates is only applied on the input, you can output any legit integers in the output.
 » 6 weeks ago, # |   0 Hey, can anyone tell how to solve D using DP? It has a DP tag, and I am practicing DP questions, so I would be more than grateful to know about that! :D