### vovuh's blog

By vovuh, history, 2 months ago, translation, ,

<almost-copy-pasted-part>

Hello! Codeforces Round #629 (Div. 3) will start at Mar/26/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria ZeroAmbition Stepanova, Mikhail pikmike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

</almost-copy-pasted-part>

Thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for help with testing the round!

UPD: Also thanks to Vitaliy kuviman Kudasov for testing the round!

UPD2: Editorial is published!

• +352

 » 2 months ago, # |   -38 Is it _overrated_ XD.
 » 2 months ago, # |   +138 We want more contest in this "Corona" era . Thanks a lot bro.
•  » » 2 months ago, # ^ |   -20 Following
•  » » 2 months ago, # ^ |   -17 Why don't u visit ur recent contests and upsolve the easiest unsolved problems? :-)
•  » » » 2 months ago, # ^ |   +1 I do brother. But live contest has the maximum awesomeness.. You know what I mean. <3
•  » » 2 months ago, # ^ |   -6 yes. I agree brother. This is a very good way to keep busy. Happy Coding. :D
 » 2 months ago, # | ← Rev. 2 →   +55 Due to Home Quarantine registration will exceed 22k for sure :)
•  » » 2 months ago, # ^ | ← Rev. 2 →   +9 Obviously, what could be a better way to spend time ? ;)
 » 2 months ago, # | ← Rev. 2 →   +94 Hope everybody uses Face Mask and keeps distance from others like The Codeforces logo :)
•  » » 2 months ago, # ^ | ← Rev. 2 →   -57 Ok, I get it. That was not funny.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Wasn't that the coronavirus?! :PDue to unexpectedly large number of participants in the Lunchtime, our systems were unable to handle the load, and we are forced to stop the contest, which will be unrated.
 » 2 months ago, # |   +80 We want at least 2 contests per week in this time of pendemic Corona.
•  » » 2 months ago, # ^ |   +63 Why ? be greedy ... I want at least 7 contests per weak ... (in the rest of the day Ill upsolve the contest)
•  » » » 2 months ago, # ^ |   +39 It's not an easy job to prepare contests and come up with 5-7 problems.
•  » » » » 2 months ago, # ^ |   +16 I know ... but many contests are in queue ...
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   +37 You can attempt to come up with about 12 decent problems (and with 4 hard problems that can make for Div. 1) that people will not scream "shitty mathforces/bruteforces/dataforces/etc.", write a bunch of tests, stress-test that, ask a bunch of testers to test your problems, find corner cases and stress-test again, reject 6 out of said problems, etc.. Writing a contest is NOT easy, and if you are so insistent on having a contest, how about go write yourself one? We will see the quality of your problems.
 » 2 months ago, # |   +44 One contest per 3 days will be good for us.
 » 2 months ago, # |   +49 CodeForces is making our Quarantine interesting by hosting regular contests...
•  » » 2 months ago, # ^ |   0 The problem makers are also in Quarantine. So, they have more time than ever before to create more problems.
 » 2 months ago, # |   +5 Thank God that coding does not transmit Corona infection :) Thank you very much *-)
 » 2 months ago, # | ← Rev. 2 →   +2 What can be more interesting work to do in quarantine than solve some classical competitive programming questions set by vovuh and learn from our mistakes that we do in real time contest. Thanks Codeforces.
 » 2 months ago, # |   0 I'm still new on codeforcesCan someone explain what it means that the penalty is 10 minutes ?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +10 In the resulting scoreboard, participants are compared first by the number of solved problems, then by the total penalty time — for every solved problem, it is the time taken to solve it (in minutes) and 10 minutes for every unsuccessful submission on it.
•  » » » 2 months ago, # ^ |   0 Thank you <3
•  » » » » 2 months ago, # ^ |   +5 Just to make it clearer: you won't be penalized 10 minutes of solving time during the contest: you will have full 2 hours to solve the problems regardless of your submissions.
•  » » » » » 2 months ago, # ^ |   0 Thank you got it
•  » » » » » 2 months ago, # ^ |   0 So basically if we have a WA submission it will add up 10 mins to our submission time in the scoreboard right?We won't actually have to wait 10 mins to make a submission?
•  » » » » » » 2 months ago, # ^ |   0 Yes, penalty of 10 minutes is added to your submission time, you don't have to wait for 10 minutes to submit. Do note that TLE is also a rejected submission and is penalised with +10 minutes.
 » 2 months ago, # |   0 How do I configure vim like tmwilliam in his YouTube videos? e.g:-font,keybindings,etc.I am a beginniner in vim.
•  » » 2 months ago, # ^ |   +7 Why don't you ask him? How would others know his configuration?
•  » » » 2 months ago, # ^ |   0 Please post his reply here too.
•  » » 2 months ago, # ^ |   0 have a look at the other people's dotfiles (.vimrc to be specific) in github
 » 2 months ago, # |   +4 Waiting for the moment when i'll be participating unofficially in these rounds :(
•  » » 2 months ago, # ^ |   +1 I found that even orginal 1500 rating is hard to reach.:(
•  » » » 2 months ago, # ^ |   0 But goals need to be bigger than our achievements.
 » 2 months ago, # |   +1 I just wait for div3 contests :(
•  » » 2 months ago, # ^ |   0 yeah me too.
»
2 months ago, # |
+11

We want more contest to pass our home quarantine time with coding.

# staywithcoding

 » 2 months ago, # |   +38 I think that this contest may turn out to be a Codeforces Server Pressure test (CSP)!
•  » » 2 months ago, # ^ |   0 CSP...
 » 2 months ago, # | ← Rev. 6 →   -6 I got troubled to submit my solution at the last time of contest
 » 2 months ago, # | ← Rev. 3 →   0 Please make strong pretest cases!!
 » 2 months ago, # |   +2 Contests these days are of much help to kill time.Many thanks to Codeforces!
 » 2 months ago, # |   +2 regular contest with two days gap will be good in current situation...
 » 2 months ago, # |   0 I wish you all a good performance in this round.
 » 2 months ago, # |   0 It would be great if the contests are organised on a regular basis or atleast every alternate day, coz this is the time we need them the most.
 » 2 months ago, # |   -9 I really love div.3 rounds
 » 2 months ago, # |   0 We need more of this, we ain't got nothing to do on this pandemic
•  » » 2 months ago, # ^ |   0 we ain't got nothing to doYou could always practice previous contests...
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +2 Well There is much less thrill in doing virtual contests psychologically.
 » 2 months ago, # |   -18 I'll 爆杀 in this contest. Hope everyone good luck!
•  » » 2 months ago, # ^ |   0 (That's very dangerous! Keep yourself safe and don't get killed during this contest)
 » 2 months ago, # |   0 Please increase the number of round,s per week.These days it's difficult to spend a day without contest.
»
2 months ago, # |
+6

Codeforces is Best thing to do in home quarantine.

# Keep Social Distancing.

 » 2 months ago, # |   +8 We need more contests during self-isolation))))
 » 2 months ago, # |   +13 can we have this website in dark mode? it will be easier on the eyes.
•  » » 2 months ago, # ^ |   0 maybe you can try this, in case you didn't know go to chrome://flags and search dark in the search bar, then you can select enabled with selective inversion of everything and then relaunch the chrome
•  » » 2 months ago, # ^ |   0
 » 2 months ago, # |   +10 Thank god. I'll finally have a break of 2:00 hrs in which I'll not regret my life which I've been doing this whole quarantine
 » 2 months ago, # | ← Rev. 5 →   -19 just be an expert
•  » » 2 months ago, # ^ |   +4 Maybe you are expected to be an expertImprove your spelling and everyone will expect you to be an expert
•  » » 2 months ago, # ^ |   -11 such a bold statement
 » 2 months ago, # |   -15 +18k registrations till now, I hope our submission won't take too long to be judged.Best of luck CF servers
 » 2 months ago, # |   0 Effect of Corona !!
 » 2 months ago, # |   -14 I think codeforces should restrict registrations at 25k or something.. Excess load might cause servers to remain down. A good contest for few is better than no contest at all. :/
•  » » 2 months ago, # ^ |   +3 Not for the ones who don't get to take it.
 » 2 months ago, # | ← Rev. 2 →   -10 please...I want more contest in this "Corona" season. Because live contest is better solution for passing boring time
 » 2 months ago, # | ← Rev. 2 →   +4 please more contests in this "corona" time live contests feels more competitive than virtual :) ;
 » 2 months ago, # |   +3 wish you successful home quarantine...CF Registration amount proves, you are fighting against corona...
 » 2 months ago, # | ← Rev. 2 →   0 Hope it will be great as always)
 » 2 months ago, # |   0 OMG 20k participants!!!
•  » » 2 months ago, # ^ |   0 Because all are home quarantine and love coding.
»
2 months ago, # |
0

# protect covid-19

I hope we will get the quarantine and isolation related problem.

 » 2 months ago, # | ← Rev. 2 →   +2 Already 22000+. Today total registration gonna be 24k+Stay Home. Stay Safe.Be a Compititive Programmer.
 » 2 months ago, # |   +2 Seeing the number of registrations, I already opened m1.codeforces.com XD
»
2 months ago, # |
Rev. 4   +6

Wow!! 22000+ Registration!!!
Now Waiting for 23000+

# Corona_fact

 » 2 months ago, # |   0 I bet there will long submission queue !!. 23K !! Dayyyummm !!!
 » 2 months ago, # |   +1 Has the number of participants broken the record?
•  » » 2 months ago, # ^ |   0 YUP
•  » » » 2 months ago, # ^ |   0 _hit What was the previous record?
•  » » » » 2 months ago, # ^ |   0 Last edu round had 20k+ registrations. Before that it was ~18k.
 » 2 months ago, # |   +18 very weird problem d
•  » » 2 months ago, # ^ |   -24 It was dp, and I really liked the problem; something unique. I don't think I can explain more, since my own solution was very messy. Hope the pretests were strong.
•  » » » 2 months ago, # ^ |   +12 it can be solved with greedy approach pretty easily too
•  » » » » 2 months ago, # ^ |   0 Could you, please, elaborate? Because I couldn't really think of any approach, at all (just Pupil things :)) — but I am getting better). I tried DP and backtracking, but got lost in the details and couldn't implement them properly.
•  » » » » » 2 months ago, # ^ |   +20 Ok, so we would like to assign colors in following pattern: 1 2 1 2 1 2.. We will assign same color to all segments with equal numbers in it, so for sequence like this: 3 3 3 1 1 2 4 5 5 the colors would look like this: 1 1 1 2 2 1 2 1 1. Now the only problem is that first and last element can still be different and have same color assigned to it. To fix that we take any segment of length >= 2 and change color of last element in it to to opossite one and recalculate the color array. For previous example it would look like this: 1 1 (2) 1 1 2 1 2 2. In case there is no segment of length >= 2, simply set color of last element to 3. https://codeforces.com/contest/1328/submission/74454901 — my implementation
•  » » » » » » 2 months ago, # ^ |   0 Wow, that's actually pretty simple. I understood perfectly, thanks! :D I didn't realize that the maximum number of colors would always be three — I thought there were some cases where you'd need four or more colors (though I couldn't find any).
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 That's an awesome solution!
•  » » » » » 2 months ago, # ^ |   0 It was a very hard implementation for me at least lol. First, if there is only one kind of number in the array, answer is 1, so paint all of them as 1.Second, if n is even, paint them in alternate colors 1,2,1,2 and it will be correct for every input.Third was problematic, answer can be 2 or 3, depending on the number of adjacent elements which are different. If that number is even the answer is again 2, other wise its 3.
•  » » » » » » 2 months ago, # ^ |   0 For case t=[1,2,3] we need 3 colors [1,2,3] and for t=[1,2,2,3,3] we need 2 colors [1,2,1,2,2]. So your explanation is not true.
•  » » » » » » » 2 months ago, # ^ | ← Rev. 5 →   0 1 2 3, if written in a circle have 3 adjacent elements that are different (1 2) (2 3) and (3 1), thus the answer is 3. Sorry for not clearing this, count includes all the adjacent elements including the first and last. Although You are right, it is wrong for other test case like 1 1 2 2 2 2 3, because it says 3 colors are required, but it can be done one 2.
 » 2 months ago, # |   0 Everybody is enjoying their home quarantine or lock down situation. The huge number of participants says that. right? ;)
 » 2 months ago, # |   +3 anybody else that couldn't participate due to the heavy load on servers?
 » 2 months ago, # |   +3 anybody else that couldn't participate due to the heavy load on servers?
 » 2 months ago, # |   +1 Can E be solved using LCA?
•  » » 2 months ago, # ^ |   +11 I tried to do it using LCA, but my solution gave WA on test 56.
•  » » » 2 months ago, # ^ |   0 Mine gave WA on test 53.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +2 Yes.The observation is that all the parents of the nodes in a query has to be in the same path.So find the parent of each node in a query and check if they are in the same path from root using LCA.
•  » » 2 months ago, # ^ |   +1 I used LCA, and passed it.
•  » » » 2 months ago, # ^ |   0 Link of your solution?
•  » » » » 2 months ago, # ^ |   0 74483153 my lca solution
 » 2 months ago, # |   0 Almost 25K registrations! Really Coronaforces)
 » 2 months ago, # |   0 how to solve D?
•  » » 2 months ago, # ^ | ← Rev. 4 →   +4 I only consider 4 situations: all elements are the same : (1 color)1 1 1... the length of the elements is even : (2 colors)1 2 1 2... and now we just need to think situations where the length of the elements is oddif t[1]==t[n] then: 1. (2 colors)1 2 1 2...else if t[1]!=t[n] and at the same time there exist one i(1<=i<=n-1) where t[i]==t[i+1] then: (2 colors)1 2 1 2... otherwise: (3 colors)1 2 1 2 ... 3
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 What if 7 3 3 4 4 4 4 4 . If I am not wrong according to your algorithm, the answer should be: 1 2 1 2 1 2 1 . But here t[n] is not equal to t[1] and they are also adjacent, then how they got same the colors?
•  » » » » 2 months ago, # ^ |   0 since there is one index i satisfy the condition t[i]==t[i+1], we can paint the same color on i and i+1. So for your example, since the first element is equal to the second element, you can paint these elements into 1 1 2 1 2 1 2, and it is correct. I got to go to bad now, if you don't understand somewhere, i will let you know tomorrow :)
•  » » » » » 2 months ago, # ^ |   0 I got it! Thanks a lot!
•  » » 5 weeks ago, # ^ |   0 Think greedily. Try to use minimum number of colors to color figure 1 upto n-1(you can color these n-1 figures maintaining all constraints using 2 colors only) and then think is you can color figure n with a color already used. If not then give it a new color!!!
 » 2 months ago, # |   +4 Is it only I or everyone was facing issues with the speed of loading for codeforces. I submitted 3 mins before the end of the contest but still, it didn't get submitted.
•  » » 2 months ago, # ^ |   0 Try using m1.codeforces.com next time, I sent all my submissions from there with no problem (while I couldn't submit sometimes from www.codeforces.com)
 » 2 months ago, # |   0 could you tell me how to slove the problem D by easy algorithm
•  » » 2 months ago, # ^ | ← Rev. 2 →   +9 If you like graphs you can see it is a coloring problem. Your vertices are the different animals and there is an edge between them if they are of a different type and adjacent. Now you want to color this graph, such that all adjacent vertices have different colors. This gives you three cases: 1. If the graph has no edges (ie only one type) you only need one color The graph is not a cycle, then you need two colors, since you can just color any path as 1212... The graph is a cycle, then it is important whether it has an odd or a even length (if you are interested how this generalises look up bipartite graphs) If the length of the cycle is even, then you can't color it in a 1212...1 fashion, since the first and the last edge would have the same color. Therefore you need three colors and can color it like 1212...23If the length of the cycle is odd than you only need two colors and can color it like 1212...2I hope that is understandable :)
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +3 Or more simply put ; if the graph is non-bipartite ; then print the bipartite coloring.If it is bipartite ; it would be because two adjacent vertices get the same color while bipartite coloring ( This is the odd length cycle case ) . Color one of these vertices to some 3rd color ; and then say Yayy! when u receive AC !Code
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 Suppose input array is 1 , 2 , 3 , 4 .Now the graph will be square 1---2--3--4 and 4 is connected to 1. .I can color vertex '1' as 1 , '2' as 2 , '3' as 1 , '4' as 2 and thus no consecutive vertex of the graph has same color.But you have mentioned that we cannot color cycle of even length.Please tell if you are saying something else.Also in your post some times you have written color the 'vertex' and some times you are saying that edges have been colored (though both should not make any difference in case of cycle)
•  » » 2 months ago, # ^ |   +23 If there is only $1$ type of animal, then the answer is $1$ color. We can simply print $1$ $n$ times.If $n$ is even then the answer is $2$. We simply print alternating $1 2 1 2 . . .$So, we are left with the case when $n$ is odd. If we can find any $i$ such that $type[i]=type[i-1]$(cycle included, i.e. $type[0]=type[n-1]$) then the answer is $2$, as the parity can be switched. Otherwise, the answer is $3$.To print the colors with answer $2$, you can alternate $1$ and $2$ with the exception of $i$ where $type[i]=type[i-1]$. Put that as the same color. This changes the parity.
•  » » 2 months ago, # ^ |   +2 If all elements are same, answer is 1 If all elements are distinct and number of elements is odd, answer is 3 otherwise answer is 2if all are distinct, simply print 1 2 1 2 ... like this otherwise take every segment containing distinct elements and fill it by 1 2 1 2... those are left, give any colour to them
•  » » 2 months ago, # ^ |   0 By observation it can be seen max distinct color required will be 3. Now if n is even 1212.. pattern will work if there are more than one number. For all same obvious 1 color will be required. Now for odd n, consider if there are at least 2 contiguous same number in cyclic array in that case color required will be 2 otherwise 3
•  » » 2 months ago, # ^ | ← Rev. 2 →   +1 You can solve D without graphs as well. It can be solved greedily. If n is even, just print "1 2" n/2 times If n is odd but a[0] == a[n-1] print "1 2" n/2 times with an extra "1" in the end If n is odd but there is a point where arr[i] == arr[i-1], then from 0 to i-1 print "1 2" and from i to n-1, print "2 1" If none is true, print "1 2" n/2 times with an extra "3" in the end Corner Case (it was for me): If all are same print "1" n times.
 » 2 months ago, # |   +40 Whoever made D is a sadist. T_T
•  » » 2 months ago, # ^ |   -7 It was very unique; I loved it. I solved it using dp, but it was very messy.
 » 2 months ago, # |   +7 Detailed video for FHere
•  » » 2 months ago, # ^ |   0 thanks it was helpful
•  » » 2 months ago, # ^ |   0 please can you tell me why using library sorting I am getting TLE but with radix sort it passes my_sub constrain is just n= 2*10^5 so O(nlogn) is fine right the why?
•  » » » 2 months ago, # ^ |   0 in Java, arrays.sort can run in O(n^2) in some conditions.I'm not well aware of how this works in Java, but I heard that can be the case sometimes.
•  » » » » 2 months ago, # ^ |   0 Thanks got it... Btw for java users here is the link explaining this in detailsAlso inbuilt sorting from Collections class(for list) of java passes it efficiently my_sub..mainly I converted array to list then Collections.sort(list) .
 » 2 months ago, # |   +1 I thought I would never complain about that but 101 tests in E did make my submission take a lot of time to be judged :)
 » 2 months ago, # | ← Rev. 2 →   +8 I don't know whether someone else has experienced this or not but codeforces was taking way too much time to show up. And many times it just says some error has occurred (my connection was good enough). Kind of annoying during the contest.
 » 2 months ago, # |   0 Too much traffic
•  » » 2 months ago, # ^ |   +13 my account is getting logged out without my intervention!!
•  » » » 2 months ago, # ^ |   0 same
•  » » » 2 months ago, # ^ |   0 same.
•  » » » 2 months ago, # ^ |   0 Same
 » 2 months ago, # |   0 I suprised that with that much number of registrants, the main page still worked faster than m1
 » 2 months ago, # |   +1 I've got 403, 503, 504, 502 not once or twice) Who got more 'AC'?
 » 2 months ago, # |   +4 (At least)last three minutes of the contestthe sites were inaccessible(including the lightweight websites like m1.codeforces.com).I had no chance to submit my problem D solution.
•  » » 2 months ago, # ^ |   0 m3 worked fine
•  » » 2 months ago, # ^ |   +2 m3 worked for me, I submitted at 1:57
•  » » 2 months ago, # ^ |   0 m2 worked fine as well.
•  » » 2 months ago, # ^ |   0 I submitted from m2 in the last 3 minutes
•  » » 2 months ago, # ^ | ← Rev. 2 →   +2 It seems, then, that it was m1 which I was unhappy with: I tried both main site and one of m1/m2/m3 (not sure which one).P.S. Now it's not a big deal :) for me(managed to submit in practice mode, my solution is wrong).
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 I think it is problem of internet in your country, not codeforces.
•  » » » » 2 months ago, # ^ |   +1 usually it works fine in my countryalso, Bad Gateway response from server looks more like server overload problems, not like connection problems on a client side
•  » » 2 months ago, # ^ |   0 same got 503 multiple times, and it was irritating.
 » 2 months ago, # |   +1 I finally thought I had found all the corner cases for D but it still gave me WA. Are we sure they generated all the possible outputs? xD
•  » » 2 months ago, # ^ |   0 I used dp as I didn't need to worry about handling all corner cases explicitly XD (P.S. I couldn't think of any corner cases).
•  » » 2 months ago, # ^ |   0 Ok, reading j_peters comment above I just found what I was missing. It was a narrow miss and just because I'm dumb >D My fault
•  » » 2 months ago, # ^ |   +1 1 2 2 3 Ans 2 colours Check this
•  » » » 2 months ago, # ^ |   0 Yea, you're right. I missed the fact that you could use any two adjacent of the same type to flip the sequence and use 2 colours, not just the last ones.
 » 2 months ago, # |   0 Second pretest prob D why this answer is wrong ? 2 1 2 2 1 2 2 
•  » » 2 months ago, # ^ |   0 Why do you believe it is considered wrong?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Because that's what my code prints, when I submit it show me WA pretest 2!EditSorry my bad I though pretest 2 = query 2.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +1 Are you sure it says pretest2 and not Test 2?? You can look with more detail to where did it fail from your submissions tab.EDIT: Oh, ok then, no problem
 » 2 months ago, # |   0 Is this contest rated?
•  » » 2 months ago, # ^ |   0 For those under 1600, like me, yes
 » 2 months ago, # |   0 Had worst experience ever in this contest....Became frustrating when even problem submission taking a hell lot of time.
 » 2 months ago, # |   0 what the fuck! I can't access the codeforce after submitting A until div3 over! It always show 403 forbidden or log out my account. No other meaning, I'm just bringing up what happened to me.
•  » » 2 months ago, # ^ |   0 Use the lightweight mirror sites. Such errors are to be expected in contests with a large number of participants. After all CF isn't a for-profit company, and can't buy up a large amount of servers unless really necessary.
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 I also have tried to log in m1 mirror site, but it not work. But thanks codeforce for providing a practice environment to me.
•  » » » » 2 months ago, # ^ |   0 then you should try m2,m3 also
 » 2 months ago, # |   0 is this round rated? cause the server was extremely slow and i could not even submit some codes
 » 2 months ago, # |   0 vovuh please make it unrated for me or consider my d solution. I submitted this solution at 22:00 butdue to netowrk traffic or i don't what happened hasn't got submitted. I am saying so because my solution was right otherwise I wouldn't requested you(I submitted as soon as connection got back). Please refer to my issue
•  » » 2 months ago, # ^ |   0 I had the code for D wrttien with 15 mins to go, but couldn't submit at all. I was finally able to submit in the last minute and it gave wrong answer :(
•  » » » 2 months ago, # ^ |   0 I submitted at 22:00 but I don't know what happened because of some site error i didn't get submitted. BTW my solution was correct I submitted it without any changes
 » 2 months ago, # |   -39 Make the contest unrated because lot of people couldn't submit their solutions :/
•  » » 2 months ago, # ^ |   0 Yes!
•  » » 2 months ago, # ^ |   +18 The mirror sites worked just fine.
•  » » 2 months ago, # ^ |   +80 Hi, sorry about it. I'm working on performance improvements. But am I right that m1/m2/m3 worked well most time? I explicitly suggested to use them in case of any technical issues, right?
•  » » » 2 months ago, # ^ |   +14 With a few exceptions towards the beginning, M2 worked fine for me throughout the round.
•  » » » 2 months ago, # ^ |   0 in Italy we had problems even using the mirror websites :c so i guess it would be better to make it unrated
•  » » » » 2 months ago, # ^ |   0 I even faced that problem
•  » » » » 2 months ago, # ^ |   +2 don't ask for making round unrated (under the name of slow servers). The actual reason is that your rating will go down (because you solved only two questions). Even though you are complaining that the server was slow, I see that you have already made a lot of submissions. How many more did you want to make
•  » » » » » 2 months ago, # ^ |   0 well, you can even see i got AC with basically the same code (i tried to submit it during the contest, but the website and the mirror1 weren't working) ten minutes later the end of the contest.(the other submission in the same minute is an error, i submitted the wrong file)
•  » » » » » » 2 months ago, # ^ |   +18 Then it's your responsibility to check mirror2 and 3 as well. The rounds prepared with so much of hard work cannot be made unrated because of a few people's nuisances. I hope you take that positively
•  » » » 2 months ago, # ^ |   +4 It is already unrated for me, but it was so sad I couldn't submit E. It's good to know about the mirror sites. I didn't know about them.
•  » » » 2 months ago, # ^ |   0 Honestly the main one worked pretty fine for me..
•  » » » 2 months ago, # ^ |   0 Faced issues even with M1 website. Was not able to load questions. Had to re-submit code few times. If many people faced such issues , maybe we make this contest unrated ?
•  » » » 2 months ago, # ^ |   +1 M3 worked fine as well
•  » » » 2 months ago, # ^ |   +1 For me all m1,m2,m3 worked just fine !
•  » » » 2 months ago, # ^ |   +1 I used m2 , it worked fine
•  » » » 2 months ago, # ^ |   0 Nah ! I got frustated and tried both m1 and m2, none worked.
•  » » » 2 months ago, # ^ |   0 m1 and m2 didn't work.
•  » » » 2 months ago, # ^ |   0 sir i have no experience using m1,m2 and m3 then , i thought it would free up after one or two reloads but that was not the case,i was logged out around 5-6 times
•  » » » 2 months ago, # ^ |   0 I want to know why I am unraded in div3
•  » » 2 months ago, # ^ |   0 Yes please
 » 2 months ago, # | ← Rev. 2 →   +8 The moment I realized that my 'expert dream' was broken! Btw, how to solve E in the time limit?
•  » » 2 months ago, # ^ |   0 Instead of iterating to find kTH ancestor, precompute LCA(using binary lifting) and rest is same what you are doing.
•  » » » 2 months ago, # ^ |   0 I got it, thank a lot!
•  » » » 2 months ago, # ^ |   0 Can you please elaborate?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +3 distance(u,lca(deepestnodeInTheQuery,u))<=1 for all u in the query.
•  » » 2 months ago, # ^ |   0 What I understood in your solution that you're trying to get the depth of every node in the tree, then what else? cause I didn't get the idea of the second part of the code after the BFS call
•  » » » 2 months ago, # ^ |   0 In each query, I make a path from the root to the vertex which has the biggest level. Every vertex in that query or their parent must belong to that path :(
•  » » 2 months ago, # ^ |   +22 Actually one can evade writing full-fledged LCA at all. To do this, just notice that you are only interested in parents of the marked vertices. Checking whether one node is an ancestor of the other can easily be done if you use time when DFS enters and leaves the node (tin / tout). AFAIK, there were absolutely no problems with TL with this approach.
•  » » » 2 months ago, # ^ |   0 Agreed, I just did it this way. https://cp-algorithms.com/graph/lca_binary_lifting.htmlThe above is about LCA, but you can see the implementation has an is_ancestor subroutine which is enough for this problem. So it's an O(n) time solution.
 » 2 months ago, # |   0 Unable to submit due to 403, 503 errors or slow server response. I am very frustrated. What is the cause of this problem. I am also think that problem C was not in the good place. It should be problem A or B.
 » 2 months ago, # |   +1 Can someone explain how to solve B? I feel stupid.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 I solved using a recursive function with one added extra parameter except N and K: cntB -- the number of 'b' characters which should be present in the string (it can be 0, 1 or 2).The problem can be solved trivially for cntB=0 and cntB=1. After solving for those two cases, you can consider cntB=2 as having two subcases: one with first letter 'a', the other with first letter 'b'. (Note that the number of cases started with 'b' is easy to calculate if you already colved cntB=1 case.)I think this solution (74434027) is not optimal but it was somethink I could think out more or less quickly, worked for me.
•  » » 2 months ago, # ^ |   0 Consider position of the left 'b', let that pos be $n-p$ Then there exist $p-1$ strings with left 'b' at that position, because you can place the right 'b' at $p-1$ positions.Implement a loop counting the number of these strings with increasing $p$.
•  » » » 2 months ago, # ^ |   0 can you please share your code?
•  » » » » 2 months ago, # ^ |   0 74425278Note that after klick on a user you can see that ones submission after click on 'Submissions'.
 » 2 months ago, # | ← Rev. 2 →   0 Very frustrated because the website was not working properly(errors) may be due to heavy load on website..The questions did not load fast and also to submit had to reload the page again and again
 » 2 months ago, # |   0 How to use dp in D? I solved using a lot of if else statements
•  » » 2 months ago, # ^ |   0 for problem D, my solution was thislet the continuous elements form a grp,if #grps == 1 then all same colorelse if #grps is even then only 2 colors (alternate colors) else if #grps is odd and #grps == n then 3 colorselse if #grps is odd and #grps < n then we can do with 2 colors only , we just have to color the last element of a continuous grp (of sz > 1) with a color diff from that of the members of the same grp and continue alternatingbut this gave WA on TC2, dont know why
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 (I got WA on test case 2 at first) Try a test case like 1 3 1 2 1 and make sure your coloring is valid.
•  » » 2 months ago, # ^ |   0 after the contest, i implemented a dp solution and left a lot of comments, check it out if you want https://codeforces.com/contest/1328/submission/74505814
 » 2 months ago, # |   0 Could someone help me figure out what is wrong with my submission in Problem E 74478785
•  » » 2 months ago, # ^ |   0 An edge from u to v doesn't mean that u is the parent of v if we build the tree from root 1
 » 2 months ago, # | ← Rev. 2 →   -6 More than 23K people participated!!! I think it is a new Record!!
 » 2 months ago, # |   -22 One of the worst Div3's contests i have ever been entered !!The site broken down many many times through the contest !! specially at the end of the contestThe difficulty of the problems Wasn't properly distributed well at all !!!Thank You!
 » 2 months ago, # |   +7 Service was not so much bad comparing whith load..
 » 2 months ago, # | ← Rev. 3 →   +2 Anyone experienced something like this after submitting solutions. HTTP Status 403-Forbidden(Sorry I am not able to upload the image in comments. So here is the link of the screenshot I am talking about: https://pasteboard.co/J0UgDjL.png I submitted my solution for A and C and experienced this screen and assumed that my answer got submitted but it wasn't and it was happening throughout the contest.
•  » » 2 months ago, # ^ |   0 I also face this type of problem, today.
•  » » 2 months ago, # ^ |   0 same problem
•  » » 2 months ago, # ^ |   0 Tughe kya lgta hai mike tere liye contest cancel karwayega
 » 2 months ago, # |   +7 I want more contest. It is the best way to spend time!
 » 2 months ago, # |   +18 I solved E in O(N+K) (K is the total sum of k_i) using offline querys and dfs. If you guys solved it with O(NlogN) complexity, have a look at my solution :Dhttps://codeforces.com/contest/1328/submission/74433847
•  » » 2 months ago, # ^ |   0 Online?
•  » » » 2 months ago, # ^ |   0 Offline here means you grab all queries and process them all at once as you know the input data (here the tree structure) won't change.
•  » » » » 2 months ago, # ^ |   0 Can you solve it Online?
•  » » » » » 2 months ago, # ^ |   0 Sorry I misunderstood what you meant. I saw your submission on E. Sounds very interesting. For those you may be interested: https://codeforces.com/contest/1328/submission/74446758
•  » » » » » » 2 months ago, # ^ |   0 Can you solve it Online && o(n) ?
•  » » » » » » » 2 months ago, # ^ | ← Rev. 3 →   0 Yes, I can think of two ways to do this1). Fast LCA in $O(1)$ using Farach Colton Bender algorithm 2). Precompute in and out times in dfs traversal for each node. This let's you answer $is\_ancestor(a,b)$ in $O(1)$ time.
•  » » 2 months ago, # ^ | ← Rev. 2 →   -8 I solved E in O(N + KlogK)(K is the total sum of k_i) but answering queries in online. My solution: 74522963
 » 2 months ago, # | ← Rev. 5 →   +5 To solve E, I used binary lifting technique on the tree. I precomputed for each node $log(n)$ parents using dfs(same preprocessing which is done for LCA). To process each query, I pick the node with index $i$ that has maximum depth among the $k$ nodes which are given in the query then I simply check for any other node in $v$ if:-$v[j]$ is an ancestor of $v[i]$ on the path from $1$ to v[i] with distance equal to $depth[v[i]]-depth[v[j]]$ from $v[i]$-$v[j]$ is the child of the ancestor of $v[i]$ on the path from $1$ to $v[i]$ with distance equal to $depth[v[i]]-depth[v[j]]+1$ from $v[i]$if none of these two conditions is fulfilled then the answer is "NO" and if at least one of these two is fulfilled for all nodes in $v$ then the answer is "YES" for this query.
•  » » 2 months ago, # ^ |   -11 This task has a simpler solution.
•  » » » 2 months ago, # ^ |   0 What is it?
•  » » 2 months ago, # ^ |   0 Online && O(n)
•  » » » 2 months ago, # ^ |   0 You have a solution n log you use sorting.
•  » » 2 months ago, # ^ |   0 I think that's a bit easier: Sort all $v[i]$ by their depth. Take the deepest one ($v[0]$) and lift it to the depth of $v[1]$. They must either be the same vertex or have the same parent. Keep lifting $v[0]$ to all remaining $v[i]$.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Why am I getting a WA on tc 56. Any hints to the testcase.Thanks in advance!!My Solution
•  » » » 2 months ago, # ^ |   +3 Won't it cause TLE if the tree is "straight" because in that case deepest node will have depth = n so time complexity would be O(m*n) ?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +3 Good question! This is what the binary lifting technique solves (as mentioned by amiratou): for each node, you store its parent, its 2-parent (parent's parent), 4-parent, ..., $2^k$-parent up to $L = \log(n) \approx 19$. Then you can jump through the tree in $L = O(\log n)$ steps for each $v[i]$.The statement guarantees that the total size of queries is under $2 \cdot 10^5$, so this should work.
 » 2 months ago, # | ← Rev. 3 →   0 Thanks, Codeforecs as this is the best thing in which we can contribute our quarantine time period.But in this contest, a lot of issues were there because of server and problem D even I am not able to submit the solution of problem D because of the server error. No regrets, Hail Codeforces!!
 » 2 months ago, # |   0 My rating right now is less than 1600 but it is showing me as unofficial participant in this contest... This is may be because i registered when I was expert... So finally whether i will be considered Official or not in this contest?
 » 2 months ago, # |   0 Giving this div 3 contest for first time on this platform would have been a lot more fun if their web server wouldn't have stopped responded which took the peace of my mind. It took me a lot of time to understand that I have to go to one of those light websites, login again, wait for 3 minutes and refresh the page to see the verdict. It was a total mess.
 » 2 months ago, # |   +9 There was problem in submitting code It showed Http error while submission
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 I had the same problem during contests
 » 2 months ago, # |   0 How soon editorial will be because there are a lot of interesting and hard problems?
 » 2 months ago, # |   +3 How to solve D?
•  » » 2 months ago, # ^ |   +11 answer 1 — when all the numbers in the array are the sameanswer 2 — when you have n% 2 = 0 or when you have two consecutive identical elements (you can change the parity, draw there is not difficult))answer 3 — everything else (paint the first vertex in color 3, and then alternate 1 2)
 » 2 months ago, # |   0 http://codeforces.com/contest/1328/submission/74484167Can anyone explain me whats wrong in my solution for D ?I basically looked for an adjacent pair of equal values. If such pair exists then answer would surely be 2 (or 1). I started giving colors accordingly based on comparision of a value with it's preceding one.If such pair doesn't exist then answer would either be 2 or 3 depending on whether number of elements is even or odd.
•  » » 2 months ago, # ^ |   0 what's your output for this 7 1 2 3 1 2 3 ?
•  » » » 2 months ago, # ^ |   0 You mean 7 7 1 2 3 1 2 3 I suppose ?I'm getting 3 1 2 1 2 1 2 3
•  » » » 2 months ago, # ^ |   0 nvm, got it !
•  » » » 2 months ago, # ^ |   0 what should be output for this?
•  » » » » 2 months ago, # ^ |   0 3 colours, 1 2 1 2 1 2 3
•  » » 2 months ago, # ^ |   0 Here's a countertest: 1 6 1 2 3 4 5 1 You output 2 2 1 2 1 2, which is clearly invalid.
•  » » » 2 months ago, # ^ |   0 Damn, should have worked according to my logic, didn't code it properly i guess ;(Thanks a lot for your help
 » 2 months ago, # | ← Rev. 2 →   0 Can anyone hack this submission. Not able to find why it is right or wrong :(Thank You
•  » » 2 months ago, # ^ |   +3 I did not run any testcases, just went through your code and i think your logic is right.You have sorted in decreasing order of levels, and after that for each pair you have checked if their lca is either equal to the latter or its parent. This is what I understood from your code.This is correct in my opinion because suppose answer is YES, then it is mandatory that a vertex with greater level lies in subtree of all vertices with level lower than its own or in case a vertex of lower level is replaced by some other element at distance 1, then from it's parent. Since you have sorted in decreasing order so transitive relation will hold within the vertices i.e if u lies in subtree of v with level[u] > level[v] and v in turn lies in subtree of w with level[v] > level[w] then u lies in subtree of with level[u] > level[w] and above condition will hold true.
 » 2 months ago, # | ← Rev. 3 →   +5 The questions were standard however the server was very slow and had a very bad gateway. I had been trying for logging in for the past 20 minutes and submit however I was not able to doIt would be nice if you make the contest unrated.
 » 2 months ago, # |   0 Please either consider by third question I submitted during the contest or unrate it !! The contest was a total mess I couldn't upload my solution !! Really frustrating!!!!
 » 2 months ago, # |   +3 Why during the contest codeforces has thrown me out of its profile many times and I couldn't open tasks ? Also I couldn't join to m1, m2, or m3 codeforces. Why this bad things happen to me? Who had same problems?
•  » » 2 months ago, # ^ |   +1 Same problem buddy
 » 2 months ago, # |   0 This time, the contest was at a very good level. The problem D had the exact amount of difficulty which should be there for creating a margin between participants and it saved the contest from becoming a speedforces :)
 » 2 months ago, # |   0 Anyone knows why https://codeforces.com/contest/1328/submission/74488792 is accepted (Python) and https://codeforces.com/contest/1328/submission/74488483 is not (PyPy) as generally PyPy is faster than Python. Cost me 1 hour...
•  » » 2 months ago, # ^ |   0 Probably bad string concatenation, which CPython is helpfully optimising to $O(n)$. See my comment here: https://codeforces.com/blog/entry/74235#comment-589125
•  » » » 2 months ago, # ^ |   0 Thanks!
 » 2 months ago, # |   +3 recently police arrested div.1 guys... 'cause the site was underage. p.s. -- i tried submitting problem D solution during last minutes, but site kept on crashing... phew! 24K contestants
•  » » 2 months ago, # ^ |   0 Following.
•  » » 2 months ago, # ^ |   +2 Very correct
 » 2 months ago, # | ← Rev. 9 →   0 can someone tell me the problem in this code.I'm getting WA for B. or any good corner test case. i used val=(-1+sqrt(1+8k))/2 and position of b=n-1-val || n-k+(val*(val-1))/2 https://codeforces.com/contest/1328/submission/74481937
 » 2 months ago, # |   +1 Conduct contests alternatively on day basis. Quarantine days.
 » 2 months ago, # |   0 seems like vovuh prepared these questions for Educational round and it posted as div3 by mistake lol
 » 2 months ago, # | ← Rev. 3 →   0 As mentioned in the annoncement that it will be unrated for participants with rating >=1600,but still it is showing me as a trusted participant and also there are lots of expert in official standing. Does anybody know why this is haapening?
•  » » 2 months ago, # ^ |   0 You must have registered before turning blue
 » 2 months ago, # |   0 Can someone get penalized for unsuccessful hack attempt in div 3 contests?
•  » » 2 months ago, # ^ |   0 No there is no points for successful hack as well as no penalty for unsuccessful hack in div3 rounds.
•  » » » 2 months ago, # ^ |   0 Is there points/penalties for hacks in educational rounds?
•  » » » » 2 months ago, # ^ |   0 No.
 » 2 months ago, # | ← Rev. 2 →   +3 i was logged out almost 5-6 times, it was showing bad gateway all the timeand logging in would take another 5-6 minand this might have happend to many usershttps://i.imgur.com/zVqJ4a1.jpg@codeforces do something about it in future and about this round
•  » » 2 months ago, # ^ |   +1 And this https://imgur.com/ubmZOeL
 » 2 months ago, # |   -13 How to Solve D if it is compulsory to paint the same type of animals with the same color, and we have to minimize the total number of colors used as given in the problem statement.vovuh pikmike
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Sadly thats NP complete, you can easily reduce the normal vertex coloring problem to it.
•  » » » 2 months ago, # ^ |   0 Didnt get you. Could You please elaborate.Thanks j_peters
•  » » » » 2 months ago, # ^ |   0 Do you know what NP-completness is?
•  » » » » » 2 months ago, # ^ |   0 Yes I do, but I dont know what you mean by the normal vertex coloring problem!
•  » » » » » » 2 months ago, # ^ |   0 Just the problem of deciding whether a graph has a k coloring is NP-complete (https://en.wikipedia.org/wiki/Graph_coloring). And you can reduce this problem to the problem described by you.
 » 2 months ago, # |   +1 The server was too slow! I couldn't even read some problems and check my verdict after submissions! I hope Codeforces will fix the issues in future contests because it affects our ratings!
 » 2 months ago, # |   0 MikeMirzayanov Its not good. I was using m1.codeforces.com during the contest and while solving problem d , no clarification came that two same adjacent species can have different colors too. throughout the contest i was getting wa bcoz of this fact. why no announcement appeared on mirror sites.
•  » » 2 months ago, # ^ |   +4 It was pretty clear from the problem statement itself that two same and adjacent species could have different colours. You should maybe try and read the problem carefully than complain.
•  » » 2 months ago, # ^ |   +4 I think you are wrong, as many participants (it is just my opinion). This issue is even considered in examples and you just didn't see it as many of the participants who asks us about this. The second test case of the example: $t = [1, 2, 2, 1, 2, 2]$, $c = [2, 1, 2, 1, 2, 1]$. $t_5 = t_6$ and $c_5 \ne c_6$.
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 vovuh My complain is only that, why updates are not visible on mirror sites. I am not complaining about the question. But if new updates would have appeared then it would be good for participants who use mirror sites for faster access. MikeMirzayanov
•  » » » » 2 months ago, # ^ |   0 Okay, if you complain only about this, then I agree with you that notifications and clarifications should be allowed in mirrors because it's unfair and it's an advantage for other participants. But don't forget the initial target of these mirrors: they were created to allow users read and solve problems almost offline even if the main site doesn't respond (afaik). I don't sure but hope this issue will be fixed.
•  » » » » » 2 months ago, # ^ |   0 Yes, one might get the right approach or atleast understand what the question is really asking, where sometimes people face difficulties due to some lack of clarifications. so if updates are also appear on mirror sites then its good. leave it, no issue. i will open one main tab of cf.com aside of mirror site, to get any notifications. thanks for reply.
•  » » » » » » 2 months ago, # ^ |   0 I even didn't notice there was a notification for that problem. This failure could be a good experience for future contests. Personally, I won't start thinking on a problem, let alone coding, if I don't understand every corner of a problem statement.
 » 2 months ago, # | ← Rev. 3 →   0 Why am I unofficial??? MikeMirzayanov Vovuh
•  » » 2 months ago, # ^ |   0 You might have registered while you were blue.
•  » » » 2 months ago, # ^ |   0 In that case MikeMirzayanov, this is bug should be solved.
 » 2 months ago, # |   +3 Sadly, a lot of O(n^2) and O(k) solutions are passing for B i think
•  » » 2 months ago, # ^ |   +1 I think no , in worst-case : n = 10^5 or k = 10^9 ,So: if O(n^2) = 10^10 OR if O(k) = 10^9 this will give TLE that if also T = 1 , Let's say if T = 10^4 and n = 10^5 in evey test-case so complexity will be equal : 10^10 * 10^4 = 10^14 this absolutely TLE :). So i think every solution O(n^2) or O(k) if pass in pretests will Fail in final test.
•  » » » 2 months ago, # ^ |   0 It is probably because of some compiler optimization ig.
 » 2 months ago, # |   0 How to solve Problem F using DP?Thanks!
 » 2 months ago, # |   0 How to solve C ?? idea needed
•  » » 2 months ago, # ^ |   0 The idea is quite simple,we have to minimise the maximum of two numbers. 0 can be written (0+0)%3,now for 2 we have two possibilities either (0+2)%3 or (1+1)%3,using the latter it is guaranteed the solution won't become worse and is optimal. For the final part, 1 can be written as (0+1)%3,adding 1 to any string guarantees that string to be greater than the other one in decimal format. Now we can append 0s to that string and x[i] to the other string.
•  » » 2 months ago, # ^ |   +11 We know the following:$0 = (0+0)\mod 3$ $1 = (0 +1)\mod 3$$2 = (1+1)\mod 3$ or $(0+2)\mod{3}$We loop $i$ from $0$ to $n-1$:For $c[i]=0$: we simply append $0$ to both a and b.For $c[i]=1$: we append $0$ and $1$ to $a$ and $b$ respectively. After doing this the first time, we would always have $a>b$, so we append the reverse i.e. $1$ and $0$ to $a$ and $b$ respectively. This minimises $a$, the maximum of the two.For $c[i]=2$: we append $0$ and $2$ to $a$ and $b$ respectively, once we have encountered $c[j]=1$. Otherwise, we simply append $1$ to both $a$ and $b$. We can see this easily if we take a number which has no $1$. We would try to distribute $2$ evenly, as we want to minimize the maximum.
 » 2 months ago, # |   +1 My solution for Question D without using Graphs and DP.https://codeforces.com/contest/1328/submission/74499296
 » 2 months ago, # |   0 can someone explain the code in editorial of this problem?Codemonk-Best Index
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Here is my code with explanation. code... #include using namespace std; typedef long long ll ; int main() { ll n ; cin >> n ; vector v; for(ll i = 1; i <= n ; ++i){ ll x; cin >> x; v.push_back(x) ; } ll pref[n] ; pref[0] = v[0] ; for(ll i = 1 ; i < n ; ++i){ pref[i] = pref[i-1] + v[i] ; } vector toadd ; toadd.push_back(0); toadd.push_back(2); while(true){ ll prevdiff = toadd[toadd.size() - 1] - toadd[toadd.size() - 2] ; ++prevdiff; ll now = toadd[toadd.size() - 1] + prevdiff ; toadd.push_back(now) ; if(now > 1e5) break ; } /// toadd is an array containing the numbers which can be added to index i /// that is , we can add 0 , 2 , 5 , 9 , 14 ... to index i each time. ll ans = -1e18; for(ll i = 0 ; i < n ; ++i){ /// choose i_th index as the special index , then check how far can u go . /// from i , you can go to i + 2 , i + 5 , i + 9 and so on .. /// means add 0 to i , 2 to i , 5 to i , 9 to i /// do a binary seach to find how far can u go from index i by taking one at a time , /// then 2 at a time , then 3 at a time and so on .. ll till = i ; ll low = 0, high = toadd.size() - 1; while(low <= high){ ll mid = (low + high) / 2 ; ll curr = i + toadd[mid] ; if(curr <= n-1){ till = curr; low = mid + 1 ; } else high = mid - 1; } // cout << " i is " << i << " tioll " << till << endl ; if(i == 0){ ans= max(ans , pref[till]) ; } else { ans = max(ans , pref[till] - pref[i - 1 ]); } // cout << " ans is " << ans << endl ; } cout << ans << endl ; return 0 ; } 
 » 2 months ago, # |   0 Need idea for B , i got TLE using stl next_permutation.
•  » » 2 months ago, # ^ |   0 u will get tle as there can be n^2 permutations.
•  » » 2 months ago, # ^ |   0 You cannot use next_perm function as it will calculate n*n perms.you simply need to find positions of both the b's.
 » 2 months ago, # |   0 Is there any other way to solve E rather than LCA?? Can somebody please help with what is the problem in this approach,, Link : https://ide.geeksforgeeks.org/jws6KpkplH
•  » » 2 months ago, # ^ |   0 Lets say what len[i] is length from root to i. We have some nodes in query, lets sort they by their len and group by this len in some map sort_by_len. lets say current_root — root of lasts nodes. Go through the sort_by_len and say, what if nodes with the same len have different parent we don't have answer. Of course if it is a root of tree we need to update current_root = 0; If they have the same parent = current_parent, if we dont have current_root we need update it = current_parent, in another case we need to say what this current_parent is child of current_root (we can do it using tin and fup time in tree in O(1)). In case if it isn't we don't have answer. And update current_root.
•  » » 2 months ago, # ^ |   +5 Well I wasn't able to understand your code. But indeed you can solve it in O(nlogn) using dfs. There is another version of DFS, where you store arrival and departure time of every node. Search for it. 1 For answering every query, just sort parent of all vertices with increasing depth. (Depth is a distance of node from root that can be calculated using dfs and parent too). 2 Now for each vertex let's say v, check if arrival time is moe than or equal to vertex u and departure time is less than Equal to vertex u. (Here is the first vertex vertex in the sorted list of vertices) 3 If not then answer is NO else it's YES. :)
 » 2 months ago, # |   +1 i had an issue at problem C usually i use Kotlin for my submissions i had TLE at test case 5 i made another submission using same code but in java this time and i got an acthe kotlin sub : https://codeforces.com/contest/1328/submission/74481945 the java sub : https://codeforces.com/contest/1328/submission/74513383
 » 2 months ago, # |   +9 More div. 3 contest pls ~.~
 » 2 months ago, # |   +2 Admins, please check out these two submissions: Submission 1 Submission 2
 »