### SleepyShashwat's blog

By SleepyShashwat, 2 weeks ago,

Good Evening Codeforces! ^_^

I invite you to participate in Codeforces Round #682 (Div.2) taking place on Nov/13/2020 17:35 (Moscow time). The round, authored by Anti-Light and me, is rated for users rated less than 2100, while other users can participate non-competitively.

The round features six problems, and you have 2 hours to solve them. There may, or may not, be an interactive problem; regardless, you should know how to deal with them.

I would, now, like to thank–

We will announce the scoring distribution shortly. The scoring distribution is 500–750–1250–1750–2250-3000.

Good luck, and stay safe!

UPD: Editorial

For students in high school or below—

Participants who are currently in high school or below are eligible to win prizes — 25 USD gift cards to 5 random participants who solve at least 3 problems. Prizes are sponsored by Athena Education and are NOT related to Codeforces. To be eligible, please fill this form (it will be closed after the round ends). If you're interested in participating in other technical events, such as Machine Learning and Computational Linguistics, please head over to exunclan.com.

• +240

 » 2 weeks ago, # | ← Rev. 2 →   +4 Registered Participants are eligible for the following prizes. Registered participants on round or those who filled the form?
•  » » 2 weeks ago, # ^ |   +34 Those who filled the form; I have edited the blog to reflect this. Thank you!
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Is there any special registration for those who are participating in EXUN Clan's contest by DPS RKP?
 » 2 weeks ago, # |   +8 Hmm, it would have made sense if there were cash prizes for top rankers + random people, or only top rankers. But to have prizes only for random people is a bit weird.
 » 2 weeks ago, # | ← Rev. 2 →   +18 Expecting a Good Problem Set. Because it's SleepyShashwat
 » 2 weeks ago, # |   +16
 » 2 weeks ago, # |   +17 Hope you weren't sleepy while writing problem statements.
•  » » 2 weeks ago, # ^ |   +17 He lost a lot of sleep due to problem statements, that's why he's sleepy now.
 » 2 weeks ago, # |   -141 .
•  » » 2 weeks ago, # ^ |   -24 Seems like first time we are seeing Monogon loosing contribution
•  » » » 2 weeks ago, # ^ |   +75 I'll have to find a new source of dopamine now
•  » » » » 13 days ago, # ^ | ← Rev. 2 →   -32 Seems like you already found one, But sadly I have to loose some of my contributions because of above comment. Though I don't care about it(but who doesn't like green++).Edit:Also I can see realnimish gaining +47 because of my username, thats interesting. I think people should atleast appreciate my username, if they don't like the comments XD.
•  » » » » » 13 days ago, # ^ |   -12 Its a trap
•  » » » 2 weeks ago, # ^ |   +55 Its a trap
•  » » » 2 weeks ago, # ^ |   +13 You just see he will reply to the comments like yours and get 1k upvotes.
 » 2 weeks ago, # |   +78 intresting problems.
•  » » 13 days ago, # ^ |   +8 such a boy !
 » 2 weeks ago, # |   +33 I'm currently in high school but over 2100, so this round will be unrated for me. Will I still be eligible for any prizes?
•  » » 2 weeks ago, # ^ |   +27 Yeah, you are.
•  » » 13 days ago, # ^ |   +3 One prize gone
•  » » 13 days ago, # ^ |   +28 And here I am , Btech Final year and still switching between green and cyan.
•  » » » 13 days ago, # ^ |   0 Cyan and Green? Let just leave the conversation
•  » » » 13 days ago, # ^ |   +1 Here I am, Btech 3rd year and can't even climb up to green.
•  » » » » 13 days ago, # ^ |   0 I must say that your profile picture gives the PERFECT REACTION for your statement, LMAO ;)
•  » » » » » 12 days ago, # ^ |   0 Haha
 » 2 weeks ago, # | ← Rev. 2 →   -25 As a tester these problems were very interesting!
 » 2 weeks ago, # |   +98 Mandatory meme
•  » » 13 days ago, # ^ |   -15 yea codforces should provide more contests :,)
 » 2 weeks ago, # |   +1 [Your text to link here...]()
•  » » 13 days ago, # ^ |   -8 I am telling you that cute little face had no idea that round would be unrated.. Though had fun first 10 minutes of rounds..
 » 2 weeks ago, # |   +135 Finally!
 » 2 weeks ago, # |   +3 Wow that's a whole lot of testers!
 » 2 weeks ago, # |   +3 Now I am more excited about the 3b1b-style video editorials!!
 » 2 weeks ago, # |   0 lol, 1 week without contest,It was difficult, MikeMirzayanov
 » 2 weeks ago, # |   +13 please we request don't take 10 days gap for codeforces contest
 » 2 weeks ago, # |   +71 These 10 days made me realise the plight of div 1 users. Guys hats off to your patience (all div 1 users)
•  » » 13 days ago, # ^ |   0 Is that the polish eagle? fireblaze777
•  » » » 13 days ago, # ^ |   0 No, it is a phoenix ig
 » 2 weeks ago, # |   -6 yo 3b1b type videos? that's sick
 » 2 weeks ago, # |   +4 Finally a contest now :)It seems that there are much more people testing for the contest. So I think this Div.2 would be an excellent one :)
•  » » 13 days ago, # ^ |   +5 Oh no, it became an unrated contest becuase of B :-(
•  » » 13 days ago, # ^ |   0 I think I would like to delete my comment :-(Picture below shows how I feel when I saw the announcement that the contest is unrated...
 » 2 weeks ago, # |   +3 Finally something to cheer about
 » 2 weeks ago, # | ← Rev. 2 →   -15 hoping for good problem set sleepyshashwat
 » 2 weeks ago, # |   0 Waited)
 » 13 days ago, # |   +18 ![ ]()
 » 13 days ago, # |   +4 Wow, there is Anti-Light in writers too!!I guess this round is going to be awesome.
 » 13 days ago, # |   -13
 » 13 days ago, # |   +22 Happy Diwali :)
 » 13 days ago, # |   0 after a long waiting we got codeforces div 2 round thanks a lot...
 » 13 days ago, # |   -9 B should be of 1000 points like every contest. Don't know why they changed that in this contest.
 » 13 days ago, # |   -8 Indian Round :)
 » 13 days ago, # |   -17 They say it's an Indian contest but it isn't just an Indian contest, it's an Indian_Iranian contest. Because Anti-Light is Iranian. So... it means it's gonna be so good.
 » 13 days ago, # |   0 I didn't finish the form which to prove i'm a high school student. Could I finish it now?
 » 13 days ago, # |   +3 Happy Diwali Everyone !!
 » 13 days ago, # |   +101 problems are very sexy 10/10 would bang
 » 13 days ago, # |   -23 Is it rated?
•  » » 13 days ago, # ^ | ← Rev. 3 →   0 is rated for users rated less than 2100, while other users can participate non-competitively.so, Yes!Update: Not rated D:
•  » » 13 days ago, # ^ |   0 no(
•  » » » 13 days ago, # ^ |   0 ok mens))
•  » » 13 days ago, # ^ |   0 Nope :(
 » 13 days ago, # |   +1
 » 13 days ago, # | ← Rev. 2 →   +5 happy diwali to everyone out therethis diwali i pray to god so that your code gets compiled and accepted at one go(mine too :) ).happy diwali happy coding
 » 13 days ago, # | ← Rev. 2 →   0 Every body holds his hat XD
 » 13 days ago, # |   0 registered already but showing need to register to submit
 » 13 days ago, # |   +1 queue?
 » 13 days ago, # |   0 I submitted a source code before they changed N and T, and got WA for no reason, very cool.
 » 13 days ago, # |   0 Why the fuck the statement of B is changing?
 » 13 days ago, # |   0 No No Not again! Why Cf why ?
 » 13 days ago, # |   +5 what's going on. is that really unrated?
 » 13 days ago, # |   +3 I don't get it What was wrong with B?
•  » » 13 days ago, # ^ |   +3 same here, i also saw the correct constraints after submitting A in 2 minutes(they said constraints were wrong for 10 minutes)
 » 13 days ago, # |   +13 Got a round after so many days and that too became unrated :(
•  » » 13 days ago, # ^ |   +10 felt same. :(
 » 13 days ago, # |   +57 Friday the 13th
•  » » 13 days ago, # ^ |   0 Haatss offf !! to your braiin .lmao
 » 13 days ago, # |   -9 When I will tell my granchildren that we had rated contests on CodeForces, I bet they wouldn't believe me.
 » 13 days ago, # |   +6 After waiting for so many days, we got unrated round... :-(
•  » » 13 days ago, # ^ |   0 This is my first contest and that too became unrated..
 » 13 days ago, # |   +4 Why unrated? I was really fast in ABC, so sad :/
 » 13 days ago, # |   +32 So sad that this is unrated! It's first time I pass the D
 » 13 days ago, # |   +59 The problems are really good! It's a pity that so many testers and no one caught the issue with constraints on B :(
•  » » 13 days ago, # ^ |   0 What was the issue? I didn't get it !! Were the constraints low or high?
•  » » » 13 days ago, # ^ |   0 It's too low, so the chance to get RTE is high
•  » » » 13 days ago, # ^ |   +3 I believe the actual constraints were initially 2e5, but displayed as 1000-2000, then midcontest, the constraints were changed, and then again constraints were reverted back with updated TCs.Picture with updated constraints
•  » » » » 12 days ago, # ^ | ← Rev. 2 →   0 I need to delete my comment
•  » » 13 days ago, # ^ |   +29 Too many chefs spoils the food
•  » » » 13 days ago, # ^ |   0 so you're born
•  » » » » 13 days ago, # ^ |   0 Get the fuck outta here
•  » » 13 days ago, # ^ |   +1 Agree the problems were quite good could have been a great round.
•  » » 13 days ago, # ^ |   +30 I don't want to say too much, but this isn't the fault of testers.
•  » » » 13 days ago, # ^ |   +90 It is neither author's fault nor testers'. I guess it's contestants' fault that they couldn't guess the correct Constraints.
•  » » » » 13 days ago, # ^ | ← Rev. 2 →   +36 How about let's try to understand the situation better instead of making pointless sarcastic statements that no one actually implied.There are more people involved in contest preparation than just author and tester. Several times accidents have happened because things are changed (and sometimes, need to be changed) at last minute, when most testers have already completed their job. And often in real life, taking the blame isn't as easy as "it is person X's fault". There are often cases where something is shitty but no one actually really did anything wrong. Of course something has to change but it isn't as simple.
•  » » » » » 13 days ago, # ^ | ← Rev. 3 →   +10 Okay, sorry for that but if things are changed at the last minute, then it is better is postpone the contest and have it tested again. It's better for everyone.
•  » » » » » 13 days ago, # ^ |   +17 don't get me wrong but if the above comment was by Monogon you must have laughed and upvoted too.
•  » » » 13 days ago, # ^ | ← Rev. 2 →   0 Maybe they don't even know if the constraints are right or not, so it is not appropriate to put the responsibility on the testers without thinking about it, I think.
 » 13 days ago, # |   +14 You know . when you make round unrated half of participants are happy and half not !. im in unhappy group . also when the reason of that is just a bit change in limits!!!!
•  » » 12 days ago, # ^ |   0 this round is not rated?
 » 13 days ago, # |   +9 when u finally get <2k rank but round becomes unrated :(
 » 13 days ago, # |   +1 Luckily I didn't use array with constant space in B
 » 13 days ago, # |   +78 40 testers and noone used assert while testing to check the constraints??? Seriously what did all these testers do? Felling sad for the authors :(
•  » » 13 days ago, # ^ |   +35 Don't you know, testers job is to ask for contributions?
•  » » » 13 days ago, # ^ |   +41 Actually, testers could not get any contribution.
•  » » 13 days ago, # ^ |   +12 It's writer's job to add validator and validator tests. And coordinator's job to check if the author did it.
•  » » » 13 days ago, # ^ |   +17 I know, I was involved in preparing and testing many contests (Not Codeforces rounds). Usually while testing assert should added every where, to check the constraints and all other conditions.
 » 13 days ago, # |   +13 Very disappointing. 3 questions inside 25 mins and on track for CM status, and then it's unrated because the constraints were wrong.I sympathise with the writers and am grateful for the effort that is put in. How did the testers not pick this up?
 » 13 days ago, # |   +5 What was the mistake(in constraints) in B ?
•  » » 13 days ago, # ^ |   +6 The correct constraint is $2 \leq n \leq 1000$, but at the beginning of the contest it was $2 \leq n \leq 2 \times 10^5$. Now the constraints have been fixed.
•  » » » 13 days ago, # ^ |   0 I think it is the other way. The tests where with arrays of size up to 2e5, but the statement stated n<=1000. Then they changed the statement, then the tests, then the statement again to be like it first was.
 » 13 days ago, # |   +14 I am not sure what the testers are supposed to do but confirming the constraints seems like one of the first things to do. Anyways, the problems were nice. Also, I think there should be a gap between different tests in sample. Makes it a lot easier to read.
 » 13 days ago, # |   -12 Happy Diwali Everyone!
 » 13 days ago, # | ← Rev. 3 →   -30 .
•  » » 13 days ago, # ^ |   +33 There are still prizes so please don't discuss.
•  » » » 13 days ago, # ^ | ← Rev. 2 →   0 .
•  » » 13 days ago, # ^ |   +10 No, you can't
•  » » » 13 days ago, # ^ | ← Rev. 2 →   0 .
 » 13 days ago, # |   +49 It's a shame the round is unrated, the problems are quite beautiful. The issue with constraints on B was not the fault of authors, so please don't downvote the blog out of anger.
•  » » 13 days ago, # ^ |   -52 ok,We will downvote your comments from now on
•  » » » 13 days ago, # ^ |   +79 Downvote me for being supportive of the setters who had nothing to do with the cause of it being unrated? Okay, then I'm proud of those downvotes
•  » » » » 13 days ago, # ^ |   +14 Ok I had some slightly bad information at the time I made my comment, but I still stand that people shouldn't downvote the announcement or comments before understanding how the error happened. Still just wait for an explanation of what went wrong.
•  » » » 13 days ago, # ^ |   0 I don't think it's a wise move ...I know you're angry for the contest, yes, we are all disappointed, but no matter how the contest is, it's not the fault of these users who write their comment, I think. So it may be a better choice to delete what you say just now.No offense to anyone.
 » 13 days ago, # |   +15 Feeling Sad for SleepyShashwat !!! Problem set were really good !!
 » 13 days ago, # |   +9 ()
•  » » 13 days ago, # ^ |   -8 I can feel that.
 » 13 days ago, # |   -6 This is the first time i solved a problem with in 60 seconds i got 500 points but sadly the contest became unrated :(
•  » » 13 days ago, # ^ |   0 yeah and this is the first time I solved problem B in a contest.
 » 13 days ago, # |   +61 Even though it's unrated, don't discuss the problems, please, before the end of the contest. Writer is still going to give prizes
•  » » 13 days ago, # ^ |   -13 But why though? It evidently affected the round enough to make it unrated, but it still holds credibility for the Exun event (where you represent your school)?
 » 13 days ago, # | ← Rev. 2 →   -10 ready for the next round!
 » 13 days ago, # |   +15 One request to codeforces if round is unrated please use bold letters so we don't get a blow after a while
 » 13 days ago, # |   +61
•  » » 13 days ago, # ^ |   +112 Div 2 people should not be allowed to complain about contest frequency.
•  » » » 13 days ago, # ^ |   0 It's a joke mate
 » 13 days ago, # | ← Rev. 2 →   +81 [Deleted]
 » 13 days ago, # |   +1 B positive
 » 13 days ago, # |   0 The tasks were really very interesting.
 » 13 days ago, # |   0 When you solve 3 problems in 12 mins finally, after consecutive blows in previous contests, and the entire universe conspires to screw your rating!
•  » » 13 days ago, # ^ |   +6 hahahaha....reminds me of SRK's dialogue from Om Shanti OM !!
•  » » 13 days ago, # ^ |   0 to bad ;)
 » 13 days ago, # |   +1 Damn I couldn't get C but solved D and climbed to rank 18 for a moment. And now I am like bruh
 » 13 days ago, # |   0 Will try hard next time...
•  » » 13 days ago, # ^ |   0 no worries next time.....
•  » » » 13 days ago, # ^ |   0 Yes we should keep hope....
 » 13 days ago, # |   0 Actually,B doesn't really need an array.
 » 13 days ago, # |   +8 Thank you. I love Codeforces!
 » 13 days ago, # |   0 I sweeped A+B within 15 minutes and then watched the round ruin. But the problems were interesting, hoping to face more like these in future.
 » 13 days ago, # |   +6 If you got the idea of problem B, it didn't matter the constraints. And the notification of the correction was done with plenty of time to review the problem for any player. I don't think the effect to the score would be stronger than what happens when hidden tests fail at the end of the round after pretests passed. In my opinion, the round shouldn't be unrated...
 » 13 days ago, # |   +61
•  » » 13 days ago, # ^ |   0 I can feel that feelings, guy.Hold on for the contest on Sunday!
•  » » 13 days ago, # ^ |   0 How did you solve problem C? Can you explain your approach?
•  » » » 13 days ago, # ^ |   0 explaned this here
 » 13 days ago, # |   -12 came to read comment section just to be sure that It's unrated.
 » 13 days ago, # |   0 I was supposed to lose 73 points... and then the round became unrated.Anyways, I still think it's a pity that the round is unrated because problem B was nice (even though I couldn't solve it). Based on comments, the remaining problems were also nice.
 » 13 days ago, # |   +3 well i think i found solution to C but its way too hard for C and takes too long to code ... D was really easy for me on the other hand maybe im a potato :/
•  » » 13 days ago, # ^ |   +11 C is easy: You just have to make the parity of a[i][j] the same as i + j.
•  » » » 13 days ago, # ^ |   +8 yeah i found it rn lol glad its unrated
•  » » 13 days ago, # ^ |   +14 Well, you could make some elements even, and some elements odd. After actions your matrix mod 2 should look like: 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 So the algorithm is: if ((i % 2) + (j % 2) % 2 && a[i][j] % 2) a[i][j]++; else if ((i % 2) + (j % 2) % 2 == 0 && a[i][j] % 2 == 0) a[i][j]++; 
 » 13 days ago, # |   +4 Today maybe it was my best performance , and it got unrated .In the next contest it will be rated and I will get a minus 50. Cause that's life.
•  » » 13 days ago, # ^ |   +3 But it'll not change the fact that it is your best performance today isnt. Don't put a number tag on everything , life will be beautiful.
 » 13 days ago, # |   0 what is wrong with this idea for $D -$ If n is odd $or$ (n is even and there is no odd frequency element) then $YES$ else $NO$
•  » » 13 days ago, # ^ |   0 If all elements xor =0, then n is even will still be possible
•  » » 13 days ago, # ^ |   0 It should be : if n is odd or (n is even and the xor of all the elements is 0) then Yes else No !
•  » » 12 days ago, # ^ | ← Rev. 3 →   0 Try this testcase: 44 1 7 2 Answer is: YES11 2 3 because: 4 XOR 1 XOR 7 = 2
 » 13 days ago, # |   0 What is wrong with my code(problem D) https://codeforces.com/contest/1438/submission/98320619
 » 13 days ago, # |   +5 Dear division 1, the short interaction between you and me was nice. Now, we have to part away.
•  » » 13 days ago, # ^ |   0 dont worry its unrated xD
•  » » » 13 days ago, # ^ |   +6 Now, I'm out of 1700 in an unrated round where many participants left the contest. I'm raging even more now.
 » 13 days ago, # | ← Rev. 2 →   0 .
•  » » 13 days ago, # ^ |   +1 for each i and j, ensure that inp[i][j] + i + j is even (or odd). then adjacent numbers will have opposite parity, making sure that adjacent numbers are different.
•  » » 13 days ago, # ^ |   0 Try to arrange elements like , 0101010 1010101 0101010 where 0 represent an even number and 1 represent an odd number. Of course you can always change the parity of a number by adding 1 to it.I have seen that most of the people have done it by using dfs also.
 » 13 days ago, # |   +6 Well it was Friday the 13th. Coincidence? I think not :)
 » 13 days ago, # |   0 Can someone explain how to solve problem C?
•  » » 13 days ago, # ^ |   0
•  » » » 13 days ago, # ^ |   +1 fu**!! it was such an easy but a nice problem.
 » 13 days ago, # | ← Rev. 2 →   +76 3blue1brown styled Video Editorials:Problems A+B: https://www.youtube.com/watch?v=Z0JKnlmhVOc
•  » » 13 days ago, # ^ |   0 Awesome explainations man! I really hope you continue doing them for other rounds.
•  » » 13 days ago, # ^ |   0 looks like i supercomplicated B and C. :(
•  » » 13 days ago, # ^ |   0 Well explained man. Thank You.
•  » » 13 days ago, # ^ |   0 this is really good
•  » » 13 days ago, # ^ |   0 Really nice and quick realisation! Do you have a public repo where the code for the videos is published?
 » 13 days ago, # | ← Rev. 2 →   0 did you also overcomplicated solution for B or are you normal?expected solution was if all elements are distict print "NO" else "YES".
•  » » 13 days ago, # ^ | ← Rev. 2 →   +1 .
•  » » » 13 days ago, # ^ |   0 i used prefix sum and it's wrong i don't know why https://codeforces.com/contest/1438/submission/98322326
•  » » » » 13 days ago, # ^ |   0 2^$(10^9)$ won't find in int range or even long long range. So, your solution overflows
•  » » » » » 13 days ago, # ^ |   0 thank you
 » 13 days ago, # |   +10 So in D, I constructed solution for odd n and couldn't get the x-or = 0 thing for even n, foolishness 100. Just got it now.
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 for n-odd i think the solution is xor between all numbers and that's all. So you just have to print 1,2,3 1,4,5 .. 1,n-1,n for n-even i think you don't have solution if : all numbers have the same bit 1 or xor between all isn't 0. WA on test 4
•  » » 13 days ago, # ^ |   0 Same thing.
 » 13 days ago, # |   +19 Did anyone else use 2-SAT for C? xD
•  » » 13 days ago, # ^ |   +37 twf using dfs for C
•  » » » 13 days ago, # ^ |   +17 Pfft, you aren't a real programmer if you don't solve 2-SAT by putting it into your own hyper-optimized (exponential but still super fast) 400-row general SAT solver.
 » 13 days ago, # |   0 Nobody did any hacking, interesting XD
 » 13 days ago, # |   +56 It's okay that the round is unrated. It happens.However, I hope the announcement would emphasize the fact that it's unrated when it's unrated. I saw only the first two sentences of the announcement, and I didn't read the rest of it because I saw that it was talking about problem B and I already passed it, so I thought there is no need for me to read it any further.
•  » » 13 days ago, # ^ |   0 Exactly. I just now came to know that the round is unrated :(
 » 13 days ago, # |   -8 How will the prizes be given now since the round is unrated and maybe many participants left the contest in between?
 » 13 days ago, # |   +3 Can anyone explain why my dfs solution for C is giving wrong answer on pretest-2 here's my Submission.I've tried it on some other test cases and unable to find any mistake. Can anyone help?
•  » » 13 days ago, # ^ |   0 Spoiler1 3 2 3 3 1 3 2 2 Basically, it's possible for your code to increment the same value twice.
 » 13 days ago, # | ← Rev. 5 →   +34 My solutions: AAnswer=[1]*n BPainfully try to squeeze in random modulo, ehm... 2 equal b[i]s --> answer = YES, otherwise = NO CTry to satisfy "non-equal-neighbors" condition modulo 2 SpoilerIf we color odd bi-s black and even bi-s white, then b table will be colored like a checkerboard. Hence the solution: b_ij%2 needs to be equal to (i+j)%2 DObservation 1: xor or all ai-s is an invariant (because (ai+aj+ak) == (ai+aj+ak) + (ai+aj+ak) + (ai+aj+ak))Suppose that in the end we end up with a final array == ([u] * n), then the xor of the final array is 0 (if n is even), or u (if n is odd)If n is even, and xor of or all ai-s != 0, then the answer is NO (due to invariant)If n is odd, then the answer is YES (I'll use example with n=7, here a123 = a1+a2+a3)[a1, a2, a3, a4, a5, a6, a7] ->[a123, a123, a123, a4, a5, a6, a7] ->[a12345, a123, a123, a12345, a12345, a6, a7] ->[a1234567, a123, a123, a12345, a12345, a1234567, a1234567] ->[a1234567, a1234567, a1234567, a12345, a12345, a1234567, a1234567] ->[a1234567, a1234567, a1234567, a1234567, a1234567, a1234567, a1234567] ->If n is even, and xor of or all ai-s == 0, then the answer is YES (I'll use example with n=6)[a1, a2, a3, a4, a5, a6] -> [a123, a123, a123, a4, a5, a6] ->[a12345, a123, a123, a12345, a12345, a6] ->[a12345, a12345, a12345, a12345, a12345, a6]Notice that a12345 == a6 because xor of or all ai-s == 0 (a12345 + a6 == 0) F420+4-2-0 times do the following: pick three different numbers u, v, w and put query(u, v, w) to array.With very high probability (>= 1/2 * 1/2 == 1/4 ???) result = either left or right child of root.Pick 2 most frequent labels of this array (call them child1, child2).For n-2 other labels x: if query(child1, child2, x)==x, then return x as resulting root. ENote that because a[i]>0, then a[l+1]+...+a[r-1] > 0, so a[l] xor a[r] >0, so there should be at least one 1 in binary representation of a[l] xor a[r]Lets suppose that most significant non-zero bit of a[l] xor a[r] == b. Lets also suppose that b-th bit of al is 0 and of ar is 1: bit(a[l], b)==0, and bit(a[r], b)==1 (we can handle the case bit(a[l], b)==1 and bit(a[r], b)==0 by reversing array b).Lets iterate over all possible choices of l and b: - find r1 == smallest i>=l+2, such that bit(a[i], b)==1; (O(1) with preprocessing) - find r2 == smallest i>=r1+1, such that bit(a[i], b)==1; (also O(1) with preprocessing)Check if [l, r1] and [l, r2] are valid segments (O(1) with prefix sums) Note that there are no more segments [l, r] for fixed l and b, that is, r cannot be > r2.Why? Because if r>=r2+1, then a[l+1]+...+a[r-1]>=+a[r1]+a[r2]>= 2**b + 2**b == 2**b+1, but this also contradicts our assumption that most significant bit of a[l] xor a[r] is b.As a corollary: answer <= 30 * n * 2 * 2
 » 13 days ago, # |   0 Video Editorials https://www.youtube.com/watch?v=RXJOWUEQz7k
 » 13 days ago, # |   +8 Finally 13 th November. It's Unrated,still intrigued with some great problems....
 » 13 days ago, # |   -30 Lodu contest
 » 13 days ago, # |   0 Can anyone please tell me as to why this solution to B was wrong? Link to Submission98288806
•  » » 13 days ago, # ^ |   0 You need to read the full input for each test case.
•  » » 13 days ago, # ^ |   0 Try this testcase152 2 2 2 2Your programme will not take all of the inputs.
•  » » » 13 days ago, # ^ |   0 Thanks a lot!
 » 13 days ago, # |   +1 Never keep a contest on Friday the 13th
 » 13 days ago, # |   0 Is it unrated now?
•  » » 13 days ago, # ^ |   0 Isn't that obvious?
 » 13 days ago, # |   0 Video Editorials https://www.youtube.com/watch?v=xxAr1ytqWhs
 » 13 days ago, # |   0 We want one more rated contest in this week as this contest became unrated
•  » » 13 days ago, # ^ |   0 agree
•  » » 13 days ago, # ^ |   0 And there is one on Sunday :)
•  » » » 13 days ago, # ^ |   0 I wanted to say arrange one more contest including other contests for the recovery of this unrated round.
 » 13 days ago, # |   0 Why this solution doesn't work 98303387, but this solution works 98327745?
•  » » 13 days ago, # ^ |   0 Because in the first one when i=n-1, a[i+1] is out of bounds.
 » 13 days ago, # | ← Rev. 3 →   +11 Important test case is missing from D. I submitted what should be an incorrect solution, and later resubmitted a correct solution. However, my incorrect solution also passes.The test case in question is where N = 4 and the answer is YES, e.g. N = 4, A = 2 2 2 2, or N = 4, A = 1 1 3 3My incorrect code printed out "N-4" as the the number of steps, which gives an output: steps = 0, ops = 1 2 3Clearly this is incorrect, and I corrected my code to output: steps = 1, ops = 1 2 3However the test cases are not currently sufficient to identify this bug.
•  » » 13 days ago, # ^ |   0 I think it's checker's job to check the correctness of your outputThe checker reads the number of steps. Because it's 0, the checker doesn't read any operations and your output is correct. CMIIW
•  » » » 13 days ago, # ^ |   0 0 would be an incorrect number of steps in the case N = 4, A = 1 1 3 3
•  » » » » 13 days ago, # ^ |   0 Yeah you're right, I didn't test your program with the last input
 » 13 days ago, # |   0 some please point the mistake in this Problem C solution solution_link
•  » » 13 days ago, # ^ |   0 try this testcase 1 2 3 2 2 4 2 2 3
 » 13 days ago, # | ← Rev. 2 →   +1 Easy solution to problem E:Notice that if $a_l \oplus a_r = a_{l+1} + a_{l+2} + ... + a_{r-2} + a_{r-1}$ is satisfied, then $a_l + a_r \geq a_{l+1} + a_{l+2} + ... + a_{r-2} + a_{r-1}$ is also satisfied.Assume we fix the position of the rightmost element $r$. Now let $l$ be the index of the first element to the left of $r$, so that $a_l + a_r \geq a_{l+1} + a_{l+2} + ... + a_{r-2} + a_{r-1}$. The sum of $a_l ... a_r$ is at least twice as large as the sum of $a_{l+1}...a_{r-1}$. Lets denote the sum $a_{l+1}...a_{r-1}$ by $x$. Notice that the element at the next valid left endpoint will have to be at least $x * 2$, the next one at least $x * 4$ ... Hence there are at most $log(maxA)$ candidate left endpoints for a single $r$. We can check all of these subarrays $O(N \cdot logN \cdot log(maxA))$ time using range queries or set (the solution works with a very small constant factor).
 » 13 days ago, # | ← Rev. 2 →   0 Hello, a newcomer here.I was trying to use pypy3 to do F, and I got a lot of TLE's. I tried many ways to go around this, but I wasn't able to find a not-very-dodgy solution: I had to do it in "batches"https://codeforces.com/contest/1438/submission/98332683Is there a not-very-dodgy way to do this with pypy?Here are some of my failed attempts: https://codeforces.com/contest/1438/submission/98331404 https://codeforces.com/contest/1438/submission/98330796
•  » » 13 days ago, # ^ |   0 I agree with this. I can't find a way to fit the solution within the time limits using pypy either.
 » 13 days ago, # |   0 can anyone explain code from jiangly  int t; std::cin >> t; while (t--) { int n, m; std::cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { int a; std::cin >> a; std::cout << a + (a % 2 != (i + j) % 2) << " \n"[j == m]; } } } // Plz explain this line // std::cout << a + (a % 2 != (i + j) % 2) << " \n"[j == m]; Thank you folks. 
•  » » 13 days ago, # ^ |   0 If (a % 2 != (i + j) % 2) this statement is true it will add 1 with a . And the statement means -->> a odd and (i+j) even -OR- a even and (i+j) odd.
•  » » » 13 days ago, # ^ |   0 how does this syntax works << " \n"[j == m]; ?
•  » » » » 13 days ago, # ^ | ← Rev. 2 →   0 That's the equivalent of saying:if (j == m) cout << '\n';EDIT: Think of it this way:You are given a string of two characters ' ' and '\n', which is represented as " \n". Take the character at index [j == m]. Keep in mind that j == m yields either 1 (true) or 0 (false).Hope it clears it up.
•  » » » » 13 days ago, # ^ |   0 if j==m it will print a new line otherwise a space
•  » » » » » 13 days ago, # ^ |   0 got him man, he really writes few lines of code in his every soln..
 » 13 days ago, # |   -28 upvote this comment if you too think today's contest was mainly based on simple observations only.[please don't downvote to pull my leg]
•  » » 13 days ago, # ^ |   0 That's the case with most Div2 rounds nowadays, which is by no means a bad thing. In fact it's only true with A, B and C problems. Give D, E and F a go and you'll be proven wrong very easily. People of all levels get 1 problem to play with, while others stay far below/above their current level and in my opinion that is very well balanced.Problem solving is all about logical thinking and making observations, maths and algorithms are really the tools to execute the idea.
•  » » » 13 days ago, # ^ |   0 great insights.