Hello Codeforces!

Asymmetry and I are glad to invite you to Codeforces Round #743 (Div. 1) and Codeforces Round #743 (Div. 2), which will be held on Sep/18/2021 17:35 (Moscow time).

Each division will have 6 problems and 2 hours to solve them. All problems were written and prepared by Asymmetry and me. The round will be rated for both divisions.

We would like to thank:

We've put great efforts into preparing this round and we hope that you will enjoy it.

Good luck!

UPD: We would also like to thank Sexpert for testing the round and KAN for translating the statements into Russian.

UPD2: Here are the scoring distributions:

Div. 1: $500$ — $1250$ — $1750$ — $2500$ — $2500$ — $3250$

Div. 2: $500$ — $1000$ — $1500$ — $2250$ — $2750$ — $3500$

UPD3: We are sorry that the round became unrated due to the long queue. We hope that you enjoyed the problems anyway.

## Winners

Congratulations to the winners!

Div1.

Div2.

UPD4: Editorial is out!

• +878

 » 12 months ago, # |   +270 Since Monogon had ascended into the coordinator realm, I became the new VIP tester.btw, as a VIP tester, I tested
•  » » 12 months ago, # ^ |   -15 That's okay, but were you tested too?
 » 12 months ago, # |   +179 As a tester, I wish you sunny weather ^^
•  » » 12 months ago, # ^ |   -64 As a resident of a warm country I downvoted.
•  » » » 12 months ago, # ^ |   +3 as a lover of your pp,I still downvoted you
•  » » 12 months ago, # ^ |   +4 as a -ummm ughh uhhh yes
 » 12 months ago, # |   +253 As coordinator I want to thank the VIP authors Asymmetry and Markadiusz
•  » » 12 months ago, # ^ |   -208 .
•  » » » 12 months ago, # ^ |   -22 But still takes contibution ;)
•  » » » 12 months ago, # ^ |   0 Ah, you misplaced dogs
•  » » 12 months ago, # ^ |   +8 As participant I want to thank coordinator Monogon and authors Asymmetry and Markadiusz
 » 12 months ago, # |   0
 » 12 months ago, # |   -38 When will next div 3 round happen??
 » 12 months ago, # |   +16 Looking forward to participate
 » 12 months ago, # | ← Rev. 3 →   -122 Challenge:hit 200 downvotes under this comment (bye bye contribution)
 » 12 months ago, # |   +145 As a coauthor, I wish everyone best of luck and a positive skill delta after the contest.
 » 12 months ago, # |   +46 As a tester, I wish everyone happy rating :)
•  » » 12 months ago, # ^ | ← Rev. 2 →   -8 Wish me happy rating for the next two-three contests so that I can have your current color
•  » » 12 months ago, # ^ |   0 Because thats what heroes do:))
 » 12 months ago, # |   -21 Why the huge difference between C and D problems !!!! ** it was the first time i see such a difference ** Is it okay >>
 » 12 months ago, # |   0 Don't wanna miss the contest but suffering from anxiety and depression for the past few days.Hopefully I will overcome anxiety and depression soon and start playing in contests
•  » » 12 months ago, # ^ |   +15 Mental health is much more important than competitive programming, so take it easy, hoping for some well wishes from a fellow stranger.
•  » » » 12 months ago, # ^ |   0 Yeah,I am going to meet my psychologist today for that reason.Being mentally strong is important in cp too.Because you can have all the skills in the world but if your mind is unstable during 2 hour contest I Don't think you can deliver your best.Anyway,I am going to consult my psychologist soon and come back strongly.And thanks for your kind words.Cf has really been like a family to me
•  » » » » 12 months ago, # ^ |   +2 I hope you become well in the coming days and I wish the best of luck for you in the contest
•  » » » » » 12 months ago, # ^ | ← Rev. 3 →   0 Thanks for your support.Unfortunately I am not stable enough to give today's contest but hopefully I will be giving every contest in cf from 23rd September.I wish you all the best in today's contest
•  » » » » » » 12 months ago, # ^ |   0 Take good rest bro ,and come back strong
•  » » » » » » » 12 months ago, # ^ |   0 yeah sure buddy, pray for me.Good luck for today's contest.Wish you high rating!!!
•  » » » » » » 12 months ago, # ^ |   0 Thanks Noelle-s-Stupidsta , I'm still working on a strategy to reach a better level but I think it will take some effort and time to reach a higher rank
•  » » » » » » » 12 months ago, # ^ | ← Rev. 4 →   0 solve 1/2 1200 rated problems solve 1/2 1300 rated problems solve 1/2 1400 rated problems Do these three things everyday solve 2 1500 rated problems Do this in every week Don't miss any contest Do all these in the next 2 months and be confident and always believe you can be as good as anyone.Hopefully your rating will be between 1200-1300 after that
•  » » » » » » » » 12 months ago, # ^ | ← Rev. 2 →   +11 From my experience, I think you just need learn the basic technique to get rating >1600. Do too much easy problem doesn't make your skill better.
•  » » » » » » » » » 12 months ago, # ^ |   -6 I agree but my learning was always extremely problem-solving oriented.Even I never studied binary search.I felt the importance to learn it only when I had to do some binary searching in a problem. Well, every human-being is different.So, strategies may vary
•  » » » » » » » » » 12 months ago, # ^ |   0 I'm trying to do this recently and I'm learning new topics as well but it's not always easy to use new topics in solving problems it takes some time
•  » » » » » » » » 12 months ago, # ^ |   0 Thanks for the advice I'm going to try it and maybe I will try solving problems on other websites as well
•  » » » » » » » » » 12 months ago, # ^ |   0 yeah, atcoder beginner contests are very helpful, you may check it out
•  » » » » » » » » » 12 months ago, # ^ |   0 i will thanks
 » 12 months ago, # |   0 kickstart round is also scheduled from 17:00 UTC on the same date, can u guyz plz prepone the round?
•  » » 12 months ago, # ^ |   +1 That way it will clash with Atcoder ABC
•  » » » 12 months ago, # ^ |   -34 Whats your Atcoder Handle ??
 » 12 months ago, # |   -89 As someone who wants to hit -69 contribution mark, I request y'all to downwote for high ratings. thank you!
 » 12 months ago, # |   +122 As an old, almost retired contestant who grew up in the same school as the authors, I'm thrilled to see what my younger comrades prepared :)
 » 12 months ago, # |   +8 Interesting division 2 scoring distribution. I expect (and hope for) a sizeable jump between C and D.
 » 12 months ago, # |   +16 Early scoring distributions! :D
 » 12 months ago, # |   0 I am a newbie and started giving contests on this platform from this month itself. Excited for this another upcoming contest!! All the best everyone!
•  » » 12 months ago, # ^ |   +2 I am a specialist and started giving contests on this platform from last year itself. Excited for this another upcoming contest!! All the best everyone!
•  » » » 12 months ago, # ^ |   +1 I am a pupil and started giving contests on this platform from this year itself. Excited for this another upcoming contest!! All the best everyone!
•  » » » » 12 months ago, # ^ |   +2 I am a future expert and started giving contests on this platform 20 yrs ago. I was excited for this then upcoming contest!! All the best everyone!
•  » » » » » 12 months ago, # ^ |   0 Lmao
 » 12 months ago, # |   0 Target to solve A, B & C asap to get a good rank, D seems to be much harder based on rating distribution.
 » 12 months ago, # |   -19 Noice looking contest good luck :> HEHEHE HA
 » 12 months ago, # |   -8 I hope a good result for everyone !
 » 12 months ago, # |   -9 Hope all get positive points :)
 » 12 months ago, # |   -39 many tks for your efforttt hope to up rate uhuhu
 » 12 months ago, # |   +14
 » 12 months ago, # |   -12 Very good stuff worked to prepare this contest I guess, thanks
•  » » 12 months ago, # ^ |   -27 your welcome
 » 12 months ago, # |   -70 As your father,I want some contribution
 » 12 months ago, # |   +48 I just want to say that 743 is a prime number.
•  » » 12 months ago, # ^ | ← Rev. 4 →   +8 why are you a foolishgoat ? Btw I just want to say that number of characters in foolishgoat is also prime (11)
•  » » » 12 months ago, # ^ |   +6 Well, I'm foolishgoat because I'm just a goat that comes to Codeforces so that I can train and become a smart one.
 » 12 months ago, # |   0 Suiiiiiiiiiiiiiiiii!
 » 12 months ago, # |   0 all the best to all
 » 12 months ago, # |   0 Wish Me Cyan !!!
 » 12 months ago, # |   +4 "An Unexpected error" is showing up whenever i am submitting my solution!!! Anyone else facing the same issue????
•  » » 12 months ago, # ^ |   0 Me also
•  » » » 12 months ago, # ^ |   0 Check the selected problem either it's selected or not every first time submission.
 » 12 months ago, # |   +17 Queue :(
 » 12 months ago, # |   +8 too long queue :(
 » 12 months ago, # |   +9 A contest after ages and what we see is a Queue
 » 12 months ago, # |   +84 unrated please
 » 12 months ago, # |   +12 QueueForces T_T.
 » 12 months ago, # |   +10 such a long queue , it has to be unrated .
 » 12 months ago, # |   +11 15 minutes since A is in queue.....
 » 12 months ago, # |   0 Thinking for 10min shall I get TLE in problem B or not :)
 » 12 months ago, # |   +8 too long queue:(
 » 12 months ago, # |   +5 while true: dequeue()
 » 12 months ago, # |   +8 please extend the contest by 15 mins at least due to the long queue.
•  » » 12 months ago, # ^ |   -48 don't make it unrated because the problems are really good.
•  » » » 12 months ago, # ^ |   +23 just cause you solved , this is unfare to wait for 20 min to get wa verdict
•  » » » » 12 months ago, # ^ |   0 i never said it is fair to not make it unrated but an alternative is to extend it since a contest is much awaited by everyone.
•  » » » » » 12 months ago, # ^ |   +5 imagine waiting for B and then getting wa after 30 min for some silly stuff , meanwhile some guy solved after 30 min and submitted in first go , I dont think extending contest will justify now
•  » » » 12 months ago, # ^ |   0 So good that you submitted A twice
•  » » » » 12 months ago, # ^ |   0 it was a mistake, i accidentally submitted my B solution in A.
•  » » » » » 12 months ago, # ^ |   0 yeah, I thought so ...
•  » » 12 months ago, # ^ |   0 Its not possible google kickstart is on the way.
•  » » » 12 months ago, # ^ |   0 for me at least any CF contest >>>> any other contest except(ICPC).
•  » » » » 12 months ago, # ^ |   0 Lol, I guess you are only thinking about you. Possibly everyone here will participate in kickstart.
 » 12 months ago, # |   +26 This should definitely be unrated!
 » 12 months ago, # |   +40 The contest must be unrated . Such a long queue
 » 12 months ago, # |   +29 I think there should be a clear guideline in Codeforces when the round should be unrated. Because queue in first few minutes can severely affect the rating in case there is a difficulty gap in the problems.
•  » » 12 months ago, # ^ |   +9 20min. queue. Should be unrated
 » 12 months ago, # |   +6 Why so long queue??
 » 12 months ago, # |   +1 Too long queue, please, make this round unrated
 » 12 months ago, # |   0 The queue is too long today? i submitted a solution 5 mins back and still it's not judged yet.
•  » » 12 months ago, # ^ |   0 20 minutes here bro!! I feel the same
•  » » » 12 months ago, # ^ |   +2 30 min here
•  » » » » 12 months ago, # ^ |   0 lol
 » 12 months ago, # |   +31 Queueforces ;-;
 » 12 months ago, # |   +8 MikeMirzayanov what type of queue is used for submissions, my submission at 7 min is not yet judged but some user's 12 min sol are judged. Please help!!!!
•  » » 12 months ago, # ^ |   +17 That might be a stack, not a queue then!
•  » » » 12 months ago, # ^ |   0 might be a stack of queues lol
 » 12 months ago, # | ← Rev. 2 →   -7 If unrated, my possibility of becoming CM will be ruined for this time.
•  » » 12 months ago, # ^ |   +4 If unrated, my possibility of becoming newbie will be ruined for this time.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 Sed lyf, but the chances of being unrated is 99.99%.
•  » » » » 12 months ago, # ^ |   +1 Thanks codeforces. I will be back again.
•  » » » » » 12 months ago, # ^ |   +1 Done :( Hope you break into CM next edu!
•  » » » » 12 months ago, # ^ |   +4 Done :( Hope you break into CM next edu!
•  » » 12 months ago, # ^ |   0 Same :sob:
•  » » » 12 months ago, # ^ |   0 I feel you.
•  » » 12 months ago, # ^ |   0 If unrated, my possibility of becoming pupil will be ruined for this time.
•  » » 12 months ago, # ^ |   0 Same here . 2nd person to Solve C . Also A and B were pretty easy but here I'm crying
•  » » » 12 months ago, # ^ |   0 probably because of queue issues and many ppl left, just saying
 » 12 months ago, # |   +41 Unrated please!!
 » 12 months ago, # |   +5 Why queue is so long?
 » 12 months ago, # |   +6 Is it unrated?
 » 12 months ago, # |   +12 20 mins just to get wrong answer so sad
 » 12 months ago, # |   +9 The contest should be unrated cause of long queue!
 » 12 months ago, # | ← Rev. 3 →   +16
 » 12 months ago, # |   0 @mike @contest admins please give the info whether it will be rated or notso that we can do some other things.
 » 12 months ago, # |   +6 I am waiting for more than 30 minutes, still my solution is not judged .
 » 12 months ago, # |   0 Next contest shall be to program decent queue
 » 12 months ago, # |   +1 Disgusting queues
 » 12 months ago, # |   0 To be honest round should be unrated as 30 minutes are too much just to get a wa.Nothing to take from Authors you did a phenomenal jobbut it should be unrated.30 minutes are too much guys/
 » 12 months ago, # |   +1 Such a bad queue :(
 » 12 months ago, # | ← Rev. 2 →   +19 Me: submitsCodeforces: Click this
•  » » 12 months ago, # ^ |   0 It is also gonna cost penalty and pain if it comes out to be wrong.
 » 12 months ago, # |   +8 Imagine submitting before 30 min and getting WA. :))
 » 12 months ago, # |   +17 It'll be unrated, there's no point participating. There's no better way to compensate for never getting results on pretests.
 » 12 months ago, # |   +4 queueForces
 » 12 months ago, # |   0 Finally it's unrated now !!
 » 12 months ago, # |   0 it's unrated no doubt just have fun solving problems
 » 12 months ago, # |   0 Good bye , tata, Allah Hafiz
 » 12 months ago, # |   +2 Nice round. It's a pity that this round is unrated(
 » 12 months ago, # |   0 F
 » 12 months ago, # |   +1 Great questions, sad the round will be unrated.
 » 12 months ago, # |   +18 Second person to solve C only for round to get unrated xD
 » 12 months ago, # |   0 Best round but very sad that this became unrated
 » 12 months ago, # |   0 I thought the problems were really nice, so I'm disappointed that the round went unrated.
 » 12 months ago, # |   +18 will it be unrated for div 1 also?still 0 announcement
•  » » 12 months ago, # ^ |   0 yeah! it was announced that it will be unratted for div1 too
 » 12 months ago, # |   0 Bye Bye, See you at Google kickstart
 » 12 months ago, # |   +11 When I solved A and B under 15 minutes, the round gets unrated. Of course, why not :(
 » 12 months ago, # |   0 Read first three problem . The questions were interesting . Sad that the round in unrated :(
•  » » 12 months ago, # ^ |   0 same, pal. same
 » 12 months ago, # |   -8 Thousands of submissions are in queue and only one of them is running. why?
 » 12 months ago, # |   0 thanks for hosting I enjoyed the problems I attempted. sad the queue times were too long.
 » 12 months ago, # |   +6 B and C were so beautiful, very sad it's unrated.
 » 12 months ago, # |   +1 this is not expected from such big organization please fix this for once I did so good in the contest (a and b) this fast (i'm newbie) :(((
 » 12 months ago, # |   +131 Results of other OJ：Result of Codeforces:lol
•  » » 12 months ago, # ^ |   +3 3ms TLE kinda sus tho..lol
•  » » 12 months ago, # ^ |   0 where i can see it? im about first image
 » 12 months ago, # |   0 It's a pity that the round was unrated. But, the tasks were interesting. Thanks!
 » 12 months ago, # |   0 After so much time as a beginner i am finally able to solve a few and it is unrated now. Tbh i am pissed off :(
 » 12 months ago, # |   0 I have a theory that most problem-setters make tough problems just to avoid queue issues. LOL! Nice contest, btw.
 » 12 months ago, # |   0 problems were really good and don't deserve unrated(;_;)
 » 12 months ago, # |   +3 Feels sad man , when first contest you give goes unrated :(
•  » » 12 months ago, # ^ |   0 I_Hate_Swaps you shouldn't feel sad problem B.Swaps
 » 12 months ago, # |   +6 nowdays Long queue is common problem in cf. please do something MikeMirzayanov :(
•  » » 12 months ago, # ^ |   0 Custom invocation is also unusable during contest.
 » 12 months ago, # |   +27 Imagine waiting for a Codeforces round for 1 week... and this.
 » 12 months ago, # |   +38 Unlucky comeback after ~2 years of inactive. F.
•  » » 12 months ago, # ^ |   0 yup for me ~2 months F.
 » 12 months ago, # |   0 Please fix this!
 » 12 months ago, # |   0 unraited...
 » 12 months ago, # |   +90 How to get rid of queues on CF? The answer is...Make div. 1 rounds only
 » 12 months ago, # |   0 Unrated？
 » 12 months ago, # |   0 comeback failed, folks. :(
 » 12 months ago, # | ← Rev. 2 →   0 Could have been one of my best, really sad. But a lovely problem set. Cheers to the setters!
 » 12 months ago, # |   +24 It was the first contest I liked in probably the last 12 months and seeing it getting unrated this way, I feel sad for the authors very much. Markadiusz and Asymmetry I liked the problems a lot and hope to see you guys with another contest soon!
•  » » 12 months ago, # ^ |   0 Thank you for your support :)
 » 12 months ago, # |   +52 Problem 1C seems to be the same with Problem C in 2020-2021 ACM-ICPC, Asia Kunming Regional Contest.
 » 12 months ago, # |   +3 cucked my comeback
 » 12 months ago, # | ← Rev. 2 →   0 Problems was really nice. i think i will become specialist again after this contest :) but Unfortunately unrated :(
 » 12 months ago, # |   +41 The problems are nice! Because it is unrated now, I can sleep early today LOL :)
•  » » 12 months ago, # ^ |   +20 do kickstart that is in ~80 mins from now
•  » » » 12 months ago, # ^ |   +10 That's too late :(
 » 12 months ago, # |   +5 This is still a good problem collection and worth trying out. I will still try to do my best even if it's unrated.
 » 12 months ago, # |   -8 Can there be a announcement that they will rate the round? If not please tell me so that I can stop worrying. :(
•  » » 12 months ago, # ^ |   0 Don't Worry Codeforces always keep their words... They said its unrated means its unrated...
 » 12 months ago, # | ← Rev. 2 →   +52 1-gon's first round got unrated due to the long queue. Now Asymmetry and Markadiusz set their first round coordinated by 1-gon, and the round got unrated due to the long queue. RIP
•  » » 12 months ago, # ^ |   +78 :(
•  » » » 12 months ago, # ^ |   0 And Both contests had nice problems :(
 » 12 months ago, # |   0 logic behind b?
•  » » 12 months ago, # ^ |   0 Since a[0]!=b[0] we need to make those two elements so that a[0]
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +3 We can avoid binary search since we know the numbers in a[] are 1, 3, ..., 2n-1. Create an array c[] such that c[k] gives the index j for number k i.e. if a[i]=k, we get j by c[k]. To fill c[], we can iterate over array b and store index j for all numbers smaller than the current no in b.
•  » » » » 12 months ago, # ^ |   0 Doesn't this require sorting, which yields linearithmic time complexity either way?
•  » » » » » 12 months ago, # ^ |   0 No, the numbers are relatively small compared to the length of the input (<=n), so a simple loop, described above, is enough.
•  » » » » » » 12 months ago, # ^ |   +8 Oh I completely misunderstood that comment. I got it now, thanks!
 » 12 months ago, # |   -49 give editorial ASAP. I have to do a lot of homework. Spoilerdidn't got any AC. Spoilerproblem A how to change 2020 with 6 operation. help me please!!
•  » » 12 months ago, # ^ |   +11 well I think: 2020 -> 0022 -> 0020 -> 0002 -> 0000
•  » » » 12 months ago, # ^ | ← Rev. 3 →   0 swap two digits (you can choose which digits to swap, and they don't have to be adjacent). how the following operation is feasible with one swap we must have to do two consecutive swap. 0020 -> 2000 -> 0002 please clarify
•  » » » » 12 months ago, # ^ | ← Rev. 3 →   0 swap 0 and 2?i don't understand what you wonder...p/s: they don't have to be adjacent, but adjacent is accepted
•  » » » » » 12 months ago, # ^ |   0 logic was sum up all non zero numbers and also increase by 1 if the position of nonzero element is not last...
•  » » » » 12 months ago, # ^ |   0 i also have the same doubt becaz this---"you can choose which digits to swap, and they don't have to be adjacent" has been clearly mentioned in the problem
•  » » 12 months ago, # ^ |   0 2020 -> 2002 (swap 3rd and 4th element) -> 2001 -> 2000 -> 0002 (swap 1st and 4th element) -> 0001 -> 0000
 » 12 months ago, # |   +3 The problems were good. (especially Problem B...able to do in O(N)) PS: All the best for Kickstart buddies. :)
 » 12 months ago, # |   0 First time my code was accepted in contest but fine i enjoyed the problem....
 » 12 months ago, # |   +5 Any thoughts of problem E? It seems to be a dp problem, but I didn't figure out the recursion formula.
•  » » 12 months ago, # ^ |   0 it looks more like a divide and conquer problem for me, i tried dp and it didn't work.
•  » » 12 months ago, # ^ | ← Rev. 3 →   0 NVM. Thought it was D.
 » 12 months ago, # |   -20 I dont understand why people in comment section are filled with sarcasm and down votes
 » 12 months ago, # |   0 For problem C, we first figure out if it is possible to finish the whole book by SCC (strongly connected component). If size of some (possibly 1) SCC are greater than 1, then it is impossible to complete the book. After that, we use 2 min heap to store pages with indegree 0. First heap stores current traverse. Second heap stores next traverse.Link for my submission
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Using SCC is a bit overkill and definitely a waste of time for this problem.The goal (when checking if understanding the book is possible) is to check if there is a cycle. We can do that with a DFS (or multiple, in case of a DAG, which we are dealing with here) which, instead of marking a vertex visited, can set two different kinds of flags.The DFS works as follows: Set flag "in progress" for current vertex Consider all neighbours, for each 2.1. If its flag is "in progress", then a cycle is detected 2.2. If its flag is "unvisited", then run the DFS on the neighbour. Set flag "visited" for current vertex We can count the result with a DFS too, using dynamic programming on a DAG. Every vertex with no outgoing edges receives value 1, because that chapter will be understood during the first reading of the book. Every other chapter will be understood after all its prerequisite chapters are understood, so the result for the chapter is the maximum of the results for the prerequisite chapters... but slightly modified to account for the order of the chapters in the book.I'm not the best at explaining so maybe my code will help.
•  » » » 12 months ago, # ^ |   0 topological sort :|
•  » » » » 12 months ago, # ^ |   0 Yes, and?
•  » » » » » 12 months ago, # ^ |   0 Idk :D
•  » » » 12 months ago, # ^ | ← Rev. 5 →   0 I actually used a different approach. I made two heaps : the first one is the "main" heap, the second one is the "pending" heapThe "main" heap's purpose is to store the progress chapters you can learn right now given that you're already learn all required chapters. Meanwhile, the "pending" heap's purpose is to store the chapters which you have learned all the required chapters but the chapter number is less than the chapter we currently onSo let's process the chapters one by one starting by those which have no requirements. (E.g. the ones which have 0 in-degree)Each time we're processing of the current chapter (let's say we name it U) we do this : check all other chapters V which has U as requirements subtract V's degree by 1 if V's degree become 0 then : A. If V > U, then this chapter comes after U, then put it on the "main" heap OR B. If V < U, then this chapter lies before U, since we can't read it backwards, put V to "pending" heap on the end of each processing, if our "main" heap becomes empty, put all chapters in "pending" heap to "main" heap and increase the number of read by 1 (because this means we will start re-reading the book)To check if it's impossible, just check if after we're done with all the processing, there exists at least a chapter we haven't processed beforeMy implementation
•  » » » » 12 months ago, # ^ |   0 This work is O(nlog(n)) though due to the heap! But it's still a fine approach.
•  » » 12 months ago, # ^ | ← Rev. 2 →   +1
 » 12 months ago, # |   +8 How to solve div2 D?
•  » » 12 months ago, # ^ | ← Rev. 3 →   +36 First of all, xor of all the elements of the array should be $0$ (xor of all the elements of the array isn't changed after any operation).From here, I am assuming that xor of all the elements of the array is $0$.If n is odd, it's always possible to change all the elements to $0$.Note that if $a_{i}=0$ and $a_{i+1}=a_{i+2}$, $a_{i}\oplus a_{i+1}\oplus a_{i+2}=0$. This is the main idea of my approach.Now select indices $n-2,n-4,...,1$. It's easy to observe that now the first element of the array will be $0$ and $a_{i}=a_{i+1}$ for all even $i$ less than $n$. First element will always be $0$ because it is the xor of all the elements of the array Now select $1,3,...n-2$. After these operations, all the elements of the array will be $0$ and total number of operations performed is $n-1$. If $n$ is even, you can split it into two subarrays of odd length. So if you can find an $i$ such that $i$ is odd and xor of first $i$ elements is $0$, you can change all the elements to $0$, otherwise you cannot.
•  » » » 12 months ago, # ^ |   0 Oh holy crap this is brilliant. And here I got stuck with some greedy ifological strategy which... I'm reasonably confident would work but I didn't manage to implement it.
•  » » » » 12 months ago, # ^ |   0 Yeah, such approach can work too but I had to consider many different cases.Basically: we iterate from left to right, either A keeping all elements behind 0 or B leaving all elements behind 1 (for simplicity ensuring that the current element is 1 too after previous operations).A: if applying the operation to the current $i$ will result in zero xor, we do it. Else if the $i$th element is 1, we ensure that $i+1$ is too; we know that $i-1$, if it exists, is zero, and we can zero $i-1..i+1$, and if it doesn't, we switch to B.B: if applying the operation to the current $i$ will result in zero xor AND there's an even number of 1s behind us, we zero $i..i+2$ and 1s behind us two at a time. Otherwise we ensure that the next element is 1 (working through a few cases it can be shown that if it's 0, the current xor must be 1). codefor (int i = 0, carry = false; i < n - 2; ++i) { if (!carry) { if (!(a[i] ^ a[i + 1] ^ a[i + 2])) { flip(i); } else if (a[i]) { if (!a[i + 1]) { flip(i); } i? flip(i - 1): void(carry = true); } } else if (!(a[i] ^ a[i + 1] ^ a[i + 2]) & ~i) { for (int j = i; j > -1; j -= 2) { flip(j); } carry = false; } else if (!a[i + 1]) { flip(i); } } bool success = !a[n - 1] && !a[n - 2]; 
•  » » 12 months ago, # ^ |   +10 First you must have an even number of 1s in the array, otherwise it's impossible to change all elements to 0s.Then group all the 1s in pairs: (1st, 2nd), (3rd, 4th), ... we will solve the problem by changing each pair of 1s to 0s repeatedly: if there are an even number of 0s between two 1s, we firstly change those 0s to 1s by performing operations on i such that $a_i=1, a_{i+1}=0, a_{i+2}=0$ repeatedly. Then perform operations on i such that $a_i=0, a_{i+1}=1, a_{i+2}=1$. Note that assume the indices of the two 1s are $l$ and $r$, we must have either $a_{l-1}=0$ or $a_{r+1}=0$ in order to solve this case. if there are an odd number of 0s between two 1s, similar to case 1, we first change all zeros to ones except for the rightmost zero. Now we have $1\dots 101$, then we perform an operation on 101, then do the similar thing on case 1 but from right to left. Note that there are no extra requirement to this case. So the strategy is firstly find one pair that can be solved then solve the remaining pairs from that pair in both direction. If none of the pairs can be solved, it's impossible to change all 1s to 0s. Submission: 129221560
 » 12 months ago, # |   0 https://codeforces.com/contest/1573/submission/129205633 Can someone please help me in figuring out why this submission gets TLE?
 » 12 months ago, # | ← Rev. 2 →   0 How to solve div2 B ?
•  » » 12 months ago, # ^ | ← Rev. 7 →   0 since array a is odd numbers and array b is even numbers. so lexicographically smaller/greater is defined at index 0. so only comparing values at index 0 is enough let cost[x] = # swaps to move a value v < x in array 'a' to index 0. ans = 2n and iterate over i = 0 to n - 1: ans = min(ans, i + cost[b[i]]); // i <- #swaps to move i_th number in array b to index 0 if iterating is over. the ans will be the answer ---------------- how to create cost array? intialize cost array with max value = n for (int i = 0; i < n; ++i) { cost[a[i]] = i; } for (int i = 1; i < 2 * n; ++i) { cost[i] = min(cost[i], cost[i - 1]); } 
•  » » 12 months ago, # ^ |   0 We need to find the minimum no of swaps so that no at the first index of odd array is less than the no at the first index of the even array . One way to do this is brute force. For each even no we try to get the nearest odd no which is less than that even no in the odd array. But this will be a O(n*n) algorithm and may give TLE for the tight constraints. So a better way is to store the indices in some ds like a map and for each no 2 4 6 8 ... We store the minimum of the indices of the current no — 1 and the index of previous no .And finally itterate through all the possibilities which will be only n checks and get the global minimal answer out of all the possible.My Accepted code :https://codeforces.com/contest/1573/submission/129208921
 » 12 months ago, # |   0 Although round got unrated but I liked task B!
 » 12 months ago, # |   -6 My segment tree solution for Div1 A
•  » » 12 months ago, # ^ |   +1 can you just briefly explain what you are storing/updating in the nodes?
 » 12 months ago, # |   0 Can anyone help me to find a counter case? 129205285
•  » » 12 months ago, # ^ |   0 1 4 3 2 3 4 0 2 2 4 0 Correct answer is 3 yours gives 2.I have used a similar approach with the topological sort, except instead of storing the chapters to be read in the next iteration in vec, i just added n to the chapter and pushed it into pq. 129229753
•  » » » 12 months ago, # ^ |   0 Thanks a lot, but i was so dumb that i forget priority queue stores greater elemnet first. I thought it keeps smaller element first. You just saved a lot of time mine.
 » 12 months ago, # |   0 I have tried a video editorial for problem C :book https://youtu.be/KWkkZEGffZw . Have a look at it..and if have any doubts let me know in comments
 » 12 months ago, # |   0 Can I change the statement that a[i] is (0/1) to [0,100000] on Problem 'Xor of 3'.Is there a solution?
•  » » 12 months ago, # ^ |   +3 Maybe you can solve the task in each bit, but the operation times may exceed $n$.
•  » » » 12 months ago, # ^ |   0 I think We can do that as well in n-1 operations.
•  » » 12 months ago, # ^ |   +3 I think my solution doesn’t use the 0/1 condition so probably yes.
 » 12 months ago, # |   +1
 » 12 months ago, # |   +41 editorial is also still in queue'' LOL
•  » » 12 months ago, # ^ |   +2 is the editorial rated ?
 » 12 months ago, # |   0 I'm newbie :(((
 » 12 months ago, # |   -8 For Question B, Can Someone please tell me why my approach is wrong? https://codeforces.com/contest/1573/submission/129231370My approach is that our task is to make a[0] < b[0], this can be done by two ways, either bring the closest number which is greater than a[0] in 'b' to the 0th position, let's say it is at j-index, then the answer will be 'j', or bring the closest element from 0 in a which is less than b[0], and the final answer is the minimum of both!Any counter test-case which fails this approach would be highly appreciated!
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 1 4 7 5 3 1 2 6 4 8 answer is 2 not 3
•  » » » 12 months ago, # ^ |   0 Thanks, I got it!
•  » » 12 months ago, # ^ |   0 You are only considering making the swaps on either a or b. In some cases it is beneficial to do the swaps on both arrays.
 » 12 months ago, # |   0 You want the clock to show 0 with as few operations as possible. In an operation, you can do one of the following:1 decrease the number on the clock by 1, or2 swap two digits (you can choose which digits to swap, and they don't have to be adjacent).here in 2nd operation we cannot swap adjecent digits but no one is talking about it ! plzz reply am not getting the exact thing or it is something that was some mistake from creators and now no one is talking about it since they got ac?
 » 12 months ago, # |   0 Is div1 B supposed to make us feel pain?
•  » » 12 months ago, # ^ |   0 Yes!.. No? Maybe.Check this solution out!
 » 12 months ago, # |   -9 Easy solution for B [Sparse Table]: 129189027
 » 12 months ago, # |   0 waiting for editorial ...
 » 12 months ago, # |   0 orz Molewus for the round being unrated.
 » 12 months ago, # |   -8