### I_love_myself's blog

By I_love_myself, 14 months ago, translation,

Hello, Codeforces!

I'm glad to invite you to Codeforces Round #637 (Div. 1) - Thanks, Ivan Belonogov! and Codeforces Round #637 (Div. 2) - Thanks, Ivan Belonogov!, which will be held on Apr/23/2020 17:45 (Moscow time). The round will be rated for both divisions (I hope).

All problems were written and prepared by Aleksey Aleks5d Upirvitskiy, Alexey alexX512 Perevyshin and by me, Denis I_love_myself Sapozhnikov. Thanks to 300iq, voidmax, I_Remember_Olya_ashmelev, Akulyat, okwedook, Minnakhmetov, divanik, Zakoden, Jostic11, Nakinamo, 4qqqq и allisyonok for testing problems and good advice, isaf27 for round coordination and help with preparation and MikeMirzayanov for great systems Codeforces and Polygon.

You will be given 6 problems in both divisions and 2.5 hours to solve them. Please, read all the problems. Good luck, have fun and I wish everyone high ratings!

The scoring distribution will be announced closer to the beginning of the round.

Did you notice unusual in the title of the round? Here is the message from MikeMirzayanov:

With this round we want to convey fiery greetings and once again say thanks for the support to Ivan Belonogov Belonogov. And it’s not only about his significant gift on the 10th anniversary of the platform. Starting to participate in 2011, Ivan has come a long way from a participant in Div. 2 rounds to the international grandmaster, became the ICPC world champion as part of ITMO team. Such a striking motivational example of a success story! Thank you, Ivan!

UPD1: The scoring distribution will be:
Div1: 500-750-1250-1750-2250-3000
Div2: 500-1000-1500-1750-2250-2750

UPD2: Due to technical problems, the round is delayed by 10 minutes. Sorry!

UPD3: Editorial is published!

UPD4: This was our first round and we made mistakes wherever possible. Sorry for this. We decided to make Div1 round unrated, Div2 round is still rated. You can read more details in this post. We hope that you enjoyed solving interesting problems and did not pay attention to our mistakes.

• +125

 » 14 months ago, # | ← Rev. 2 →   -329 Just go away! Don't read this....
•  » » 14 months ago, # ^ |   -186 Let's take the initiative to never Comment.Lol!
•  » » » 14 months ago, # ^ | ← Rev. 2 →   -225 Yeah! This happens every time when I comment! @kaushal_26 what happened to your comment! LOL
•  » » » » 14 months ago, # ^ | ← Rev. 5 →   -198 And just do it one more time!
•  » » » » 14 months ago, # ^ |   +18 "This happens every time"maybe because your comments are no help or use for the community.
 » 14 months ago, # |   -8 Good luck and have fun, everyone! :D
 » 14 months ago, # |   +25 Some division rounds are of 2 hours while some of 2.5 hours. I am curious as they both have same number of questions(on average). What is the reason then? Is it that the 2.5 hour rounds are slightly tougher/ implementation heavy?
•  » » 14 months ago, # ^ |   +68
•  » » » 14 months ago, # ^ |   -31 Ahaha such a funny meme)))) YES BUT ACTUALLY NO)))) It's like "YES", but actually "NO" :)))))
•  » » » » 13 months ago, # ^ |   -11 I never saw a girl who was a Master on Codeforces. You are the first one
•  » » 14 months ago, # ^ |   +103 Aha.. figured it! They contain questions similar to 2hr round contests but in a difficult language!
•  » » » 9 months ago, # ^ |   0 Well, I took Virtual participation last night and spent 0.5h understanding the meaning of Problem B.The statement is too difficult for people who do not use English as mother tongue to understand quickly.
 » 14 months ago, # |   +113 As one of the testers of this round, I can say that tasks are too interesting. Hope that the authors ' efforts will not be in vain :_)
•  » » 14 months ago, # ^ |   -58 Wow!
•  » » 14 months ago, # ^ |   -49 Thank you for your efforts :)
•  » » 14 months ago, # ^ |   +69 Bait
•  » » » 14 months ago, # ^ |   +38 It definitely is.
•  » » » » 14 months ago, # ^ |   +16 orz
•  » » » 14 months ago, # ^ |   0 yep
•  » » 14 months ago, # ^ |   -22 You were right. Really good problems.
 » 14 months ago, # |   -111 I hope it'll be easy.
 » 14 months ago, # |   -181 How many problems will there be?5 or 6 or 7or6 or 7 or 8?
•  » » 14 months ago, # ^ |   +85 "You will be given 6 problems in both divisions"
 » 14 months ago, # |   -82 I wish this blog was posted at codeforces top page so I don't have to find this blog.
 » 14 months ago, # |   -33 https://codeforces.com/blog/entry/68665i have some questions...
 » 14 months ago, # | ← Rev. 5 →   -51 Hope the problem statements will be short.
 » 14 months ago, # |   -50 My first Div. 1 contest! Hoping I can still participate in Div. 1 after this.
•  » » 14 months ago, # ^ |   -40 Haha.
 » 14 months ago, # |   -33 what is ivan's codeforces handel?
•  » » 14 months ago, # ^ |   +7
 » 14 months ago, # |   +41 It has been mentioned that $Please,\,read\,\, all\,\, the\,\, problems.$ Does this mean that problems might not be in increasing order of difficulty?
•  » » 14 months ago, # ^ |   +26 nope there is story of Fricking Nastya and Simp Denis.
•  » » » 14 months ago, # ^ |   0 Nastya got no chill
 » 14 months ago, # | ← Rev. 2 →   -41 .
•  » » 14 months ago, # ^ |   +15 it seems like creators dont like short problems
•  » » » 14 months ago, # ^ |   +3 agreed
 » 14 months ago, # | ← Rev. 3 →   -53 The only question about the contestWill the No. 1 spot in the rating change ?tourist or Retired_MiFaFaOvO or Anyone else
•  » » 14 months ago, # ^ |   -28 chill bro,LGM dont need to worry
 » 14 months ago, # | ← Rev. 2 →   -19 Deleted
•  » » 14 months ago, # ^ |   -55 But still we can see your deleted comment :p
 » 14 months ago, # |   +21 "I love myself" is such a good user name :DHope this round will have strong pretests.
 » 14 months ago, # |   -13 Wish everyone high rating and I hope that most of you go to the next rank in this contest.
 » 14 months ago, # |   -26 hopefully the problem statements would be short..
 » 14 months ago, # |   +17 Much more frequent contests
 » 14 months ago, # |   +17 I_love_myself will there be any sub-part problems?
 » 14 months ago, # | ← Rev. 2 →   -26 So many contest in quarantine time
 » 14 months ago, # |   -19 Good！
 » 14 months ago, # |   -23 Thanks, Ivan Belonogov.
 » 14 months ago, # |   -51 a round is held in his honor and the last time he logged into codeforces was two months ago...most probably he won't even know for a long time that he is respected so much by Mike Mirzayanov and Company....IT is ironic if u think about it!lMaO************
•  » » 14 months ago, # ^ |   -17 Not really, maybe Mike could have conveyed his respect through a personal mail or something.
 » 14 months ago, # | ← Rev. 2 →   -35 Please we need a nice problems
 » 14 months ago, # |   +22 Good luck, guys!We will be live upsolving the round when it ends:https://youtu.be/0kr6YSroclg
•  » » 14 months ago, # ^ |   0 hey!! I watched your videos. Nice explanation. Good job done :) I have a doubt in problem E. You figured out that cyclic dp will create a problem as the recursion will catch itself in loop. So, we should use dijikstra, to find minimum distance from source(0) to destination(n), by considering dp states. So, the solution Time complexity will be : m*(g+r)*log(m*(g+r)), which will cause TLE. So, how to optimise it?
 » 14 months ago, # |   -20 Thank you, Ivan!
 » 14 months ago, # |   +4 Interesting nickname
•  » » 14 months ago, # ^ |   +86 I love my nickname as much as myself
 » 14 months ago, # |   +237
 » 14 months ago, # |   -23 Thank you mister Ivan Belonogov Belonogov
 » 14 months ago, # |   -11 Hope this round has strong pretests...
 » 14 months ago, # |   -19 What will be the score distribution?
 » 14 months ago, # |   -19 Good luck and have fun
 » 14 months ago, # |   0 Can we please have the scoring distribution now I_love_myself ?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +49 I'm curious to know why people want to know the scoring distribution? Does scoring distribution impact how you are going to attempt the questions? Or is there anything else? (For me it is sufficient to know that the later questions have more marks then the previous ones)
•  » » » 14 months ago, # ^ |   -11 for Mental preparation
•  » » 14 months ago, # ^ |   0 Done!
 » 14 months ago, # |   +9 Good luck everyone!
•  » » 14 months ago, # ^ | ← Rev. 2 →   -16
 » 14 months ago, # | ← Rev. 4 →   -21 [Deleted]
•  » » 14 months ago, # ^ |   -10 It has been published. Please check the UPD1
 » 14 months ago, # |   -122 Programmers are so bored in quarantine, they are giving downvote to maximum comments O_o
•  » » 14 months ago, # ^ |   -40 and yours as well
•  » » » 14 months ago, # ^ |   -22 and mine as well
•  » » » » 14 months ago, # ^ |   +11 poor me
•  » » » » » 14 months ago, # ^ |   0 orz you
 » 14 months ago, # |   0 Thanks Ivan for his support ! Hope that one day I could be like him <3
 » 14 months ago, # |   -13 Why has it been extended by 15 mins?
•  » » 14 months ago, # ^ |   +17 yes
•  » » 14 months ago, # ^ |   +14 delayed 10 min , not 15
 » 14 months ago, # |   +21 why it is delayed?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +19 Small problems on Codeforces and Polygon. Nothing serious.
•  » » » 14 months ago, # ^ |   +11 But the Problem statements were not so small. :)
•  » » 14 months ago, # ^ |   0 Due to technical difficulties :(
 » 14 months ago, # | ← Rev. 2 →   -12 I was checking my phone for a few minutes, then saw the contest page again and thought I had slept and woke up for the next contest. /s
•  » » 14 months ago, # ^ |   +4 next time try not being drunk while attending a contest
•  » » » 14 months ago, # ^ |   +13 haha okay!
 » 14 months ago, # |   +191 When it is delayed ...
 » 14 months ago, # |   -13 delay 10m :((
 » 14 months ago, # | ← Rev. 2 →   +17
 » 14 months ago, # |   0 Yet another long round, 2 hours 30 minutes (+10 minutes delay?)
 » 14 months ago, # |   +15 no electricity in my place...So its good..hope electricity comes back in 10 minutes
•  » » 14 months ago, # ^ |   +19 codeforces knew it , they did it for you
•  » » » 14 months ago, # ^ |   +31 Electricity came just after writing the comment...
 » 14 months ago, # |   +16 10 minutes delay after a long time.
 » 14 months ago, # | ← Rev. 2 →   -6 Round hasn't even started, but codeforces already start to lag :/
•  » » 14 months ago, # ^ |   0 your pic is a love.. <3
 » 14 months ago, # |   +47 when I went to have my dinner, I had 12 minutes left.. When I came back I still had 12 left
•  » » 14 months ago, # ^ |   +62 The problem of being faster that light, is that you can only live in the darkness.jpg
•  » » 14 months ago, # ^ |   -10 seems like you mastered ultra instinct after all these efforts lol...
 » 14 months ago, # |   0 IT took me one minute to realize my network is still working well and the time on my clock is still right...
•  » » 14 months ago, # ^ |   0 Congo bro! Round delayed for *9 minutes
 » 14 months ago, # |   +149 Antipleasant tasks, I wish authors to end third grade faster
•  » » 14 months ago, # ^ |   +31 Can't agree more. I just give up this round.
 » 14 months ago, # |   +83 Extreme long statements, to reach the actual question its taking time.
 » 14 months ago, # | ← Rev. 2 →   0 I did register for the Div. 1, the website even did notice me about the contest started and I clicked Enter buttonBut then after I finished the 1st problem, the website says I never register!!!!!Do I really need to register for both Div. 1 and Div. 2 to join the contest??
•  » » 14 months ago, # ^ |   +1 u cant register to div. 1 ur green
•  » » » 14 months ago, # ^ |   0 Oh i see, thank you!
 » 14 months ago, # |   +147 The problem statements are too complicated!
 » 14 months ago, # |   -41 IMO problem C is so cool!
 » 14 months ago, # |   0 Recently, the div2 rounds are not being scheduled on weekends like it used to happen earlier. Been missing a lot of recent rounds because of this. Looking forward to more weekend contests :)
 » 14 months ago, # |   +34 Div2 D weak pretests :C
 » 14 months ago, # |   +116 $My\,\,Dad:-\,$ Don't run behind the girls. They are too complicated. you can be ruined.$Me\,to\,\,my\, \,Dad$ (after this round) $:-$ They can complicate a problem statement too if they appear.
•  » » 14 months ago, # ^ |   +14 Nice story, awesome DAD
 » 14 months ago, # |   +28 I haven't seen a cancer like this before.
 » 14 months ago, # |   +33 I would say div2 C is too complicated
 » 14 months ago, # |   +19 Tasks description was so long, I had to print it on paper because text didn't fit my screen resoltion.
 » 14 months ago, # |   +9 I mean, task should not test our reading skills. It took me way too long to understand and at the end I ended up not understanding the problem anyway.
 » 14 months ago, # |   +90 UGH !!!!StatementForces !
 » 14 months ago, # |   +47 Denis(in the statement) is such a poor guy.
•  » » 14 months ago, # ^ | ← Rev. 4 →   0 That is not an excuse for him to go on a rampage in a public place destroying expensive electronic equipment.
 » 14 months ago, # |   +178 I hate those div1 coders who make fake profiles just to take part in div2, pls stop doing this! Are you guys afraid to take part in div1, afraid to lose your rating? If that's the case i feel sorry for you. I might have a lot less rating than you guys but i take part in contests to learn new things, not just to improve my rating!
 » 14 months ago, # |   0 i cry
 » 14 months ago, # |   +13 statements are too long to be read...
 » 14 months ago, # |   +24 VeryLongProblemStatementForces
 » 14 months ago, # | ← Rev. 2 →   +38 I don't know about E and F, but the rest of the problems from Div2 were absolute trash: no creative thinking, pure implementation. And the length of problem statements is another story.
 » 14 months ago, # |   +24 The problems are shreiking and saying comprehension skills are better to be developed than coding skills. Hope codeforces will not make such lengthy problem statements in future which further decomposes just to a for loop only . Those who read fast are fast scorers in this contest.
 » 14 months ago, # |   0 Haha.. Loved the story line!
 » 14 months ago, # |   +8 Very much complicated problem statements. And 2-3 lines of these complex story is necessary to solve the problems. Rest of them only confused me.
•  » » 14 months ago, # ^ |   -7 True
 » 14 months ago, # |   0 How to solve Div-2 D. Will greedy work here ?
•  » » 14 months ago, # ^ |   +4 Actually soln is greedy but take care of valid string after using exactly k.
•  » » » 14 months ago, # ^ |   0 I thought of doing dp. But, tge implementation was very difficult for me to do.
•  » » 14 months ago, # ^ |   +1 You can look at English Commentary of Problem D here I hope it helps!
•  » » » 14 months ago, # ^ |   -8 Thanks, understood the mistake I was making.
 » 14 months ago, # |   +13 How to solve Div.1 C?
•  » » 14 months ago, # ^ |   +11 My solution which takes O(m*g*log(m*g)) passed the pretests. I just use dijkstra with vertices are (index of safe point, time left to move before red light)
•  » » » 14 months ago, # ^ |   0 I didn't think that would pass though :/
•  » » » 14 months ago, # ^ |   +10 You can just use 0-1 bfs instead of dijkstra to remove log.
•  » » » » 14 months ago, # ^ |   +5 how does the 0-1 bfs work?
•  » » » » » 14 months ago, # ^ |   +15 It's same as regular bfs, but instead of queue use deque and if cost of edge is 0 push to the front of deque else to the back.
•  » » » » » » 14 months ago, # ^ |   0 sorry, I meant to ask how you use it to solve problem C because my dijkstra had wasn't on a graph with 0/1 edge weights
•  » » » » » » » 14 months ago, # ^ | ← Rev. 3 →   +31 If we change distance to number of (r + g) time segments costs will be 0\1.
•  » » » » » » » » 14 months ago, # ^ |   0 ah that's nice. thanks!
•  » » 14 months ago, # ^ |   0 I just did Dijkstra and passed the pretests. However, it passed too tight.
 » 14 months ago, # |   +6 Pretest 5 of Div2D?
 » 14 months ago, # |   0 What is the test case 5 for DIV.2 D?
 » 14 months ago, # |   +20 How to solve div1C/2E ?
 » 14 months ago, # | ← Rev. 3 →   +14 I have no issues with stories in problem statements if they fit in well, but the story of Div2B seems like its just been created for the sake of having a story and has practically no relation to the actual problem. In my opnion the entire 4th and 5th paragraphs are utterly useless and just serve to confuse people.
•  » » 14 months ago, # ^ |   +3 It confused me a lot. It was very sad :_v
 » 14 months ago, # | ← Rev. 2 →   +670 WORST STATEMENTS EVER!!! English was so broken and not understandable at some times that I can't even. And to top it all off, inital version of Div1E was some freaking misunderstanding, a very bad joke. It contained a lot of very weird words, like "power" instead of "degree", firstly "pick" instead of vertex, then "peak" instead of vertex and then some very weird sentence for making a move with some random "top" in the middle of it. Of course the statement was corrected, but SILENTLY AGAIN. Less than two weeks ago, I requested that whenever any changes are made then please make an appropriate announcements https://codeforces.com/blog/entry/75806?#comment-601901 and no improvement here. Quality of statements and that poor misunderstanding called initial statement of Div1E and no broadcast after its change made me rage quit the contest first time in many years.EDIT: Sad part is that problems alone seemed really nice. But even though I was pretty pumped up with energy and good hopes before the contest, all I could find in today's contest was confusion and anger.
•  » » 14 months ago, # ^ |   +72 Yet we still get an annoying announcement for "the checkpoints in C may not be given in sorted order".
•  » » » 14 months ago, # ^ |   +98 Yes, like what the frick was that? It made me angry as well. First embarassing thing was to allow an input format without such natural condition. When searching for bugs in my code I reread the statement like two times in the search of condition that they are sorted, because I could not believe my eyes it is not present. And then, I don't care whether you get 1000 questions about whether this sequence is sorted or not, you went for such poorly or evilly prepared contest, so let's take responsibility for your actions and do not make it unfair for people that spend their time and nerves on this. We do not get an announcement "hey, statement of E was complete shit, you should reload it", but we get "hey, you get WA because you didn't notice that some sequence doesnt have to be sorted"...
•  » » » » 14 months ago, # ^ |   +32 Not including non-sorted case in pretests(or even examples) was just stupid.
•  » » 14 months ago, # ^ |   +83 Yeah, the statements were shit.
 » 14 months ago, # |   +3 What is Test 3 in 1C ?
•  » » 14 months ago, # ^ |   0 10 5 0 3 4 7 10 9 10 Probably this?
•  » » 14 months ago, # ^ |   0 This one was useful to me: 26 6 0 9 10 12 22 26 11 11 
 » 14 months ago, # |   +24 It was hard to comprehend the problem statements.
 » 14 months ago, # |   +22 I took more time to understand C than to code the solution
•  » » 14 months ago, # ^ |   0 No wonder — as soon as you realize what the solution is there is not much to code. :)
 » 14 months ago, # |   +4 For Div.2 C I am sharing my strategy to solve it which has passed the pretests.Take an example of n = 7 and 1-indexed array arr and position allotment p:Step 1: i = 1 arr = [1,1,1,1,1,1,1] Now generator can select any index from 1 to 7. Suppose it selects index-4. Now we can't select position-4 further. p = [?,?,?,1,?,?,?]Step 2: i = 2 arr = [1,1,1,?,2,1,1] Now generator will have to select will have to select position-5 as it is the maximum position. p = [?,?,?,1,2,?,?]Step 3: i = 3 arr = [1,1,1,?,?,3,1] Now position 6. p = [?,?,?,1,2,3,?]Step 4: i = 4 arr = [1,1,1,?,?,?,4] Now position 7. p = [?,?,?,1,2,3,4]Step 5: i = 5 arr = [1,1,1,?,?,?,?] Now again generator can select any index from 1 to 3. Suppose it selects index-3. p = [?,?,5,1,2,3,4]Step 6: i = 6 arr = [1,1,?,?,?,?,?] Now again generator can select any index from 1 to 2. Suppose it selects index-1. p = [6,?,5,1,2,3,4]Step 7: i = 7 arr = [?,1,?,?,?,?,?] p = [6,7,5,1,2,3,4]KEY OBSERVATIONS:1: If the position j is selected for number i, Then the remaining positions with a greater index should be placed with i+1 and so on i.e. position j+1 with i+1,j+2 with i+2... 2: Positions less than j will again depend on selection by the generator as all the values will be 1. The assignment of the remaining positions could be considered again as the new problem with the unassigned minimum number which is 5 in the above example.Any permutation follows these observations results "Yes" else "No".
 » 14 months ago, # |   +9 I Read problem C for 40 minutes then only got what it is saying. In B also sometimes setter says that peaks have to be answered and sometimes says parts of doors another dielemma NO comments for A(Which is a first ever Div2 A seen by me!)
 » 14 months ago, # |   +10 How to solve E? dijkstra's gave TLE.
 » 14 months ago, # |   +23 Maybe my English is so poor that I can't even understand the meaning of the problem.I am so sad.
•  » » 14 months ago, # ^ |   +121 No, it was the English of round's authors.
 » 14 months ago, # |   -8 i feel so smart writing a 100 line function to check the current number in D, only to notice that the strings were given in the problem statement :), and unable to submit it in time because of that.
 » 14 months ago, # |   +3 I dunno why the time limit for div.2 D was so tight. It cost me like 14 submissions to pass the pretests.
 » 14 months ago, # | ← Rev. 2 →   +172 Was fun typing all the digits on Div1B before realizing that it's listed...
•  » » 14 months ago, # ^ |   +14 Good to know I'm not the only person who actually wrote them all out (though I'm probably the only one who wrote one incorrectly and got a WA).
•  » » 14 months ago, # ^ |   +17 I realized it now, after reading your comment. XD
•  » » 14 months ago, # ^ |   +36 Since you have to copy manually anyway, how about: const bitset<7> dig[10] = { bitset<7>("1110111"), bitset<7>("0010010"), bitset<7>("1011101"), bitset<7>("1011011"), bitset<7>("0111010"), bitset<7>("1101011"), bitset<7>("1101111"), bitset<7>("1010010"), bitset<7>("1111111"), bitset<7>("1111011"), }; 
•  » » » 14 months ago, # ^ |   +91 you can also do vector bits { 0b1110111, 0b0010010, 0b1011101, 0b1011011, 0b0111010, 0b1101011, 0b1101111, 0b1010010, 0b1111111, 0b1111011, }; 
•  » » » » 14 months ago, # ^ |   0 I Copied the line from the problem statement and put it in a string vector . void diginit() { vector arr = {"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"}; foru( i, 0, arr.size()) { string s = arr[i]; vi temp; for (auto it : s) { temp.pb(it - '0'); } digit.pb(temp); } } 
 » 14 months ago, # |   +5 A: So easy. B: So easy. C: I need some time to find the construction method. Oh I make it! D: It's slightly difficult, but I can solve it with more time. E: ??? ...OK, Good night.That's all.
•  » » 14 months ago, # ^ |   -26 Easiness is relative, I didn't find B easy at all. Speak for yourself.
 » 14 months ago, # |   0 I think the constraints on problem E (Nastya and Unexpected Guest) were too tight for Java. After my first try the program failed due to time on the third pretest and after implementing some stupid optimizations (not changing the O complexity) I got the program to reach the pretest 8. Here's my program if anyone's wondering: https://pastebin.com/Z3Xjg1rk. I'm fairly positive my program would work if the time limit was 2 seconds instead of 1.
•  » » 14 months ago, # ^ |   +9 If you had used 0-1 BFS, which is probably the intended idea, even a Java solution would have passed.
•  » » » 14 months ago, # ^ |   0 Can you explain how to use 0-1 BFS in the problem? How do you interpret the problem as one with 0-1 edges?
•  » » » » 14 months ago, # ^ | ← Rev. 5 →   +2 Make the graph where vertices are pairs of numbers $(t, p) \in \{0, \dots, g\} \times \{1, \dots, m\}$representing being at the $p$th line at time $t$. There's an edge between $(g, p)$ and $(0, p)$ of weight $1$, which corresponds to waiting at that spot during the red light. Also put edges between $(g, p)$ and $(g+dist(p, p+1), p+1)$ and $(g+dist(p, p-1), p-1)$ (as long as those numbers are in the right ranges) which correspond to moving forward or backward. These edges have weight $0$, since there's no red light you have to wait for.
 » 14 months ago, # | ← Rev. 2 →   +15 The video tutorial of Div-2D.
•  » » 14 months ago, # ^ | ← Rev. 2 →   +4 Great video. But it was possible to solve using only 2 states. Solution
 » 14 months ago, # |   +194 Just imagine sposoring this round xDDDD
•  » » 14 months ago, # ^ |   +98 should ask for a refund
 » 14 months ago, # |   +27 I don't want to blame any of the authors, the tasks (at least A,B,C,D) were good in my opinion. However, the staments for B and C are long and hard to read for no reason at all.
 » 14 months ago, # |   +9 Was it just me or were some of the problem statements rather long and complex? I decided to start with Div2 C and feel like I made a big mistake. I spent forever trying to understand what the problem was asking for. Decided not to submit anything as I had lost too much time. Which is unfortunate as some of the other problems were very interesting..
 » 14 months ago, # |   +3
 » 14 months ago, # | ← Rev. 3 →   0 Is there not a maxtest in the pretests of Div2D/1B? My solution takes 70 * n ^ 2 instead of 10 * n * k but still passes pretests in around 200ms even though it should take upto 3e8 operations. Fast simple operations or weak pretests? 77820531
 » 14 months ago, # |   0 English Commentary for Div 2C is here
 » 14 months ago, # |   +65 My idea for D, unfortunately I spent a lot of time solving slightly different versions of this problem and understood the statement correctly too late: It's a modification of DFS — the following describes processing some subtree. The key is that if we move down to this vertex from its parent at times $t \rightarrow t+1$, we want to move back also at times $t \rightarrow t+1$. Clearly, we want to rewind at some point. We'll process subtrees of some $s_1$ sons, returning from them at times $t+2, t+3, \ldots, t+s_1+1$, then rewind to a time $t-s_2$ and process the subtrees of the $s_2$ remaining sons, returning from them at times $t-s_2+1, t-s_2+2, \ldots, t-s_2+s_2=t$. Finally, we move back. This is optimal because we either have $s \le t$ sons and choose $s_1=0, s_2=s$, which means $t+1$ is the maximum used time and we don't make the max. time worse by what we're doing in this vertex, or we have $s \gt t$ sons, choose $s_1 = s-t, s_2=t$ and the worst-case time is just $s+1$, which is the obvious lower bound — we need to visit each vertex at least as many times as its degree (+1 for the initial visit of the root). This is the comment I wanted to post 3 HOURS AGO
 » 14 months ago, # |   +18 Trust me the test cases are weaker than my eyesight! Boom!I am blind :(
 » 14 months ago, # |   -10 Can someone please explain 2 C ?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +3 incase the input was 7 8 9 4 5 6 1 2 3 then the output will be Yes. 7 8 9 4 5 6 10 1 2 3 then the output will be No. hope this gives you a fair idea.what i did was : added the first contiguous increasing subarray at the end of the deque, and pushing the 2nd contiguous increasing subarray using push_front in deque. If I end up with with a sorted deque then the ouput will be yes, else no. refer my code : https://codeforces.com/contest/1341/submission/77810951I believe the question statement were a little confusing atleast for me !
 » 14 months ago, # |   +8 Did anybody solve F using algebra? Without signs it would be doable with matrices/permutations for example, but it became harder with the signs.
•  » » 14 months ago, # ^ |   0 Can you please share your approach ?
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 Do you mean a normal solution to F, or the approach with matrices/permutations to the problem without signs?
•  » » » » 14 months ago, # ^ |   0 I meant the approach with matrices/permutations to the problem without signs.
•  » » » » » 14 months ago, # ^ |   +7 With permutations, for each type of bracket choose some permutation which consists only of cycles of length at most $2$, possibly different permutations for different types. Now, the composition of permutations of the brackets from the left to the right will be the identity if the string is a correct bracket sequence and won't be and identity with high probability otherwise (if you chose long enough permutations and selected them randomly for example). Build a segment tree ofc.
•  » » 14 months ago, # ^ |   0 Wasted most of the contest on this approach. :(
•  » » » 14 months ago, # ^ |   +14 A function on finite sets can't really satisfy fg = 1 and gf != 1, it doesn't seem too fruitful
•  » » » » 14 months ago, # ^ |   0 Yes, I realized this during contest but thought that if we checked all balances independently after that, that would fix it. But it doesnt work on "([)(])".
•  » » » » » 14 months ago, # ^ |   0 Yea, I've even rushed for implementing checking all balances independently. I saw this case somewhere else after the contest, it looks hard.
•  » » » » » 14 months ago, # ^ |   0 Do you know how to do it faster than $O(n \cdot \sqrt{n\cdot \log(n)})$ btw? (Assuming $q=n$).
 » 14 months ago, # | ← Rev. 2 →   -9 Decent contest!Solution notes for A-D (Div 2): A) The range of sum of x is [(a-b)*n,(a+b)*n] and it works iff it intersects with [c-d,c+d]B) Use two pointers/sliding window type approach, where you add or subtract depending on the point you remove and add each step. Becomes O(n) instead of naive O(n^2)C) Basically if you put something at a point such that all other points to the right of it are filled, then we don't need to do anything. Otherwise, if we put l at point x, we put l+1 at point x+1, l+2 at point x+2..and so on until we hit a point at the right that we put previously, so we need to check if their position in the permutation is consistent with this. D) Basically dp[n][k] from n-1 to 0, where dp[i][j] stores the leading digit of the best result you can get with strings [i,n) and exactly j moves available. How do you do E? I think E was some sort of dp/dijkstra shortest paths, but couldn't figure out how to find if two points where reachable from each other in exactly g steps quickly... there could be a lot of alternating involved so there were lots of states.
 » 14 months ago, # |   0 Was it only me or the statement of DIV2 B was kind of misleading as initially it said the segment end should not be peaks but to pass the pretests they were considering segments ending at peaks also. Waisted a lot of time figuring this. Such an easy problem took 1 hr to get passed because of poor statements. Kindly make statements good as they really affect the rating.
•  » » 14 months ago, # ^ |   +7 Uhh ending of a segment cannot be a peak.
•  » » 14 months ago, # ^ |   0 What it actually said is that a peak $i$ on a segment $[l, r]$ must satisfy the condition $l  » 14 months ago, # | ← Rev. 2 → -30 Nice problem statements. First time seeing problem statements of different problems have continuing/same story.  » 14 months ago, # | ← Rev. 2 → +150 In addition to the bad and unnecessarily long statements, I was rather surprised by the constraints / time limit on Div1 C — either make it so Dijkstra (with log) fails for all, or make it so Dijkstra passes for the most common programming language. In this case some C++ solution passed and some failed without seemingly any difference. I challenged several people successfully and some unsuccessfully (some passing for 0.966s). Was it that hard to make the constraints on M <= 20,000 or 5,000 (instead of 10,000)? •  » » 14 months ago, # ^ | ← Rev. 2 → +70 Agreed--constant factor played way too much of a role here. I'm not sure how they managed to miss such a glaring issue with a dozen or so testers--the Dijkstra solution obviously exists, so they should have made a clearer decision about whether to fail it or not. Relying on hacks to catch a wrong solution is an extremely bad idea because it means that people who are hacked have a chance to fix their solutions and resubmit, while people who aren't just FST.I thought 1D was a very nice problem, but at this point I'm not sure it makes up for the extremely weak pretests and long statements of the rest of the set. •  » » » 14 months ago, # ^ | -27 As a tester, who solved it using Dijkstra I can tell we saw the problem, but couldn't do anything about it. Some slower bfs implementations are working in the same time as fast Dijkstra. So we decided that you either write optimal solution (bfs) or squeeze in Dijkstra. •  » » » » 14 months ago, # ^ | 0 I used this A*-esque heuristic considering distance from current position to destination which seemed to help: https://codeforces.com/contest/1340/submission/77862540And afterwards I re-implemented with my own heap because I've found STL's can be a bit slow: https://codeforces.com/contest/1340/submission/77863711 •  » » » » » 14 months ago, # ^ | +1 My solution (using Dijkstra) uses STL priority_queue and works in around 800ms. •  » » 14 months ago, # ^ | +26 If Dijkstra isn't the intended solution, you should fail it in the pretests...  » 14 months ago, # | +13 I am one of those not able to understand what 1341C - Nastya and Strange Generator asks for, tried for an hour. Luckyly was able to solve D afterwards, but that was no fun.  » 14 months ago, # | +12 Imagine the level of frustration when you have to throw a door at MoUnTaIn PeAkS to break them. •  » » 14 months ago, # ^ | +7 It was the most frustrating problem statement ever! The whole thing was so misleading!Even in div2 d he is talking about broken sticks! when something is broken how are you supposed to turn it on?  » 14 months ago, # | +48 The array in Div1 C isn't sorted and there is no test for that in pretests...  » 14 months ago, # | 0 Can someone help me ? What states of dp should i use for Div2 Problem D? •  » » 14 months ago, # ^ | +1 Two states are required. index of the board and current value of k. •  » » » 14 months ago, # ^ | -11 thanks !  » 14 months ago, # | ← Rev. 3 → +13 I did Div2 D with greedy approach Nlogn(Hacked)  » 14 months ago, # | +97 We've got a wrong answer on test 1 on system tests 77835164! •  » » 14 months ago, # ^ | +66 Yeah, it took me some years of practice to achieve such outcome with deterministic solution :)  » 14 months ago, # | +23 Was checker for problem D wrong during the contest? Even when my solution output two equal pairs in the sample, it got WA 3, not WA 1. •  » » 14 months ago, # ^ | ← Rev. 2 → +14 Yes, there was a tiny issue with the checker, it was fixed, but some solutions failed (8 solutions).We have written to all, whose solution failed.  » 14 months ago, # | -18 I can understand that the problem statements were a little longer but I seriously think that the story deserves appreciation. Natsaya getting confused seeing a heart and breaking the door of heart on the mountains into pieces, Denis getting distracted about her love for a random permutation generator, Denis not able to stand still while he is after a girl and so even moving in the opposite directions. Man! That's really good writing. •  » » 14 months ago, # ^ | 0 Which door stretches over mountain peaks man? I mean seriously?? •  » » » 14 months ago, # ^ | 0 I know. It doesn't make sense. But I find it extremely hilarious.  » 14 months ago, # | +17 Weak pretest in Div2A. :(  » 14 months ago, # | ← Rev. 2 → +6 Hacked by Ashish •  » » 14 months ago, # ^ | 0 I too did it without using DP •  » » » 14 months ago, # ^ | +15 Hacked you as well :) •  » » » » 14 months ago, # ^ | 0 It stopped my hearbeat for a second •  » » » » 14 months ago, # ^ | 0 Wait how can you hack after the contest? •  » » » » » 14 months ago, # ^ | 0 That's uphacking, you won't loose points for that and hence your rank won't be affected, you can read more about it here •  » » » » » » 14 months ago, # ^ | 0 If I would be loosing points I would have to wait more to become Blue •  » » » » » » 14 months ago, # ^ | 0 Hi, can you try hack my solution? 77797225 •  » » » » » » » 14 months ago, # ^ | 0 5 0100111 1001111 1100111 1010110 0110010 Here is test case he is using •  » » » » » » » » 14 months ago, # ^ | 0 Tnx a lot! •  » » » » » » » 14 months ago, # ^ | 0 Done :) •  » » » » » » » » 14 months ago, # ^ | 0 You are on fire •  » » » » 14 months ago, # ^ | +14 are the system tests for d1B are ridiculously weak? •  » » » » » 14 months ago, # ^ | +3 Saw some greedy solutions passing sys tests :-/ •  » » » » » » 14 months ago, # ^ | 0 ........................sad •  » » » » » » 14 months ago, # ^ | 0 Note that in the greedy solution one can use prefix sums of min needed sticks and max usable sticks.Using these we can check from left to right in every position the maximum number of usable sticks, and with that simply build the biggest possible digit.Given that the limited number of digits and 7-segments the complexity is something like O(n*10*10) and hence runs fairly fast.Example 77847086 •  » » » » » » » 14 months ago, # ^ | +3 I wouldn't call your solution a greedy. It's more of a backtracking with a lot of early breaking, which is like the dp solution without memoization. •  » » 14 months ago, # ^ | +11 Hacked :) •  » » » 14 months ago, # ^ | +1 Ashish you a legend if you can hack 77846297 •  » » » » 14 months ago, # ^ | +13 Done :P •  » » » » » 14 months ago, # ^ | ← Rev. 2 → +2 orzverma_ankit484 Sorry XD •  » » » 14 months ago, # ^ | +5 orz •  » » » 14 months ago, # ^ | -12 If it not too much to ask please hack this. •  » » » » 14 months ago, # ^ | +1 It seems correct to me, my solution is somewhat similar to what you are doing. •  » » » » » 14 months ago, # ^ | ← Rev. 2 → -12 Thanks •  » » » 14 months ago, # ^ | 0 Ashish On Fire !!  » 14 months ago, # | +30 Shitty pretests for Div2 D.  » 14 months ago, # | ← Rev. 2 → +57 This contest was the worst way to thank someone...  » 14 months ago, # | +127 I'm a bit worried that Russian speaking participants were a bit privileged (guess why). Statements really seem to be taken from google translate, is it true? •  » » 14 months ago, # ^ | +10 Don't underestimate Google Translate! •  » » » 14 months ago, # ^ | +127 "This road is not always can be crossed in one green light." •  » » » » 14 months ago, # ^ | +50 that sounds worse than google translate. Actually, translating to russian and back again gives: This road cannot always be crossed in one green light. •  » » » 14 months ago, # ^ | +49 "From any square, you can get to any other in exactly the same way using these roads and not visiting the same square twice." •  » » » » 14 months ago, # ^ | +30 I mean even google translate works better. •  » » 14 months ago, # ^ | -8 Just replace every the with this. Check for yourself. •  » » 14 months ago, # ^ | +56 Funny thing: while reading the Russian statements, I thought the original language is English, and translation is sub-par at times. •  » » 14 months ago, # ^ | +8 Its like bad and worse. :(  » 14 months ago, # | ← Rev. 2 → -6 So is this round unrated, since ratings are not updated? Kinda sad to have cleared the problems only to find out it. :( •  » » 14 months ago, # ^ | 0 Wait for some time it will get updated  » 14 months ago, # | +52 Damn, the first test where points in Div1 C are not sorted in the input is test 70... •  » » 14 months ago, # ^ | +21 Hacking changes the round.  » 14 months ago, # | ← Rev. 2 → +66 I've solved div1E, but I'm pretty sure the following is a counter example.My idea is to move your 3 bees to minimize the sum of the distances to the (up to) 3 neighbors of N (where you must match bees to neighbors). I've also seen other AC submissions with the same idea. (But instead of sum of distances they minimize the largest distance, then the 2nd largest distance, then the smallest distance).For a counterexample, consider the 'ladder graph' made into a cycle: two cycles A and B of length n next to each other, where A_i is connected with B_i. Note that each vertex has degree 3, and that each edges is included in a cycle of length 4 (i.e. less than 5).After picking initial bee positions close to A_0 and B_0, N can start at e.g. A_{n/4}. Now all my bees will move along the circle 1 step, and then N can just move one step up to A_{n/4+1}. This can continue forever I think. •  » » 14 months ago, # ^ | ← Rev. 2 → +41 Yeah, I also got AC with incorrect solution. I think this problem has a lot of incorrect solutions for which is very hard to create counterexamples without knowing an idea of solution. But this cycled ladder graph is counterexample to lots of solutions, and it is very strange that it wasn't in tests. •  » » » 14 months ago, # ^ | +10 Sure it's difficult to make good test cases here, but I think the only way to make a cycle of length > 5 without chords is to make it so that the entire graph is one 'double' cycle. I think it's not possible to have 2 'independent' chordless cycles of length > 5.So given that this is the only special graph, you'd think that this needs extra testing. •  » » » » 14 months ago, # ^ | ← Rev. 3 → +18 I and VladProg (who also got AC with wrong solution) also discussed solution that tries to move bees to different adjacent vertexes to Nastya's vertex without going through another adjacent vertexes to Nastya's vertex. This solution will pass cycled ladder test (because if you remove all adjacent vertexes to Nastya's vertex there will be no long cycle) but there exists another counterexample, like cycled pentagons. •  » » » » » 14 months ago, # ^ | +10 Ah, that's a neat idea, but yeah won't work for even bulkier cycles.Another idea is to choose the initial positions roughly at 0, 1/3rd, and 2/3rd along the cycle. E.g. by fixing 0 and then choosing u, v such that d[0][u] + d[u][v] + d[v][0] is maximal.Also found a construction to turn any graph G into a graph H suitable for this problem such that G is a minor of H, so you can definitely get more complicated inputs than just cycles.Anyway I'd love to see a proof that this approach works even in graphs without long cycles. The 'every edge in cycle of length <= 5' condition is useful because now some of the bees will always 'take the long route' to block off potential exits, but I can't yet prove that the max distance or sum of distances goes down by at least 1 or 3 respectively each turn. •  » » » » » » 14 months ago, # ^ | ← Rev. 2 → +20 So it's actually quite easy to embed K_5:https://imgur.com/a/LC60kW9If you make all 'edges' 100+ steps long I think it should be possible to escape.Maybe in practice the condition is/should have been that such long cycles do not exist at all anyway? So formally you can reduce the graph to a point by repeatedly contracting cycles of length <=5 to a point.Also, congrats on being red now ;) •  » » » » » » » 14 months ago, # ^ | ← Rev. 2 → 0 Thanks ;)Yeah, in random graph you can replace edges with these "ladders" and you will get graph that satisfies problem statement. (also you can split each vertex with degree > 3 into few vertexes with degree = 3 with length of ladder between them equal to zero). But obviously there exists a graph that has minimum number of bees larger than three. I suppose it's impossible (or possible, but using very big number of queries) to catch Nastya on these graphs.  » 14 months ago, # | +9 Missed out on 1D because I left out a ++pt; in one of my loops. How fun.Cool problem, though.  » 14 months ago, # | +8 In Div1 B I thought k would always be less than or equal to number of sticks which are off.As said in the problem statement, what is the maximum number that can burn on the board if you turn on exactly k sticks (which are off now) Reading the line(specially the sentence in the bracket), it seemed to me that at least k lights are off.Which led to wa in system test.  » 14 months ago, # | +31 When you realize tourist solved Div1B in 00:04, while you can't even read the statement in that time •  » » 14 months ago, # ^ | 0 How does he do so. Really reading takes so much time, specially when the paragraphs are so long. •  » » 14 months ago, # ^ | 0 But really, he fucked up big time in this contest. Big ratings drop for sure.  » 14 months ago, # | ← Rev. 2 → +2 I guess the extra 30 minutes from ingeneral round was for reading the long paragraph in each question...  » 14 months ago, # | ← Rev. 3 → +24 In div2D/div1B, case where solution can consist of leading zeroes isn't present in the systests. Thought I'd fst, but didn't. code case  » 14 months ago, # | 0 I solve A(div1) so l check if we have anybody what a[i] + 1 < a[i+1] answer No else Yes.  » 14 months ago, # | +51 hmm, I had the exact same code on all 3 submissions...Are the data structures on newer versions of C++ faster? 77856421 77857168 77857210 •  » » 14 months ago, # ^ | +31 Off the tangent, but what made you try this check? •  » » » 14 months ago, # ^ | +24 I opened up the status page and looked at the C++ solutions that passed, and most were in C++ 17 or C++ 17 (64). I switched to C++ from Java pretty recently, so I don't know too much about which version of C++ is best for certain situations. I guess this is one of those situations? •  » » » » 14 months ago, # ^ | +8 Due to the c++17 (64) being 64 bit, the compiler may emit optimizations that the non (64) variants may not. This will optimize it for the computers that the tests are running on, rather than intentionally handicapping it to keep the performance more similar to other languages. It was discussed when it was added a month or two back •  » » » » » 14 months ago, # ^ | 0 I see. I'll check out that blog. Thanks! •  » » 14 months ago, # ^ | ← Rev. 2 → +25 I suggest you make a blog, I would like to know the answer to this too. I mean this is literally double the speed compared to the other 2.I tried resubmitting some of my code too and its significantly faster •  » » 14 months ago, # ^ | +16 With GNU C++ 17 I think it is slightly faster or there is a little bit more optimization.I can be wrong, but you have long long (64-bit) type in your solution. That's why GNU C++ 17 got TL while 17(64) got AC — it works 2 times faster with 64-bit numbers. •  » » 14 months ago, # ^ | ← Rev. 2 → +8 pretty sure operations with long longs are one instruction each in 64-bit, but multiple in 32-bit, so long longs are a lot faster with 64-bit. •  » » » 14 months ago, # ^ | ← Rev. 2 → 0 That seems to be it; I switched to integers and got the same execution time, but half the memory usage.PS: congrats on the red, the color changed right after my refresh on posting •  » » 14 months ago, # ^ | -10 That's plain said on codeforce's part, sire! Very poor backend indeed. Need to take a learning or two from codechef. •  » » 14 months ago, # ^ | 0 This blog might be related.  » 14 months ago, # | +79 ![ ]() •  » » 14 months ago, # ^ | +11 what in tarnation  » 14 months ago, # | ← Rev. 3 → 0 GG loosing 700 points for long long . . ., i just changed long long to int and got accept in D1C, why should the constraints be that much though? •  » » 14 months ago, # ^ | -10 I think int should pass. As the distance to n can be at max (r+g)*m. •  » » » 14 months ago, # ^ | 0 I know that, but on that point i couldn't see any point to avoid long longs. •  » » » » 14 months ago, # ^ | -16 I think long long might not pass because it might print numbers like this: 3e9+5  » 14 months ago, # | +23 Problem were nice anyway, thx (especially D1C, E)  » 14 months ago, # | -10 Div1E is so beautiful! I still do not fully understand why my solution pass, but it is so stupidly elegant! Unfortunately, made some mistakes in code during contest... Tnx for the wonderful problem :)  » 14 months ago, # | +5 Apparently creating variables CAN be your code's bottleneck: 77824459 77859221 •  » » 14 months ago, # ^ | +20 This is rather particular to std::vector; vector::clear() doesn't actually deallocate the vector's internal buffer, so reusing the vector means you actually do many fewer dynamic memory allocations. This is compounded by the fact that vectors dynamically resize as you push_back (doubling when necessary), so you're actually saving a couple allocations per loop. You might be able to pass the problem by just doing vector::reserve(...).  » 14 months ago, # | +23 Hacked 3 greedy solutions in D1-B using very simple case: 1 2 0010010 (This corresponds to a digit 1.)Answer should be 4, but greedy solutions that consider the first compatible digit in descending order would pick 7 first then report impossible. Since there is 1 remaining broken segment, and such solutions only consider "patching" 9 -> 8 in such cases. And solutions which consider the first compatible digit in ascending order would pick 1, and report impossible as well.  » 14 months ago, # | 0 Anyone can explain better how to solve Div1C-Div2E with 0-1BFS instead of dijkstra. Please. Thanks in advanced •  » » 14 months ago, # ^ | ← Rev. 2 → +44 Construct a graph. Let a vertex in the graph be a pair$(i, k)$where$i$is the index of some intersection (sorted), and$k$is the number of seconds which have passed since the light most recently became green. Every vertex (except when$i = 0$or$i = m-1$) has two outbound edges, corresponding to the intersections before and after it (changing$k$as we would expect). Note that we can only transition if we have enough time left before the light changes. In the case where we have to wait for a red light at the destination intersection (i.e. we reach the destination exactly as the light turns red), label the edge with weight$1$, otherwise$0$. Now run 0-1 bfs to find the shortest path to all vertices.Once bfs is finished, iterate over all vertices$(i, k)$. If the destination is reachable from this vertex in less than$g$seconds, the final answer for this vertex is$(r+g)\cdot c+k+n-d_i$where$c\$ is the cost to reach this vertex in the graph. Output the minimum final answer for all vertices.
•  » »