### Newtech66's blog

By Newtech66, 2 months ago,

Hello, Codeforces!

TimeWarp101 and I are excited to invite you to Codeforces Round #782 (Div. 2) which will take place on Apr/17/2022 17:35 (Moscow time). This round will be rated for participants with rating lower than 2100.

Many thanks to all the people who made this round possible:

You will have 2 hours to solve 6 problems.

Scoring distribution: $500-750-1500-2000-2250-3000$

We've tried to keep the statements short and pretests strong. We hope you will enjoy the round!

See you all in the standings!

P.S. namanbansal013 will be livestreaming his solution explanations for some of the problems here. Do check out his channel too!

UPD: We are really sorry for the issues with the queue, but we hope you liked the problems anyway.

UPD: Editorial

UPD: Congratulations to the winners!

Official winners:

Unofficial winners:

First solves:

1. A: SSRS_ at 00:01
2. B: SSRS_ at 00:03
3. C: PurpleCrayon at 00:07
4. D: noimi at 00:17
5. E: CoderAnshu at 00:21
6. F: rainboy at 01:06

• +469

 » 6 weeks ago, # |   +62 Interesting tags.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   -37 Finally an Indian round, it's been a long time.
•  » » 6 weeks ago, # ^ |   -6 orz
 » 6 weeks ago, # |   +28 Good Luck everyone!!
 » 6 weeks ago, # |   +30 As a tester,
 » 6 weeks ago, # |   +15 Soooooooooo excited!!
 » 6 weeks ago, # |   +67 Probably one of the best Div2 rounds I've tested this year ;)
 » 6 weeks ago, # |   +22 As a tester I will say problems are are very good and interesting.
 » 6 weeks ago, # |   +27 where anime girl?
 » 6 weeks ago, # |   +53 Can you tag me for being a deadly pillow?
 » 6 weeks ago, # |   +1 I wish everyone high rating and may you solve your next alphabet { C for me :) }
•  » » 6 weeks ago, # ^ |   +5 i was not able to solve :{ still i learned a lot form this round
•  » » » 6 weeks ago, # ^ |   0 I also tried my best
•  » » » » 6 weeks ago, # ^ |   0 Yes i guess u misassigned the value of I :}
 » 6 weeks ago, # |   0 " We've tried to keep the statements short and pretests strong. We hope you will enjoy the round! "best of luck
•  » » 6 weeks ago, # ^ |   -15 WOW Thanks. So Atcoderforces
 » 6 weeks ago, # |   +31 As the legendary AwakeAnay has tested this round, it must be legendary as well. Don't forget to take part!
 » 6 weeks ago, # |   +47 The contest is held at my birthday :D Hope for luck so I am not longer hard stuck in candidate master :)
•  » » 6 weeks ago, # ^ |   -90 Hii I am from india.plezz help me I want to join with you. Can you help me in coding plzz help me how to join with you. you have any source then I can join with you any instagram Id or what'sapp number or fecbook Id or Telegram Id you have plz give me....plz reply
•  » » 6 weeks ago, # ^ |   +11 Happy Birthday!
•  » » 6 weeks ago, # ^ |   0 Happy birthday to you :) Wish you all the best
 » 6 weeks ago, # |   -8 Last two rounds were unlucky for me( Wish this round would be one of the best rounds!
 » 6 weeks ago, # |   +1 Hope I can make it to cyan this round. So close.
•  » » 6 weeks ago, # ^ |   +8 I believe in you!
•  » » » 6 weeks ago, # ^ |   +1 Thanks for believing in me. I'll get it next time though :)
•  » » » » 5 weeks ago, # ^ |   0 You did get cyan though.
•  » » » » » 5 weeks ago, # ^ |   0 This is only because some cheaters were removed from last contest (previously I was 2 points away from Specialist, but when cheaters got removed, turns out my delta was more :) ), and the result for last contest is temporarily rolled back. I should go back under Specialist once results are rolled back :)
 » 6 weeks ago, # |   +68 As a tester, this is the first round I've ever tested!
 » 6 weeks ago, # |   +4 "i_am_completely_useless for being completely useless." -- Sakura :))xD
 » 6 weeks ago, # |   +8 As a not tester of the round i hope that it would be good
 » 6 weeks ago, # |   +3 Good Luck All!!!
 » 6 weeks ago, # |   +29 I'm pumped!
•  » » 6 weeks ago, # ^ |   +3 Hello pumped!, I'm AR69420.
•  » » » 6 weeks ago, # ^ |   +7 Hello AR69420, I'm pumped!
•  » » » » 6 weeks ago, # ^ |   +7 Hello pumped!, I'm AR69420.
•  » » » » » 6 weeks ago, # ^ |   +7 Hello AR69420, I'm pumped!
•  » » » » » » 6 weeks ago, # ^ |   +14 Hello pumped!, I'm AR69420.
•  » » » » » » » 6 weeks ago, # ^ |   0 Hello pumped!, and hello AR69420.
•  » » » » » » » » 6 weeks ago, # ^ | ← Rev. 3 →   -22 .
•  » » » » » » » » » 5 weeks ago, # ^ |   0 Hello Pain_373! Are you pumped!
•  » » » » » » » » » 5 weeks ago, # ^ |   0 Not yet! Shailesh_Rathod
 » 6 weeks ago, # |   0
•  » » 6 weeks ago, # ^ |   +2 Song slaps.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 (narrator voice) "He will not become blue after this round."
 » 6 weeks ago, # | ← Rev. 3 →   0 wanted to upvote ur blog but didn't Spoilerbcz ur contri is +69 :)P.S. Upvoted now :) Spoilerbcz ur contri is not +69 :(
 » 6 weeks ago, # |   -48 As not a tester, give me positive contribution.
•  » » 6 weeks ago, # ^ |   -21 As not a tester, give him negative contribution
 » 6 weeks ago, # |   +8 As a tester, I am a tester.
 » 6 weeks ago, # |   0 As the last contest as a newbie for me :3
•  » » 6 weeks ago, # ^ |   0 Hopefully...
 » 6 weeks ago, # |   +1 Indian rounds are always interesting, most of them have a lot of math problems)
 » 6 weeks ago, # |   0 Excited
 » 6 weeks ago, # |   0 ExcitedWooooooooooooooooooooooooooooooo!
 » 6 weeks ago, # | ← Rev. 2 →   -43 Remember, if you see this name antontrygubO_o, this is gonna be another XorForces contest.
•  » » 6 weeks ago, # ^ |   0 Who cares you participate or not?
•  » » 6 weeks ago, # ^ |   +4 Sure
•  » » » 6 weeks ago, # ^ |   +56 Thank you xor your opinion
•  » » » » 6 weeks ago, # ^ |   +5 xOrlympia
•  » » 6 weeks ago, # ^ |   0 I mean BitForces.
 » 6 weeks ago, # |   +1 SOOOOO EXCITED ABOUT IT!!!
 » 6 weeks ago, # |   +10 https://youtu.be/CVC2gQY8V1kdoki doki waku waku~I've been obsessed with this song lately
 » 6 weeks ago, # |   +7 good luck for everyone
 » 6 weeks ago, # |   0 thanks !!!!!!
 » 6 weeks ago, # |   +6 Thank You all for arranging such a wonderful contest.
 » 6 weeks ago, # |   +3 As it is mentioned statements are short and pretests strong , it would be more interesting.
 » 6 weeks ago, # |   +7 Hope I turn Pupil this round :)
•  » » 6 weeks ago, # ^ |   +4 Good luck!
 » 6 weeks ago, # |   +26 So, what topics of JEE are we gonna revise today? :)
 » 6 weeks ago, # |   0 keep going
 » 6 weeks ago, # |   0 Hope I could solve B and C problem today...
 » 6 weeks ago, # |   0 As a contestant, I wish all of you good luck!
•  » » 6 weeks ago, # ^ |   +3 thanks <3
 » 6 weeks ago, # |   0 I hope that pretests are strong
•  » » 6 weeks ago, # ^ |   0 That's what he mentioned
•  » » 6 weeks ago, # ^ |   0 That's what she said
 » 6 weeks ago, # |   0 Good Luck everyone!!
 » 6 weeks ago, # |   +8 Bad difficulty of A.
•  » » 6 weeks ago, # ^ |   +6 When a chinese said it's hard you know you're fucked up.
•  » » » 6 weeks ago, # ^ |   0 hh
 » 6 weeks ago, # |   +3 Yes, you guys really have kept the statements short. Good job!
 » 6 weeks ago, # |   +1 queue!!!!
•  » » 6 weeks ago, # ^ |   0 same !
•  » » 6 weeks ago, # ^ |   0 Big bruh moment indeed.
•  » » 6 weeks ago, # ^ |   0 +
 » 6 weeks ago, # |   0 Am, I the only one, who is facing server problem
•  » » 6 weeks ago, # ^ |   0 same(
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 no, I am also facing the same.
•  » » 6 weeks ago, # ^ |   +4 Nah I can't submit anything it will be unrated most likely. They've got to figure this out, it's too popular of a platform for this to be consistently happening.
 » 6 weeks ago, # |   +5 My code is in queue for too long. What should I do?
 » 6 weeks ago, # |   0 queueforces
 » 6 weeks ago, # | ← Rev. 2 →   0 mm
•  » » 6 weeks ago, # ^ |   +1 I don't see any other option.
•  » » 6 weeks ago, # ^ |   +1 Pretty sure they have to make it unrated now. It's been like 15 minutes
 » 6 weeks ago, # |   -8 I am waiting queue a lot of min please codeforces fix this my rank now -100
 » 6 weeks ago, # |   0 IN codforces a lot of queues ! It is bad
 » 6 weeks ago, # | ← Rev. 2 →   +20 i sumbitted my same code twice , one at the main site (which crashed due to queue) and another at the alternate cf site after reloading ...now both have passed prestests , plz consider my first code and remove penalty! Newtech66 MikeMirzayanov P.S. Thnx , my 2nd sumbission got skipped.
•  » » 6 weeks ago, # ^ |   +4 Hi — I've actually done similar (on C). I did so as my first submission wasn't showing (not even as in queue), I agree any such penalties should be removed.
•  » » » 6 weeks ago, # ^ |   -23 Or just make the round unrated anyway if they can't do that.
•  » » » 6 weeks ago, # ^ |   0 Thanks for skipping my second duplicate submission.
 » 6 weeks ago, # |   0 Please make it unrated, there will be a lot of discrepancies because of the delay
 » 6 weeks ago, # |   +26
•  » » 6 weeks ago, # ^ |   0 then even problem a is hacked ;))
 » 6 weeks ago, # |   +36
 » 6 weeks ago, # | ← Rev. 2 →   0 .
 » 6 weeks ago, # |   +17 Is it just me or problem's difficulties kinda messed up today?
 » 6 weeks ago, # |   +20 C < B < A, cool round. But D is very interesting
•  » » 6 weeks ago, # ^ |   +1 Can't solve C LOL
•  » » » 6 weeks ago, # ^ |   0 And that's because I didn't read this statement: "You cannot conquer a kingdom if there is an unconquered kingdom between the target and your capital." Damn it.
•  » » » » 6 weeks ago, # ^ |   0 I think this statement is redundant anyway. You cannot achieve a better score if you jump over a kingdom like that. I also missed that statement and had to infer it myself, losing a bunch of time...
•  » » 6 weeks ago, # ^ |   0 I think B > A > C, Bad experience :(
•  » » » 6 weeks ago, # ^ |   +5 Its hard to code B, but idea isnt so hard
•  » » » » 6 weeks ago, # ^ |   0 I spent an hour on the coding of question B. :(
•  » » 6 weeks ago, # ^ |   +1 B > C > A imo
•  » » 6 weeks ago, # ^ |   +1 Same here, was able to solve B, C, and D but I was stuck with A.
 » 6 weeks ago, # |   +7 I had such a hard time solving A. Hopefully my last submition goes through system testing XD
 » 6 weeks ago, # |   -27 It was the worst contest this year.
•  » » 6 weeks ago, # ^ |   +3 Maaaaaaaaybe, but contests this year were all reaaally good so that woudln't be anything bad.Problem A was too hard — that's for sure.Problem B was kinda boring, but implementation heavy and bug prone (at least in my case).Problem C was really nice though.Problem D was nice as well.Not sure about rest as I didn't read them.
 » 6 weeks ago, # | ← Rev. 2 →   +13 Key observation for E (Hopefully obvious for most people): The answer can only be between 0, 1, 2. Then it just boils down to having dsus for each bit.
•  » » 6 weeks ago, # ^ |   +8 I know that answer can only be 0, 1, 2, and I can find when answer is 0. But how to find when asnwer is 1?
•  » » » 6 weeks ago, # ^ | ← Rev. 3 →   +25 So basically what I did was I maintained the dsus for each bit and an extra dsu just for zero-length edges. Then, for each edge, we examine whether if its length is odd or even. If it is even, then we mark both nodes as "good" as using this edge would ensure that the and-sums would never reach 1. Then, for each of the dsus, except for the one maintaining $2^0$ bit, we mark the components that has a good node to be good since it means that within the component, there is a path/walk to a good node and whilst doing so, the and-sum would never reach 1 as all the edges within this particular dsu would have $2^k$ bit set throughout. Thus, to check if the answer is one, we just check for each of the dsus (obviously except for the $2^0$ bit dsu), we check if the component is "good" and if so, the answer should be one. P.S. Sorry for a long, messy explanation
•  » » » 6 weeks ago, # ^ | ← Rev. 6 →   0 the idea for how to determine whether or not the answer for $(v,u)$ can be 1 is that since the path prefix AND is non decreasing there will be a point in the path $v \rightarrow v_{0} \cdots v_{i} \rightarrow v_{i+1} \cdots \rightarrow u$ where the prefix AND of $v_i$ to $v_{i+1}$ jumps from a value $x$ to something even where $x$ is odd and bigger than $1$, this is equivalent to $x$ having the $0^{th}$ bit on and at least one other bit on. we can check for this by iterating what the one other bit can be. setup 30 dsu with the $i^{th}$ dsu only using edges with weight having both the $0^{th}$ and $i^{th}$ bit on. the answer can be $1$ if for one of the dsu's there exist an edge from $v$'s cc to outside of $v$'s cc such that the AND value becomes even
 » 6 weeks ago, # | ← Rev. 2 →   -8 solutions from B to D can be found in youtube.https://www.youtube.com/channel/UCVul5dRaN-0ZUpwMdOjfiug/videos
•  » » 6 weeks ago, # ^ |   0 Big F
•  » » 6 weeks ago, # ^ |   +5 WTF!! This really hurts honest participants. And I was wondering it's me who has become too dumb to rank this bad in a contest. Now I see what might have happened, apart from me becoming dumber.
•  » » 6 weeks ago, # ^ |   +2 Damn, cheaters really suck
 » 6 weeks ago, # |   +8 Noice round!!! But A could've been a little bit on the easier/non-complex side!
 » 6 weeks ago, # |   0 what do you mean by this line "There is some issue with the judging system" ?can a correct solution can be judged incorrect when there is judge issue . Try not to downvote me
•  » » 6 weeks ago, # ^ |   -6 ok bro
 » 6 weeks ago, # |   0 when pretest 2 is given and you don't check that and make error in pretest 2 . Spoiler...
•  » » 6 weeks ago, # ^ |   +3 I didn't know this. I thought it would be logic to not count the wrong answer for any sample test, not only the first one.
•  » » » 6 weeks ago, # ^ |   +6 same I didn't knew this before too. but I guess it makes sense since they might have removed penalty from test case 1 coz many people submit other solution code (or maybe different language might be choosen) by mistake.
•  » » 6 weeks ago, # ^ |   +3 what?! I didn't know that too, and now I'm sad because i got 2 WA's on the first problem on test 2 :(I thought that sample tests never count as wrong answer!
•  » » 6 weeks ago, # ^ |   0 now I realised that I've been penalized for WA on 2 on problem A :P, I just submitted and left on codeforces to let me know whether my code is passing samples or not. This is sad, It should be quite logical to add no penalties for samples whether it being 1 or 2 or more samples.
 » 6 weeks ago, # |   +3 A candidate master should be able to solve problem A on a div2...That aside, problem E seemed nice, even though I can't solve.
 » 6 weeks ago, # |   -35 Good problems. And don't make any problem or contest anymore.
•  » » 6 weeks ago, # ^ |   +24 Problem $E$ was nice, and $D$ seemed okay. $A,B,C$ were pretty bad imo.
•  » » » 6 weeks ago, # ^ |   +32 I pretty like B. Actually only A is bad imo, but also not that bad. Do you guys dislike those problem because they are too hard?
•  » » » » 6 weeks ago, # ^ |   0 B was annoying, I would have swapped it with C
•  » » » » 6 weeks ago, # ^ |   +43 if problem A isn't guessable in less than a minute my dopamine neurons shut down for the rest of the contest unfortunately, skill issue
•  » » » » » 6 weeks ago, # ^ |   0 yes exactly this
 » 6 weeks ago, # | ← Rev. 4 →   +8
•  » » 6 weeks ago, # ^ |   0 that's seriously fucked up i just hope they all get skipped
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +1 Cheaters suck
•  » » 6 weeks ago, # ^ |   0 and i was thinking all the time that i am dumb for C sed lyf??
 » 6 weeks ago, # |   0 Any hints to solve A ?
•  » » 6 weeks ago, # ^ |   0 The string looks in he end likeRRRRBRRRRBRRRRB...So there are b+1 blocks of R. So each block must not be longer that (r+b)/(b+1)
•  » » » 6 weeks ago, # ^ |   +47 string goes !(BRRRRR)
•  » » 6 weeks ago, # ^ |   0 Partitioning a length $r$ stick into $b + 1$ components while minimizing the length of each stick is basically what the problem is asking about. From this observation, you could see that the maximum length would be ceiling function of $\frac{r}{b + 1}$. Hope this helps
•  » » » 6 weeks ago, # ^ |   0 My tried to go with this approach. But my solution didn't pass the pretests: https://codeforces.com/contest/1659/submission/153923182
•  » » » » 6 weeks ago, # ^ |   0 Countertest:1 11 7 4Your code yields RBRBRBRBRRR, which unfortunately has three consecutive 'R's in the end.
•  » » » 6 weeks ago, # ^ |   0 Thank you!
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Distribute the 'R' characters as equally as possible between the gaps of 'B' characters. for instance : B_B_B we would distribute 'R's equally in those gaps ( denoted by ___ )
•  » » 6 weeks ago, # ^ |   0 suppose you want to divide all r's into (b+1)sets and you have to minimize the number of maximum r for all (b+1) sets ...first put equal number of r in each set that you can find by r/(b+1) and now you can distribute one r from (r%(b+1)) and at the end of each set you can put 'b' just don't put b in last set end.
•  » » 6 weeks ago, # ^ |   +4 Forgive my poor English. Just try to put "R" between "B" evenly。 For example,if you have 3 "B", than you should try to put all "R" on the underline averagely _____B______B______B______.
•  » » 6 weeks ago, # ^ |   0 think about dividing the string to blocks of 'R' and figure out how to distribute Rs between them number of blocks = b+1 number of Rs we can distribute equally between all blocks = number of Rs /number of blocks the remaining Rs = number of Rs%(number of blocks ) then find way to distribute the remaining
 » 6 weeks ago, # |   -12 Really wack contest.
 » 6 weeks ago, # |   -10 probably the only contest of my life where i wasn't able to solve even one problem. damn it.
 » 6 weeks ago, # | ← Rev. 2 →   +12 I couldn't solve A. Felt that it was misplaced, or maybe I'm just not good in solving constructive problems. B idea was nice. Implmentation was also okay. I got the idea for C 5 minutes after contest ending. A good problem in my opinion.
 » 6 weeks ago, # |   +3 How to solve D?
•  » » 6 weeks ago, # ^ |   0 (I didn't have time to finish it, but it seems to work mathematically)sum(all) / n = amount of 1 = sthen we go from the end, realize was the 1 on n — 1 pos initially (it was if the value == n) simulate the cancellation of last addition on the suffix using a tree of segments (-1 on s length suffix), s -=1 if there was 1,solve the problem for n — 1
•  » » 6 weeks ago, # ^ |   0 Work backwards from n-1 all the way to 0. 153940196 Only accepted after contest ended.
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   0 Try to find the zeroes present in the array. If c[0]!=0, then ar[0]=1 else ar[0]=0, with the help of c[0] we can find where is the 1st zero present in the array. let's say 1st zero presents at the jth position, then ar[0]*(i=0)+1*(j-i)+0*(n-j)=c[0]. With the above formula, we can find where the 1st zero presents in the array. Similarly, we can try to find the 2nd,3rd, and nth zero.
 » 6 weeks ago, # |   +5 this time i am proud to solve A !
•  » » 6 weeks ago, # ^ |   +3 me too
 » 6 weeks ago, # |   0 problem A was fire actually
 » 6 weeks ago, # | ← Rev. 2 →   +2 I feel that A and B are harder than usual contests. C is in normal difficulty. D is interesting: I came up with a rough construction very quickly but finalizing every detail took me a long time.
•  » » 6 weeks ago, # ^ |   0 was c dp i was trying greedy one but ended up wa in pretest 2 only??
•  » » » 6 weeks ago, # ^ |   0 C can be solved using O(n) brute force: trying each kingdom as the final capital (note that each time you only need to move the capital to the right and it's better to move it as soon as possible).
•  » » » » 6 weeks ago, # ^ |   0 actually i was thinking is is if after changing kingdom answer decreases then only change means if(changing kingdom+after cost
•  » » » » » 6 weeks ago, # ^ |   0 Your idea was fine, but you want to compare only with the cost that won't exist after moving the capital, that is, you wrote arr[i]*(n-1-i)*b) but it must be (arr[i]-sta)*(n-1-i)*b). That's all I changed and accepted.
•  » » » » » » 6 weeks ago, # ^ |   0 thanx man i don't know when will i stop complicating problem and silly mistakes.
•  » » » » 6 weeks ago, # ^ |   0 Any math / intuitive proof why this works?
•  » » » » » 6 weeks ago, # ^ |   +4 Here is a sketch proof: We can calculate costs of moving capital and capturing cities separately, we just have to minimize their sum Total cost of moving the capital does not depend on exact movement of the capital — for any $i < j < k$ we have $a * (x_k - x_i) = a * (x_k - x_j + x_j - x_i) = a * (x_k - x_j) + a * (x_j - x_i)$ It is optimal to move the capital as soon as possible (until its final position) — suppose at some point the capital was at $x_i$ and the last captured city was $x_j$ where $j > i$ and the final position of the capitol is $x_k$ where $k > i$, then we $x_i < min(x_j, x_k)$, so $b * (x_{j+1} - x_i) > b * (x_{j+1} - min(x_j, x_k))$
•  » » » » » » 6 weeks ago, # ^ |   0 Thanks! Got it now
 » 6 weeks ago, # |   +1 problems a and b are very hard as unusual !!
 » 6 weeks ago, # |   +1 Any hints to solve b and c?
•  » » 6 weeks ago, # ^ |   +1 for b try to find pattern for even k??
•  » » 6 weeks ago, # ^ |   +1 for problem c : for each kingdom assume that it's the final capital transfer and calculate its cost
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Problem B : Observation from few cases : 1.if k is even then it is optimal to perform operation on zeros in pairs that is first 2 significant zeros . Till we have even number of zeros and k > 0 we can perform this operation . 2.now if there were odd zeros : 1 zero would have been left after the 1st step above so it would be optimal to flip it with the last 1( only if the last 0 is not the last character in the string )3.if k is odd it is optimal to flip it from the firstone we encounter . If not available flip from the last character. This step makes k = k — 1 => k is even now follow 1 and 2 observations for k is even case
•  » » » 6 weeks ago, # ^ |   +1 I think it is easier to reduce the question to the following: Flip all the bits k times (meaning to say flip all the bits once if k is odd and do nothing otherwise). Then you need to do k operations of flip one chosen bit. It is easier to reason about things this way. Observe that flipping everything and then flipping one bit is an equivalent operation.
•  » » » » 6 weeks ago, # ^ |   +1 Thanks for the reply . This is a very crisp observation .
•  » » » » 6 weeks ago, # ^ |   0 THanks , your solution is simple and clear
•  » » » 6 weeks ago, # ^ |   0 Thanks a lot for your explanation. It helped a lot.
 » 6 weeks ago, # |   -27 Make this round unrated all the solutions were leaked on youtube
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   +35 Making the round unrated would be a slap in the face for those who did well.Probably barely anyone saw the solutions anyway and the queue issues were minor.Are we going to make every round for which solutions were leaked in some discord server unrated too? Then there would hardly be any point in rated contests anymore.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Queue issues weren't minor, they lasted for like 25+ minutes, which is, as for me, enough for a round to get unrated
•  » » 6 weeks ago, # ^ |   +6 I doubt you would have said this if your rank wasn't 6000++
 » 6 weeks ago, # | ← Rev. 2 →   0 Those who solved A after getting wrong answer at pretest 3, what was the corner case you considered?My approach, but getting WA: There are b+1 gaps to put r characters, so the number of red chars per blue char would be either r/(b+1) or r/(b+1) + 1. Repeat of sequence x r's & 1 b the viable number of times, and add any remaining characters. Cant figure out what is missing. Thanks a lot for reading
•  » » 6 weeks ago, # ^ |   0 I tried this. Heck, I even tried binary search. But for some reason, I WA'd on tc 3. I'm annoyed lol
•  » » 6 weeks ago, # ^ |   0 For me it was 14 8 6, my first solution was putting BBB at the end
•  » » » 6 weeks ago, # ^ |   +3 Okay, this is it. Thanks a lot afix!
 » 6 weeks ago, # |   -15 What your sorry will help me ??
 » 6 weeks ago, # |   +23 it's been a while since problem A wasn't a one liner
 » 6 weeks ago, # |   +3 Did the solution for F involve calculating the diameter of the tree?
 » 6 weeks ago, # | ← Rev. 3 →   +1 153940198 153938389. Agony. I was 20 seconds too late with the accepted one
 » 6 weeks ago, # |   0 problem E: get the idea that answer could only be 0, 1 or 2. Got how to check 0. Got idea to merge one bit along with 1. But didn't find out how to check if 1 is possible.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 For each vertex, if there is an edge that connect with this point and whose value is even, set the vertex as an “ok” point(that means if you walk to this point while the and number is not 1,then 1 will not exist.). Use DSU 30 times for each bit(edges whose value in this bit is 1).Query in DSU[1..29],if the block which vertex u is in has an "ok" point, that means we have a way to protect 1 from exist.
•  » » » 6 weeks ago, # ^ |   0 Yes. Got this after check some solutions.
•  » » 6 weeks ago, # ^ |   +11 To check for 1: the path will be one such that it won't have 1 and then it'll have 0's. So that means that that last number before the 0's will have some bit that isn't 1. For each bit, consider the paths including that bit. Inside of a connected component of the edges that have that bit, we can get a path that passes through every vertex and also every edge in that component (that minimizes the number of set bits in the AND of those edges) then we'll want to use some jump starting from that component that sets the AND to 0.
•  » » 6 weeks ago, # ^ |   0 You could have a look on my explanation above : Comment
 » 6 weeks ago, # |   0 How to do B??
•  » » 6 weeks ago, # ^ |   0 greedily try from left to right. if the parity of K and s[i] is same and there is still operations left, set ans[i] as 1. For the last digit, you have to set all left K on it.
•  » » 6 weeks ago, # ^ |   0 Look from different perspective: first the whole array swap k times and each time later we change one element. Then it's optimal to set as many element in the left as one as possible. This can be done in left to right order.
 » 6 weeks ago, # | ← Rev. 4 →   +1 I think solutions to D isYou can get the total number of 1s by taking the sum of input divide by the size. The reason for this is each 1 in the array add to the sum exactly n times.We can figure out the value of the last index easily, it should be fixed for n-1 times.We will solve this one by one from the last to the first.Let say after you sort the array at length 5, you got 00011xxx, then it's obvious that if there are more than 2 0s that come after it, it will push over the 1s and will become 0. You can use binary search to find out how many times the value of index ith remains 0 (assuming you already figure out what come after it);So just figure out the bit 1 by 1 from last index all the way to first index.AC submission: https://codeforces.com/contest/1659/submission/153945063
 » 6 weeks ago, # |   0 Hello, I'm new here. Why does it say that I am registered for practice? Does that mean the contest was unrated for me?
 » 6 weeks ago, # |   0 I figured out a solution of Problem D using Segment Tree though I have no time to finish it during the contest, any other simple ways of solutions? 153940308
 » 6 weeks ago, # |   +22 WTF!Why still rated since the judge server was down for 15 minute?
•  » » 6 weeks ago, # ^ |   +18 I’m so lucky that I used that 15 minutes to solve D.
 » 6 weeks ago, # |   +11 Problem F is much more difficult than other DIV2 contest, I'm so poor at Game Theory
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +11 F for me was basically write a stupid solution that solves the problem for all states (permutation, vertex) of a tree then making one observation (if the graph isn't a star graph then Alice always wins) and some case bashing, not interesting at all. Hopefully the editorial has some proof.
•  » » » 6 weeks ago, # ^ | ← Rev. 5 →   +54 I really enjoyed solving F (I managed to prove everything during the contest, and getting AC 1 minute before the end of the contest was very exciting).Anyways, here's the proof for why the diameter being at least 3 is sufficient for Alice to win:I'll use edge move on some edge connecting vertices $a$ and $b$ to denote swapping $a$ and $b$ in our permutation, and $dist(a,b)$ to denote the number of edges on the unique simple path from $a$ to $b$. Lemma 1: Given any tree and any permutation $p$, only doing edge moves on this tree can sort the permutation.Proof of Lemma 1: If we show that a sequence of edge moves can swap any two (not necessarily adjacent) values, we can clearly sort any permutation. Suppose we want to swap values $a$ and $b$, and the unique simple path in the tree connecting them is $a=v_1,v_2,\dots,v_k=b$, where $v_i$ and $v_{i+1}$ (for all $1 \leq i \lt k$) are connected by an edge denoted by $e_i$. We can see that doing the following edge moves in order: $e_1,e_2,\dots,e_{k-1}$ cyclically shift the values $v_i$ to the right. Hence first cyclically shifting $v_1,\dots,v_k$ once and then cyclically shifting $v_1,\dots,v_{k-1} \,\, k-2$ times, swaps the values $a$ and $b$, while not changing the positions of the other values in $p$.Now we just need to show Lemma 2: As long as the diameter is at least 3 (i.e. there exists a simple path with at least 4 vertices), we can make any edge move regardless of the current $x$, while not affecting other values in $p$.Proof of Lemma 2: Let's denote the vertices of the current edge move we want to make as $a$ and $b$. Then we have 3 cases:Case 1: $x \not\in \{a,b\}$ We can simply make the swap.The other two cases are simply split into whether the edge $(a,b)$ lies on the side of the diameter (i.e. exactly one of $a$ and $b$ has degree 1), or both $a$ and $b$ have degree at least 2. In both cases, we will rely on one or two "pivot" vertices. From here on, WLOG we assume $x=a$.Lemma 2.1: If there exists a vertex $d$ such that $dist(a,d) \geq 3$, then we can swap $a$ and $b$. Proof: Doing the following swaps always works: $(b,d)$, $(a,d)$ and $(d,b)$. Note that the parity handles $x$ avoiding $a$ and $b$, while the distance constraint means Bob can't reach $d$ in time.Case 2: Edge $(a,b)$ lies on the side of the diameter. Note that the case of $a$ being on the side (i.e. having degree 1) is handled by Lemma 2.1, as there must be a path of at least two vertices connected to $b$ (otherwise the diameter would be 2). Hence we only need to show the case where $b$ is on the side. Suppose the diameter (or a part thereof) is $b-a-e-d$.Then we make the following swaps (I'll use $(y,z)$ for swapping $y$ and $z$, $\rightarrow_v$ to show Bob moved $x$ to $v$, and $\overline{p_1p_2\dots}$ for the current relevant part of $p$. Additionally, I'll list all relevant Bob's moves, in case a move isn't listed, a strategy equivalent to Lemma 2.1 applies): Initially, $\rightarrow_a \overline{abde}$. Then $(b,d) \rightarrow_e \overline{adbe}$. Then $(a,d) \rightarrow_d \overline{dabe}$. Then $(b,e) \rightarrow_e \overline{daeb}$. Then $(d,b) \, \overline{baed}$, if $\rightarrow_a$, $(d,e)$ works, otherwise if $\rightarrow_d$, the trivial case of Case 2 applies.Case 3: Both $a$ and $b$ have degree at least 2, suppose the diameter (or a part thereof) is $e-a-b-d$.Then (using the same notation as above), the following moves work: initially $\rightarrow_a \overline{abde}$. Then $(b,d) \rightarrow_b \overline{adbe}$. Then $(a,d) \, \overline{dabe}$. If $\rightarrow_a$, $(d,b)$ works, otherwise if $\rightarrow_d$, the trivial case of Case 2 applies.Finally, note that Lemma 1 can be dropped altogether, but that means you need to additionally handle the cases where a desired swap $(a,b)$ isn't connected by an edge.
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 So that's the proof for diameter at least 3 being sufficient for Alice to win? How about the cases that the diameter is less than 3? lolFor me personally, it was clear that diameter at least 4 would work before writing the brute solution, good to know that proving for 3 is way harder.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 3 →   +29 Oops, I found the first part harder to prove, so I just gave the proof of that, but here's the proof for the rest of the problem, which I actually find more interesting and cute.Let's denote $m$ as the center of the star (the tree).First, if $p$ is already sorted, Alice trivially wins.Next, if $p_m \neq m$ (i.e. $m$ is not in its position yet), we can see that if $x=m$ or $x=p_m$, Bob will win. Bob will achieve this by making sure $m$ will never go to its sorted position. When $x=m$, Alice clearly can't change $m$'s position, and when Bob has to make a move, he moves to $p_m$ (i.e. the value currently in $m$'s spot). This move is always possible since every other vertex is adjacent to $m$.Otherwise either $m$ is already in its position, or $x \not\in \{m,p_m\}$, and Alice's first move is swapping $m$ into its position. In the latter case, let's make Alice's move and solve the resulting state (notice that in this case, $x$ will become $m$, since $x \neq m$ initially). Hence, we can assume $p_m=m$.Next, suppose initially $x=m$. We know that permutation graphs $i \rightarrow p_i$ form cycles, and that the number of cycles either increases or decreases by 1 with every swapping move (meaning their parity changes). Let the initial number of cycles of $p$ be $c$. Since we want to sort the permutation, we want the number of cycles to become $n$, so the parity of the number of swapping moves we must make is the same as that of $n-c$.Notice Bob's winning strategy when $n-c \equiv 0 \pmod 2$: no matter how many moves Alice makes, when she has 2 moves left to make, $x=m$ (every other move, $x$ will become $m$). Hence after Alice makes one of the two required swaps, Bob can simply move to one of the two values that aren't yet sorted, effectively preventing Alice from winning in the next move. Since Bob has such a blocking move whenever Alice is 1 swap away from sorting $p$, Alice can never win, so Bob wins.Otherwise, $n-c \equiv 1 \pmod 2$, in which case Alice has a winning strategy: whenever $x=m$, no move is blocked, so she can make an optimal move (one that increases $c$). Whenever $x \neq m$, the number of moves left is even, i.e. at least 2, so there are at least 3 values not in their positions yet, and regardless of where Bob is, there is an optimal move. Since Alice can always make an optimal move, she wins.So far we've assumed that initially $x=m$. When this isn't true, it will be true in the next move, but it does introduce one final corner case, which is only one move being required, and $x$ not covering either of the two values not in their positions, in which case Alice wins, even though the above parity cases would suggest Bob's victory.
 » 6 weeks ago, # |   +44 Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
•  » » 6 weeks ago, # ^ |   -69 Don't talk bullshit. You don't even removed Cheaters from last Education Round.
 » 6 weeks ago, # |   0 Fast rating, thanks.I spent much longer on problem B than I should have, I came up with the idea pretty much instantly but messed up implementation many times. Does anyone know why my python solutions failed? I switched to c++ in the tail end of the contest and translated the same idea to solve B, since all my python solutions TLE'd. This was my final python attempt, which I tried optimizing using bitwise operators:https://codeforces.com/contest/1659/submission/153923577
•  » » 6 weeks ago, # ^ |   0 Instead of optimizing, you increased the complexity. You have a loop for i , and you are shifting i bits. shifting i bits take O(i) time. So your time complexity is O(n^2).Solution 1: store it in array and access each element in O(1) time. Solution 2: Instead of shifting i bits every time, notice that amount of bit shift changes by only 1. So you can use a temporary variable and divide it by 2 everytime.
 » 6 weeks ago, # | ← Rev. 2 →   -15 Those who do Leetcode regularly, can you tell me is there also problems like todays B comes? Is todays problem B can be asked in big tech company Interviews?
•  » » 6 weeks ago, # ^ |   0 lol no i guess
 » 6 weeks ago, # | ← Rev. 3 →   +13 My solution for Problem D.We iterate from left the given numbers. If we hit some column with sum greater $0$, then we found a $1$ (marked with a rectangle in the picture. This is kind of an identifying $1$). We remove all $1$-s corresponding to the same color and accordingly adjust our array. Then we continue seeking for entries greater than $0$. To find the corresponding column to a $1$ we just need to go as many steps forward, as we already found $1$s. See the bars at the bottom. The removing of the columns of $1$-s is simple. The removing of the diagonal of $1$-s can be either done with a lazy segment tree or by managing some variables about how much should be subtracted at the current position. See my solution 153943020 in method "solve".
 » 6 weeks ago, # |   +12 If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints. If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
 » 6 weeks ago, # |   -8 Problem D sucks
 » 6 weeks ago, # | ← Rev. 4 →   +40 A simple way to solve $D$:Initialize all $ans[i]$ with ones. Now iterate on $i$ from $0$ to $N-1$. If $C[i]=0$, then $ans[i]=0$.For every $C[i]\neq 0$, if $ans[i]=1$, we want to find the $0$ that will replace it at some move (if any), this should be the $C[i]^{th}$ element, so make $ans[C[i]]=0$.Otherwise if $ans[i]=0$, then this should be replaced by a $1$ before it at some move, and then replaced by a $0$ after it (if any) at some move, so we want to find the $0$ that will replace it (if any), this should be the $(i+C[i])^{th}$ element, so make $ans[i+C[i]]=0$.Submission
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Exactly how I thought about it, but my implementation(153950297) is a little weirder than yours.
•  » » 6 weeks ago, # ^ |   0 Your solution is very simple and beautiful
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +4 At the fourth paragraph in your idea (when $ans[i] = 0$) how do you arrive with the conclusion "... this should be the $(i + C[i])^{th}$ element" ?(i.e. where does the $i$ and $C[i]$ part comes from?)
•  » » » 6 weeks ago, # ^ |   +4 We have already maintained a $0$ at $i$ for $i-1$ moves. Now at the $i^{th}$ move, before making the move we have a $1$ at $i-1$, and after the move that $1$ will be at $i$.$C[i]$ tells us that a $1$ will be at $i$ for $C[i]$ moves. This means that that for the next $C[i]-1$ moves a $1$ is maintained at $i$. This means that at the $(i+C[i])^{th}$ move, the $i^{th}$ element will turn from $1$ to $0$, and since the only new element introduced at that move is the $(i+C[i])^{th}$ element, its value is for sure $0$.
•  » » » » 6 weeks ago, # ^ |   0 Hmm. Could you give an example for this argument ? I still don't quite get it :')
•  » » » » » 6 weeks ago, # ^ |   +6 For the binary string $[1, 0, 1, 0]$The sequences we get after each move: $[1, 0, 1, 0]$ $[0, 1, 1, 0]$ $[0, 1, 1, 0]$ $[0, 0, 1, 1]$ $C = [1, 2, 4, 1]$Consider the second position. It is first $0$, then changes to $1$ after the second move, and remains $1$ until the fourth move when it changes to $0$ again. Assuming $0$-based indexing, $C[1]$ tells us that the second element will be $1$ after the second and third move, then will be replaced by $0$ after the fourth move (obviously by the fourth element at $1+2=i+C[i]$).
•  » » » » » » 6 weeks ago, # ^ |   0 Oh I see. I get it now. Thanks!
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 In third paragraph, "c[i]th element should be zero". I don't understand how is this sufficient. Actual condition should be: "C[i]th element should be zero and number of zeros before C[i]th element should be i". This additional condition is to make sure that C[i]th element actually replaces the ith element
 » 6 weeks ago, # |   +1 Comparing Score distribution and problem difficulty was damn thug distinct .... A B C
 » 6 weeks ago, # |   -8 long queue cheaters... unbalanced problem difficulty
 » 6 weeks ago, # |   +3 Hi Mike please remove more cheaters I am at 1896
 » 6 weeks ago, # |   +4 Thought solution not submitted and submitted second time and got penality as website stuck for few minutes and suddenly damn two times solution submitted (-50 points) :(
 » 6 weeks ago, # |   +6 Time to practice A & B problems again. IS B a good problem? B ended my contest :v
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 You just need to consider k%2==0 or k%2==1 if==0 just operate “0” one time if==1 operate “1” one time, that would make higher to lower became “1”, and that is the biggest answer.
 » 6 weeks ago, # |   +8 24 hours for an editorial is quite poor, preparation really should be better...
•  » » 6 weeks ago, # ^ |   0 yeah, please don't make late editorials a habit :(
 » 6 weeks ago, # | ← Rev. 2 →   -11 How D?wtf????i think D is strictly harder than E
•  » » 6 weeks ago, # ^ |   0 Could you please tell me how to solve E
•  » » » 6 weeks ago, # ^ |   0 Oh,I know how to solve it
•  » » » 6 weeks ago, # ^ |   +8 the ans will be 0/1/2,for 1 and 2 cant both exist (obviously).if you only go through edges with the edges that all have 1 is some bit(for example,go through 110 , 010 and 011 ,then the 1 in the second bit will persist,which means 0 wont exist), then the ans is 0.this case can be solved using ADT.you only have to check whether the u and v in each question is connected.what if the ans is 1?first,you should ensure that the ans mustnt be 0.second, mark the vertex that has an edge with an even weight from it with a tag "A".consider a question u and v,you dont want to get 1,and as long as you pass an edge with an even weight,you will never get 1 after that(you are safe now). so the problem is that before you reach any vertex with tag "A"(mentioned above),you dont want to get 1,and you will find it really similar to the problem we have already solved in para 2:make one of the bits always 1,except the lowest bit.also ADT and you will solve it easily.for every bit,find if in the component where u is exists a vertex with tag "A".for every question,if in some bit this is true then the ans can be 1.for the rest questions without an ans till now,the ans is 2.
•  » » » » 6 weeks ago, # ^ |   0 thx
•  » » » » 6 weeks ago, # ^ |   0 What is ADT?
•  » » » » » 5 weeks ago, # ^ |   +5 union-find sets
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +1 My sol of problem D:First, observe that the values of array only get permuted but not changed. So sum of c[i]s should be n*(number of 1s). Thus number of 1s can be calculated.Now you immediately know the sorted array of timestep n: 00..0011..11. And for former timesteps, The nth position is left unpermuted. Thus if c[n]>1, a[n]=1, otherwise a[n]=0.After that you remove the influence of timestep n from c[i]s, and repeat for timestep n-1,n-2,...,0.
•  » » » 6 weeks ago, # ^ |   0 excellent.the clearest solution i've ever seen.thx vry much.
•  » » » 6 weeks ago, # ^ |   0 Can you please explain how the influence of n(previous) timestep can be removed?
 » 6 weeks ago, # |   +14 Now I have a strange problem: after this contest, the rating change of the last contest Educational Codeforces Round 126 changed. And my rating before this contest is 2101. According to the rules, this contest should be unrated for me. How can I solve this problem?
 » 6 weeks ago, # |   0 When tutorial is available? Really confused about problem B. I feel I got the solution, but I couldn't pass test case2. Really want to know what's wrong in my submission.
 » 6 weeks ago, # |   0 Why does it happen sometimes that initially rating changes are applied, then they are rolled back and then again the same rating changes are applied? What happens when the rating changes are rolled back?
•  » » 6 weeks ago, # ^ |   0 Calculating rating changes depends obviously on the standings table of all partitipants. This means, if this table changes (i.e. because cheaters where removed), the rating changes also change.In a perfect world such recalculation would be one quick step, but it seems to be not trivial, so we see this "rollback" and "recalculation".
 » 6 weeks ago, # |   0 Will the copiers be banned?
 » 6 weeks ago, # | ← Rev. 4 →   0 ..
 » 6 weeks ago, # |   +1 I feel extremely happy that my idea works for problem B. 153975614
 » 5 weeks ago, # |   0 My solutions were skipped because of a claim that my solution is similar to someone’s else solution,but I didn’t cheat,and if there’s any similarity with someone’s solution it’s not my fault,please reconsider my decision
 » 5 weeks ago, # |   0 Problems are very difficult
»
5 weeks ago, # |
-11

B_ Social Distance

# include <bits/stdc++.h>

using namespace std;

//////////////////////// ////AAYUSH DHANKECHA//// ////////////////////////

# define lli long long int

int max(int n, int m) { if (n >= m) { return n; } else { return m; } }

void solve() { lli n, m; cin >> n >> m;

lli a[n];
lli i, sum = n;
if (n != 1)
{

for (i = 0; i < n; i++)
{
cin >> a[i];
}
for (i = 1; i < n; i++)
{
sum += max(a[i], a[i - 1]);
}

sum += max(a[0], a[n - 1]);

if (sum <= m)
{
cout << "YES\n";
}
else
{
cout << "NO\n";
}
}
else
{
if (m != 0)
{
cout << "YES\n";
}
else
{
cout << "NO\n";
}
}

}

int main() { fast; lli t; cin >> t;

while (t--)
{
solve();
}

return 0;

}

 » 2 weeks ago, # |   0 "i_am_completely_useless for being completely useless." -- Sakura :))xD
•  » » 13 days ago, # ^ |   0 Nice Quote