### thanhchauns2's blog

By thanhchauns2, 7 weeks ago,

# Hi Codeforces!

_dlbm17, DeMen100ns, SPyofgame and I are delighted to invite you to participate in Codeforces Round #812 (Div. 2).

This contest is brought to you by:

Special thanks to:

The score distribution is 500-1000-1750-2000-2500-3000

Hope to see you in final standings!

UPD: We have a small gift for a Vietnamese participant who have the highest score, so if it is you, please DM me after contest. Good luck everybody!

UPD2: Editorial

UPD3: Congratulations to the winners!

Div.2:

Div.1 + 2:

• +845

 » 2 weeks ago, # |   +91 As an author, love you SPyofgame
•  » » 2 weeks ago, # ^ |   +78 As a coauthor, love you SPyofgame
•  » » » 2 weeks ago, # ^ |   +90 As a stupidest author, love you SPyofgame
•  » » » » 2 weeks ago, # ^ |   +62 As a tester, love you SPyofgame
•  » » » » » 2 weeks ago, # ^ |   +52 As a tester, love you SPyofgame
•  » » » » » » 13 days ago, # ^ |   +8 As a participant, love you SPyofgame
•  » » » » » » » 11 days ago, # ^ |   +2 As a participant, love you SPyofgame
•  » » » » » » » » 11 days ago, # ^ |   +43 As a tester, love you SPyofgame (though i don't know why i have to love you) =))))))
•  » » » » » » » » » 11 days ago, # ^ |   +4 As a participant, love you SPyofgame
•  » » » » » » » » » 11 days ago, # ^ |   +9 As a participant, love you SPyofgame
•  » » » » » » » » » 11 days ago, # ^ |   -12 As a participant, love you SPyofgame
•  » » » » » » » » » 10 days ago, # ^ |   0 As a participant, love you SPyofgame
•  » » » » » » » » » 10 days ago, # ^ |   0 As a participant, love you SPyofgame
•  » » » » » » » » » 10 days ago, # ^ |   +1 As a participant, love you SPyofgame
•  » » » » » » » » » 10 days ago, # ^ |   +7 As a master, love you SPyofgame
•  » » » » » » » » » 10 days ago, # ^ |   -16 As a candidate master, love you SPyofgame
•  » » » 11 days ago, # ^ |   0 Hello everyone and good luck in today's round, you can all try to solve as many problems as possible
•  » » 13 days ago, # ^ |   +15 As a tester, love you SPyofgame
•  » » 11 days ago, # ^ |   +44 flashback to 4 months ago
•  » » » 10 days ago, # ^ |   +1 A curious mind wants to know what happened!
•  » » » » 10 days ago, # ^ |   +1 Same question )
•  » » » » 10 days ago, # ^ |   +1 Nothing happened actually, it seems like they are friends and just like to troll each other. It was Codeforces Round #779 (Div. 2) btw.
•  » » 11 days ago, # ^ |   0 You can do anything, just don't give up!
•  » » 10 days ago, # ^ |   0 As a participant, love you SPyofgame
•  » » 10 days ago, # ^ |   0 As a participant: Spoilernothing
•  » » 9 days ago, # ^ |   0 As a beneficial participant, love you SPyofgame
 » 2 weeks ago, # |   +30 As a fan of idol thanhchauns2, I'm really looking forward to participating and solving his own contest. Hope everyone have a great time!
 » 2 weeks ago, # |   +169 problems are great! Спойлерor i will shave my hair
•  » » 11 days ago, # ^ |   +21 I wish every tester from now own takes this kind of oathproceeds to get a ocean full of shaved heads
•  » » » 11 days ago, # ^ |   +24 but not this time, trust me
•  » » 11 days ago, # ^ | ← Rev. 3 →   +57 tester này nghiện ma túy
•  » » 11 days ago, # ^ |   +50 who ask
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 sorry to say that, but I expect to see you with shaved hairAnd no, in generall contest was good and most problems are really really great, but look at ThisIg it's not OK that I spent more time on A than on B/C/D?CMON I SOLVED D FASTER THAN A
•  » » » 10 days ago, # ^ |   +1 I think it is the explanation, haha.
•  » » » » 10 days ago, # ^ | ← Rev. 2 →   +1 Curious to ask, explanation to what?P.s. No negative in this comment, but I really didn't get, sorry xd
•  » » » » » 10 days ago, # ^ |   +1 I think what make problem A harder than usual is the explanation. If we remove it maybe you will find it easier.
•  » » » » » » 10 days ago, # ^ |   +4 well, after I've read comments I understood one thingIt's my guilt that I didn't read that either X or Y is 0I'm very very sory, problem A was great, and not hard at all, I just should've read statements properly :)
•  » » » » » » » 9 days ago, # ^ |   +4 now that makes sense, i can't imagine an expert struggling to solve d2a.
•  » » » » » » » » 9 days ago, # ^ |   0 Xd, I'm sorryI understood it in way that all coordinates are (x,y) not necessarily zeroAnd actually, if I solved A at the time, an CM, not Expert :'( :noo:
•  » » » » » » » » » 8 days ago, # ^ |   0 better luck next contest (‾◡◝)
•  » » » » » » » » » 8 days ago, # ^ |   0 Thanks!
•  » » 10 days ago, # ^ |   +8 Cannot disagree.
 » 13 days ago, # |   0 Good luck everyone!
 » 13 days ago, # |   +8 ᓚᘏᗢ
 » 13 days ago, # |   +11 As a tester, I wish u guys could gain the rating :3
 » 13 days ago, # |   +5 Excited to see and all the everyone!!
 » 13 days ago, # |   +19 As a tester, hope you guys to enjoy this round.As a weeb, I recommend you guys Youzitsu (Light Novel) and Gabriel Dropout (Anime/Manga)
 » 13 days ago, # | ← Rev. 2 →   0 wish everyone can do their best!
 » 13 days ago, # |   +5 As a tester, I hate love DeMen100ns
 » 13 days ago, # |   +8 hydroshiba orz
 » 13 days ago, # | ← Rev. 2 →   +8 As the biggest fan of DeMen100ns and SPyofgame, hydroshiba orz
 » 13 days ago, # |   +30 As a tester......I'll give you guys a chance to fill the rest of this sentence
•  » » 13 days ago, # ^ |   +5 ...give hydroshiba contribution
•  » » 13 days ago, # ^ |   +15 ... amogus
•  » » 10 days ago, # ^ |   0 ..who tested?
 » 13 days ago, # |   +6 Intentionally skipped testing this round, hope this one will be as good as previous one
•  » » 11 days ago, # ^ |   +22 I unintentionally became master...
•  » » » 11 days ago, # ^ |   +4 it will still be rated for you because you registered before becoming master xDD
 » 13 days ago, # |   +10 The white text is painfully obvious on mobile
 » 13 days ago, # |   +22 My best effort in this project is breathing instead of making instant-rejected problems (")>
 » 13 days ago, # |   0 Finally your round, obviously I will take part in it
 » 13 days ago, # |   +9 "Last but not least, you for your participation and being WA, then dropping at least one color :P" It's the best easter egg I've ever seen :P
 » 12 days ago, # |   +6 amogus
 » 12 days ago, # |   0 orz
 » 11 days ago, # |   +15 why this announcement is published 6 weeks ago?
•  » » 11 days ago, # ^ |   +6 Probably because that's when it was announced? It was only added to the Home page now because it's the next contest. There are three other contests scheduled that should also be added to the Home page when they're up next.
•  » » » 11 days ago, # ^ |   +7 I saved it in a draft, only published a few days ago.
 » 11 days ago, # |   0 nice :>
 » 11 days ago, # |   0 orz
 » 11 days ago, # |   0 I can't wait to solve more than 3 problems!
 » 11 days ago, # |   0 Is the problem C of DIV2 harder than before？
 » 11 days ago, # |   +16 As a tester, i worked with authors who are talented high school, college students, they had to make a lot of efforts to prepare problemset during months, some problems were rejected or removed to have the best problemset for contestants. So no matter what you feel about this round, plz upvote this contest to encourage young Vietnamese CP-ers to contribute global CP community. Finally, let's enjoy our problems and hope all you guy get good ranking.
•  » » 11 days ago, # ^ |   +4 yeah, you are right. Everyone who has made efforts to this contest deserve encouragement!
 » 11 days ago, # |   +1 By the way, the kitty on the promotional picture is really cute (>w<)
 » 11 days ago, # |   +1 Picture looks really good,hope it will be a nice round :)
 » 11 days ago, # |   +1 I hope that C, D will not be as difficult as in the previous contest
•  » » 10 days ago, # ^ |   0 C and D were rated 2000 in the previous one. Unusual for an edu div 2 round
 » 11 days ago, # |   +5 Hope I can reach Master after this round! Good luck to everyone!
 » 11 days ago, # |   0 I hope I will solve problem C
 » 11 days ago, # |   +11 Seems like nobody notice that our coauthor, DeMen100ns has two colors in the announcement.
•  » » 11 days ago, # ^ | ← Rev. 2 →   +4 Some of us noticed but I guess nobody thought it's important enough to be written in the comments lol
•  » » » 11 days ago, # ^ |   0 Lol, okay.
•  » » » 11 days ago, # ^ |   0 Ngl, I legit didn't notice it.
 » 11 days ago, # |   0 Hope everyone have fun!
 » 11 days ago, # |   +9 Most colourful blog I've seen in a while :3
 » 11 days ago, # |   +4
 » 11 days ago, # |   -66 Watch as people upvote me just because I am a GM
•  » » 10 days ago, # ^ |   +32 Watch as people downvote me just because I am a Pupil
•  » » » 9 days ago, # ^ |   0 watch as people do nothing, just because i am somewhere in between ;)
•  » » 10 days ago, # ^ |   +13 ...or not
 » 11 days ago, # |   +11
 » 11 days ago, # |   +1 Wish I can solve at least one problem!
•  » » 11 days ago, # ^ |   0 good luck
 » 11 days ago, # |   0 Good luck! love you SPyofgame
 » 11 days ago, # |   +1 Again a contest with a huge gap between B and C :(
 » 11 days ago, # |   0 Chauncey says Good Luck!!
 » 11 days ago, # |   0 i would personally prefer two minutes later, but ok
 » 11 days ago, # | ← Rev. 3 →   -26
•  » » 11 days ago, # ^ |   0 This feels so real, I'm already afraid of not being able to make C, my friend
•  » » 10 days ago, # ^ |   0 Good thing that this round was pretty balanced tho. I can solve A, B, C yay :D
 » 11 days ago, # |   0 Is this rated for me? Up to 2100 or up to 1900
•  » » 11 days ago, # ^ |   +5 Up to 2100.
 » 11 days ago, # |   +4 C 1750 looks scary :(
•  » » 11 days ago, # ^ |   0 Hope my last contest till expert ;)
 » 11 days ago, # |   +39 I will try to become Expert in this contest! OtherwiseI will try to become Expert in the next contest but won't shave my hairs! :)
 » 11 days ago, # |   0 According to the points distribution, I guess C is going to be a good question. So what do u think ?
•  » » 10 days ago, # ^ |   0 Same
 » 11 days ago, # |   0 I will become specialist this contest!!!
•  » » 10 days ago, # ^ |   0 nice you did it!
 » 11 days ago, # |   +3 Good luck for everyone ❤(✿◕‿◕✿)❤
 » 11 days ago, # |   0 As a participant, I wish myself good luck in advance
 » 11 days ago, # |   +72 One of the authors is in a really bad health situation right now. To all participants, please shows your respect to him by solving as many problems as you can, we all want him to overcome as soon as possible.
 » 10 days ago, # |   +13 | Last but not least, you for your participation and being WA, then dropping at least one color :PB-but we can't drop any more colors -Pros and cons of being a newb
 » 10 days ago, # |   0 Happy World Wibe Web Day
 » 10 days ago, # |   0 Hope everyone get +rating changes
 » 10 days ago, # | ← Rev. 3 →   0 .
 » 10 days ago, # |   0 I guess the interactive problem is problem C because it has 1750 points :) Is my thinking correct or not ?
•  » » 10 days ago, # ^ |   0 As far as I know, ABC are never interactive since they only should require basic data structures and math knowledge sometimes (and their statement should be clear to everybody), the interactive problem will probably be D or F (my opinion :)), it's just because authors probably came up with this C, but they think it's a bit more difficult than usual, so they made it 1750
•  » » » 10 days ago, # ^ |   0 Agreed with you <3
•  » » » 10 days ago, # ^ |   0 C was interactive sometimes, AB — never
•  » » » » 8 days ago, # ^ |   0 AB — never What do you think about this ?
•  » » » » » 8 days ago, # ^ |   0 Ok, take my words back. When I tried to propose some interactive problems they said that it is too hard for D2B
•  » » » 9 days ago, # ^ |   0 My predictions came true lol
 » 10 days ago, # |   0 Hope to bring us a good experience,in addition,good luck to everyone!
 » 10 days ago, # |   0 Score of 1750 for C, its gonna be a toughy, hope I can pull through.
 » 10 days ago, # |   0 Good luck every body
 » 10 days ago, # |   0 All the Best @EveryOne !!
 » 10 days ago, # |   0 Hope i solve AB
 » 10 days ago, # | ← Rev. 2 →   0 Hope I become pupil in this contest
•  » » 10 days ago, # ^ |   0 You will broo !!
 » 10 days ago, # |   0 leetcode overlapping contest :( Anyways will solve at least 1st on leetcode, just to get coins for a leetcode shirt :)
 » 10 days ago, # |   0 Stuck on problem A :holyfuck:.
•  » » 10 days ago, # ^ |   0 Fucking love this contest!!!!
•  » » 10 days ago, # ^ |   +1 same didn't notice either x or y is 0 always.
 » 10 days ago, # | ← Rev. 2 →   0 b and c are very good problems!
•  » » 10 days ago, # ^ |   0 b is nice but c is too standard
 » 10 days ago, # |   +31 How does a blue coder solve f in 5 minutes? Jiangly didn't do it for 40 minutes.
•  » » 10 days ago, # ^ |   -15 Never judge a person by his color
•  » » » 10 days ago, # ^ |   +13 But judge person's skill by his color.
•  » » » 10 days ago, # ^ |   0 but more skilled people do tend to have higher ratings in many cases (don't judge me, I've just been unlucky in many ways)
•  » » » 10 days ago, # ^ |   0 But it's still strange and unbelievable for anyone to solve a Div.2F in 5min.
•  » » » » 10 days ago, # ^ |   -10 can you give me handle of that person
•  » » 10 days ago, # ^ | ← Rev. 4 →   0 Sorry I do suspect std leaks, but I have no ill intentions, I'm just speculating how he cheated.
•  » » 10 days ago, # ^ |   0 maybe some smurf :D
•  » » 10 days ago, # ^ |   0 Now I have almost enough proof that he is cheating. 1. He has two d and e submissions in the contest, with only a dozen seconds between them. 2. After passing the pretest of d, he submitted it again after a minute, and then wa2. This is obviously cheating by multiple people solving the problem at the same time, writers please check him. [user:thanhchauns2][user:DeMen100ns]
•  » » » 9 days ago, # ^ |   0 I agree with u but it's hard to check if he really cheated.
 » 10 days ago, # |   0 How to solve E?
•  » » 10 days ago, # ^ |   +18 2Sat, but you don't have to do a whole offline incremental SCC bs, instead you only need to maintain a DSU, check if the next restriction can be satisfied, if so change the matrix accordingly, otherwise ignore it.
•  » » » 10 days ago, # ^ |   0 In which order do you enumerate the restrictions?
•  » » » » 10 days ago, # ^ |   +8 We only iterate over the triangle above the diagonal, and we iterate from the first row to the last row with left to right in each row,
•  » » » » » 10 days ago, # ^ |   0 I see, thanks!
 » 10 days ago, # |   +1 Video Solution for Problem C.
 » 10 days ago, # |   0 Hi, I solved problem C at 1:14:31. But later i saw the code and felt that it might fail system testing as i used int instead of long at one place so i submitted again at 1:47:33 and as of now both are showing pretest passed. But i am getting points according to the 2nd attempt. If after system testing my 1st accepted solution does not fail so will i get score according to my 1st submission or 2nd submission?
•  » » 10 days ago, # ^ |   0 During system testing, your first submission will be skipped and your second submission will be considered. Also you'll lose extra 50 points for resubmission.
•  » » » 10 days ago, # ^ |   0 ok thanks,Due to unnecessary resubmission i lost around 280 points today.
•  » » » » 10 days ago, # ^ |   +1 I wouldn't consider it unnecessary if you personally had doubts about your solution. If you couldn't assure yourself that it would pass, then it would have been risky not to resubmit, since you would have lost a lot more points if it failed. Better to resubmit early than to wait until it gets hacked, or worse, until it fails system testing. I think the real lesson is that you should really examine your code carefully before the first submission, and that if you have some doubts later on, you should think carefully about whether such concerns could actually prevent acceptance. If you are unable to clear such concerns, then I think you should resubmit without regrets, even if you realize after the contest that it was okay. Hindsight is 20/20, after all.
•  » » 10 days ago, # ^ |   0 According to Codeforces Contest Rules If a contestant submits several times a problem's solution that passes all pretests, then the last solution is considered as the contestant's verified solution for this problem. All other solutions will be considered as unsuccessful attempts.
•  » » 10 days ago, # ^ |   0 The rules are that a resubmission will incur the -50 penalty, regardless of whether the former would have passed system test or not. It's unfortunate, but that's how it is.While there is no way to know for sure whether your first submission would have passed the system test now, I think int should be perfectly fine, because the largest square that needs to be considered is at most $2 (n - 1)$, which is well within int limits (unless you did something really crazy in your solution).
•  » » » 10 days ago, # ^ |   0 yeah largest square required is 2(n-1) only in my solution as well but i just thought of changing it at the end moment.
 » 10 days ago, # | ← Rev. 2 →   -10 Amazing contest!I am very happy because I solved 3 problems (A, B and C), unfortunately I solved them too late with 2 WA on pretest 2 verdicts. Does anybody know some real tips on how to solve problems faster and with less wrong submissions?
 » 10 days ago, # |   +3 Great problems. (Specially D) How to solve D? Did anyone get AC using randomized algorithms, it would be great if someone could share some insights.
•  » » 10 days ago, # ^ |   +3 hint: you can determine the winner of the four using only 2 questions
•  » » » 10 days ago, # ^ |   0 but how
•  » » » » 10 days ago, # ^ |   0 Let $a, b, c, d$ denote the four people. Query $a, c$. If we get zero, they are both losers as the winner would have more wins than the rest. Otherwise, if it is 1, then we ask $a, d$, and if the initial result was 2, then we ask $b, c$. Voila
•  » » » » » 10 days ago, # ^ |   0 Thanks, I was thinking about a wrong problem -.-I thought that the labels of participants can be permutated (ie. 1 doesn't have to play 2 at the beginning)
•  » » » » » 10 days ago, # ^ |   0 Hmm... I think I have done it exactly the way you described. Don't know why it doesn't work. https://codeforces.com/contest/1713/submission/167297638
•  » » » » » » 10 days ago, # ^ | ← Rev. 3 →   0 I guess I used too many memory by using long long...Update: my approach was wrong
•  » » 10 days ago, # ^ | ← Rev. 2 →   +6 When you query four consecutive people, it only takes two queries to figure out who the winner is out of the four people. Maintain the array of winners from the last iteration, repeat the two queries per four people, until you have either two people, or a single person, then we know the winner. The number of queries used is the sum $2^{n-1} + 2^{n-3} + ... + 2^1 (or~2^0)$ and it is easy to see that this is below the query limits
•  » » » 10 days ago, # ^ | ← Rev. 2 →   0 Sad I didn't know what to do with this information, I figured out to find a winner among four people in 2 queries during the contest. Thanks
 » 10 days ago, # | ← Rev. 2 →   0 what is the observation for b? time is very tight for c can an o(n*k) solution pass main tests? where k is number of perfect numbers less than 2 * 1e5?
•  » » 10 days ago, # ^ |   0 ObservationCurrent minimum element in the current subarray must be either at beginning or end of the current subarray.
•  » » » 10 days ago, # ^ |   0 oh thanks, so is it enough to check if arr[i] < arr[i — 1] && arr[i] < arr[i + 1] ?
•  » » » » 10 days ago, # ^ |   0 No, you need to check the smallest element in the subarray.
•  » » » » » 10 days ago, # ^ |   0 ok thanks alot
 » 10 days ago, # |   +8 For problem D the time limit was so tight using java it passed with C++ but cost me 20 minutes to debug in C++ since I don't use it much, couldn't you make a larger time limit for java? other than that the problems were really good.
 » 10 days ago, # |   0 Problems were interesting.
 » 10 days ago, # | ← Rev. 2 →   +14 As a Candidate master, I even can not solve C, and I got the worst standing since I sign in Codeforces... sad
•  » » 10 days ago, # ^ |   -28 C is worst problem in long time... we have to see simple but completly random stupid observation. Like christmas riddle for pre schoolers.
•  » » » 10 days ago, # ^ |   0 The fact that there always exists a square between $[n, 2n]$ is not something I would consider to be stupid at all... In fact, this is not only easily observed from thinking of small examples, but it's also easy to prove.Similarly, the observation that $(a + b) = (a + i + b - i)$ is extremely trivial. Neither of these are stupid. It does require some mathematical maturity to realize that these two observations would lead to an exact solution, but there is no randomness or stupidity involved here.
•  » » » 10 days ago, # ^ |   +1 It's not a stupid observation. You can do strong induction and claim that if you can build array using numbers (0,i), for each 0<=i<=n, it's also possible to do so with numbers (0,n+1). This is due to the fact that there's at least one perfect square between i and 2*i. Now you have construction using the given prime for finding (n+1)-th element, and thus can fill the suffix (i,n+1) in increasing fashion, and due to induction hypothesis we can build the remaining part.It's a cute problem imo.
•  » » » 10 days ago, # ^ |   +1 I think both C&D are tricky, agree with that the observation of C is quite random. Again, sadly I didn't pass any of them... This time I may lose more than 150 rating ... :(
•  » » » 10 days ago, # ^ |   0 C was solvable using Maximum Bipartite Matching!!!
•  » » » » 8 days ago, # ^ |   0 plz explain your approach using Max Bipartite Matching
•  » » » » » 8 days ago, # ^ |   0 We know that for every number from 0 to n — 1, we need a number to be added to it so that it's sum is a square number. We also know that for each i, i + k == square_number, then k should be between 0 and n — 1 inclusive. So we will iterate over all square numbers such that square_number — i <= n — 1, say k. Then we will add an edge between i and k. Since we need N pairs, and these pairs should not contain pairings with the same number, we can use bipartite matching. My solution : 167261911
•  » » 10 days ago, # ^ |   +6 As a Specialist, I even can not solve B, and i got the worst standing since i sign in Codeforces... sad
•  » » » 10 days ago, # ^ |   0 :( I am too sad and I can not fall asleep. This contest exposed my problems, I'm an idiot in number theory
•  » » » » 10 days ago, # ^ |   +6 You are very good sir ! I am an idiot in everything ;((((((. I think I will quit cp and hire at foodpanda after i get my bike fixed
 » 10 days ago, # |   0 This round is very nice.But I made a big mistake.I began to think D without reading it carefully!!!When I'm aware of my misunderstanding,it's too late :(
 » 10 days ago, # |   +2 First time I solved pD on div.2!
 » 10 days ago, # | ← Rev. 2 →   +11 Has anyone Accepted the problem-D using Java? I have tried reusing array[1 << 15] but the TL seems too tight.
 » 10 days ago, # |   +1 B is very similar to a USACO problem
•  » » 10 days ago, # ^ |   0 I solved Air Cownditioning for fun a few days back and was able to solve it using that.
 » 10 days ago, # |   +36 Sad for Python users — D was very difficult to complete within the time limit.
•  » » 10 days ago, # ^ |   +11 really sad
•  » » 10 days ago, # ^ |   0 Really unfair!!!
•  » » 10 days ago, # ^ |   +6 The same goes for Java users. Even SecondThread had to switch to C++ to solve D.
 » 10 days ago, # |   0 what's wrong with this approach for D?get winner of 1-2 pair, now we covered participants up to covered=2, then go iterating over next participants from covered+1 to covered*2. if someone won more matches then it's a winner for range from 1 to covered*2. now change covered=covered*2 and repeat until end.somehow I get WA
•  » » 10 days ago, # ^ | ← Rev. 2 →   +1 Won't this need (2^n)-1 queries? That's more than the allowed threshold.
•  » » » 10 days ago, # ^ |   0 hm you are right.anyway I get line for -1 handling so should got RE. will see tests of what I missed
•  » » 10 days ago, # ^ |   0 2^n — 1 > 1/3 * 2^(n + 1)
 » 10 days ago, # |   0 Is the idea for $E$ correct? I got WA2.Create graph with $n$ vertices. Iterate over all $i < j$ and if $a[i][j] < a[j][i]$ add edge with $xor = 1$, meaning, we have to swap either $i$ or $j$ cross, if $a[i][j] > a[j][i]$ add edge with $xor = 0$, meaning, we have to either swap both $i$ and $j$ cross, or not, if $a[i][j] = a[j][i]$, don't add edge.All edges have time of appearing. We have to satisfy the greatest prefix of such edges. Let's do binary search. We fixed subgraph with times $< x$. We have to set to all vertices value 0 or 1, to satisfy all edges' xor. First set all vertices undefined. Iterate over vertices, if we see undefined, set to it any value and do dfs. Dfs only walks on available edges, if it sees undefined neighbour vertice, it sets correct value to it and goes to it. If it sees neighbour vertices, such that is doesn't satisfy edge's xor, then we can't satisfy this prefix of edges.
•  » » 10 days ago, # ^ |   0 Furthermore, seems I solved $D$ in $\frac{1}{3} \cdot 2^n$ queries. What is expected to do with 2 times more queries?
•  » » » 10 days ago, # ^ |   0 I just tested your solution on the sample case and it took 5 queries to answer so I think your answer is NO.
•  » » » » 10 days ago, # ^ |   0 Aw, yes, I had miscalulated)
•  » » 10 days ago, # ^ |   0 Notice that you have to repeatedly do this process as after the greatest prefix and the first "unsatisfiable restriction" , we may still have restrictions that can be satisfied, so we would probably get a $O(mn) = O(n^3)$ solution
•  » » 10 days ago, # ^ |   0 The optimal solution is not neccessaty formed as a prefix.It means you can choose "not add edge i" and "add edge (i+k)" at the same time.
•  » » 10 days ago, # ^ |   0 Take a look at Ticket 15998 from CF Stress for a counter example.
 » 10 days ago, # |   +7 167298607 why this got TLE ????
•  » » 10 days ago, # ^ |   0 Maybe due to "cout.tie(0)"? I'm not sure about that but any other's code doesn't have this line, I can only see "cin.tie(0)".
•  » » » 10 days ago, # ^ |   +5
•  » » 10 days ago, # ^ | ← Rev. 2 →   +8 yes, I am also getting TLE without any good reason also getting WA and I have compared my soln with others who got ac and the soln are the same.
•  » » 10 days ago, # ^ |   0 endl may cause it . try '\n' instead
 » 10 days ago, # |   +42 I have probably used all of my luck for the next few months:
•  » » 10 days ago, # ^ |   0 Wow xD
 » 10 days ago, # |   +1 I loved this contest!
 » 10 days ago, # | ← Rev. 2 →   +8 D was reallllly difficult to complete within the time limit for Python user!!!!!!!!!!!!!!! It's unfair!!!, please rejudge it!!!
•  » » 10 days ago, # ^ |   0 You know that the input and output in Python is quiet slow, even my submission is the same as the tutorial , also got TLE, really unfair!!
•  » » » 10 days ago, # ^ |   0 All the python user that pass the contest, the time is 1980ms+, quiet strict
•  » » 10 days ago, # ^ |   +1 sad, always python users have to wait to increase to the next tier because of the RLE or TLE questions which happens so frequently. It's always absurd optimisations to made it pass. My friend has been waiting one year for expert and he couldn't hit it again today because he TLEd on D and he got a -60 instead, he's 5 stars on codechef (almost 6 stars) and 2450 on LCI really feel you
•  » » » 9 days ago, # ^ |   +1 Thanks for understanding!! Always Python user are not be considered in the CP. in the future if I have the chance to hold a contest, I must set different time limit restrict for different programming language, hope one day it can make true
•  » » » » 9 days ago, # ^ |   0 In leetcode yesterday I made 8 different TLE on O(26*10^5) algorithms.Top down was giving MLE, bottom up with O(n) space was giving TLE as well,I was so surprised that I submitted the same code multiple times, then finally optimised it to O(26) space and it passed
•  » » » » » 8 days ago, # ^ |   0 Once, i took part in the LeetCode weekly contest and met the same thing, really sad
 » 10 days ago, # |   +9 For D Problem, I applied the same logic as mentioned in the editorial, but i am getting Wrong Answer. I have tried my best but I am not able to figure out the mistake. Can someone please help me to figure out the mistake? 167302006
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 same bro i am also not able to find my mistake.
•  » » 10 days ago, # ^ |   0 I'm not sure whether I understand your code correctly, but I think that in a scenario where res is not 0, you have to move 2 guys to next level, but you're moving only one
•  » » » 10 days ago, # ^ | ← Rev. 2 →   +4 Yes,I think I am doing that only. For 4 players, I am always querying for the 1st and 4th one. if(res == 0): move {2nd, 3rd} up else if(res == 1) move {1st, 3rd} up else move {2nd, 4th} up Please correct in case there is anything wrong in this. 
•  » » » » 10 days ago, # ^ |   0 Yes its true, but this will make queries more than it's allowed
•  » » » » » 10 days ago, # ^ |   0 Actually, it won't exceed the queries. The Logic was correct, but there was a slight mistake in the implementation.The order in which I am pushing in a step will also matter, just made this change and I got an AC. 167311506
•  » » 10 days ago, # ^ |   0 Take a look at Ticket 16001 from CF Stress for a counter example.
•  » » » 10 days ago, # ^ |   0 Thank you so much :)
 » 10 days ago, # |   +5 167304705 why is this got TLE???
•  » » 10 days ago, # ^ |   0 Logarithmic factor maybe??
•  » » » 10 days ago, # ^ | ← Rev. 2 →   +1 my solution is (2^n*(log(2^n))2^17=1e51e5*17=2e6It must be enough for 2 seconds
•  » » » » 10 days ago, # ^ |   0 I used a vector so I about saved the logarithmic factor. But my code still took ~800ms
•  » » 10 days ago, # ^ |   -10 e.erase(*it2);You actually do n times linear operation on the array, each one works in O(n), so that is O(n^2)In such algorithm it is better to copy the data in each round, then you copy n/2 elements into a new array, which makes all in all only n single element copy operations.
•  » » » 10 days ago, # ^ |   +4 He is using sets..
•  » » » » 10 days ago, # ^ |   -9 Oups, didn't see that :/
 » 10 days ago, # |   0 what is wrong in my approach for problem B https://codeforces.com/contest/1713/submission/167293528 Approach inserted all the elements of the array into the set if the size of set is equal to the size of array this means that the all the permutations have cost greater or equal to array therefore YESif not then i m checking the position of duplicate elements if all duplicate elements are adjacent this means the permutations of it has greater cost so the answer is yes otherwise the answer is no.
•  » » 10 days ago, # ^ |   0 Take a look at Ticket 16000 from CF Stress for a counter example.
•  » » 10 days ago, # ^ |   0 The NO-instances are not characterized by duplicate elements. But rather, they are characterized by the transition from decreasing to increasing. For example, the array [2, 1, 3] should output "NO" (it requires 4 operations, whereas [1, 2, 3] only requires 3 operations), even though there are no duplicates. The issue with decreasing->increasing is that the two sides cannot be decremented at the same time once the center becomes 0, whereas a sorted/reverse-sorted/increasing->decreasing array can ensure that every operation hits all non-zero elements at once.
 » 10 days ago, # |   0 Thanks for the great contest :) !!!! Really loved all the problems and especially problem D And a great rating increment :)
 » 10 days ago, # |   0 A great contest ! Kudos to the problem setters and testers ^_^
 » 10 days ago, # |   0 Good contest all problems are nicely framed.
 » 10 days ago, # |   +8 Great problems. To be fair, I raged pretty hard about the time limit being way too tight on D (or there being way too many queries for an interactive problem), but other than that, great set :)Screencast and solutions to A-D will be available on my youtube channel as soon as youtube finishes process it.
•  » » 10 days ago, # ^ | ← Rev. 3 →   0 My logic is also the same as that of yours for D. Can you tell, what is my mistake? https://codeforces.com/contest/1713/submission/167288666
•  » » » 10 days ago, # ^ |   0 you made queries more than it's allowed. here is my submission in the last minute :) 167303592
•  » » » » 10 days ago, # ^ |   0 You can check my queries are within the limit and I have also compared my solution with the one who got ac. find no such difference.
•  » » » 10 days ago, # ^ |   0 Take a look at Ticket 16002 from CF Stress for a counter example.
•  » » 10 days ago, # ^ |   0 I have a doubt. In problem D, can we have 2 winners with same score? Did I miss something? Is it written anywhere that the winner's score is unique?Consider the following example testcase: // [0, 0, 3, 3, 4, 1, 4, 2]
•  » » » 10 days ago, # ^ | ← Rev. 2 →   0 how can the players 1 and 2 have 0 wins if the play against each other in the 1st match?.. same as players 3 and 4
 » 10 days ago, # |   0 the pretest of B is shit!
•  » » 10 days ago, # ^ |   +17 Apparently so was your solution...
•  » » » 10 days ago, # ^ |   0 So was the other 100+ people who fsted in B.Our solution are all shits.Cool.
•  » » » 10 days ago, # ^ |   0 Didn't you realized that we can pass the pretest without using long long?
•  » » » » 9 days ago, # ^ |   +8 Didn't you realize that we can pass the system tests without using long longs?
•  » » » » » 9 days ago, # ^ |   0 lol you're malding so bad because you realized he's right. thats an L right there buddy
 » 10 days ago, # |   0 knew C would be hard(er)/speedforces... knew I wasn't in my best condition (opted in out of some weird notion of 'making up' for sleeping through atcoder)yolo'd anyway, tried to rush, stumbled on A and B instead...had all possible answers of C for n<=12 pretty quickly afterward, but not enough time to find a winner out of various guesses at patterns/splits/recurrences...at least I didn't have to deal with D, so there's that... OH well, back below my april fools peak rating I go...
 » 10 days ago, # |   0 In problem B there should have been a pretest where you needed to use long long int!
•  » » 10 days ago, # ^ |   0 What? You don't need to use long long int?I easy solved it just with ints: 167240602.
•  » » » 10 days ago, # ^ |   0 There is a solution where participants want to check if $\sum(max(0, a[i] - a[i-1]))$ is equal to $max(a[i])$. In fact, this is also a correct solution but it may require a $sum$ variable to store big number which can only fit $long \ long \ int$.
•  » » 10 days ago, # ^ |   0 Check this out: 167248132 It's a simple increasing decreasing logic
 » 10 days ago, # | ← Rev. 2 →   +10 Balanced contest! Edit: I got expert back!
 » 10 days ago, # |   0 In problem D, if n=6, can we make 43 queries?As, (2 ^ 7)/3 is around 42.67
•  » » 10 days ago, # ^ |   0 ceil.
•  » » » 10 days ago, # ^ |   0 Then why it is giving me wrong answer on test 3? (Showing "Too many queries.")https://codeforces.com/contest/1713/submission/167314753
•  » » » » 10 days ago, # ^ |   0 It shows your first 43 queries. You probably make more.
•  » » » » 10 days ago, # ^ |   +1 I'm not sure but I think v.size() can be 1. (not 2)
•  » » » » » 10 days ago, # ^ |   +3 Thanks !!Yeah, v.size() will be equal to 1 when n is even, I didn't notice that. Got AC.
•  » » 10 days ago, # ^ |   0 Yea since its ceil(2^n+1 / 3)
•  » » » 10 days ago, # ^ |   0 Then why it is giving me wrong answer on test 3? (Showing "Too many queries.")https://codeforces.com/contest/1713/submission/167314753
 » 10 days ago, # | ← Rev. 2 →   0 My solution of problem B seems to be right, but it gives error on token 78 of test 2. How do I view the test in their full length? (My solution)
•  » » 9 days ago, # ^ |   0 Take a look at Ticket 16006 from CF Stress for a counter example.
 » 10 days ago, # | ← Rev. 4 →   0 can someone tell me what is wrong with my B solution: https://codeforces.com/contest/1713/submission/167256508 . i've been trying to figure it out for the past 3 hours :)
•  » » 10 days ago, # ^ |   0 Try n < 3
•  » » » 10 days ago, # ^ |   0 NOOOOOOO
•  » » 10 days ago, # ^ | ← Rev. 3 →   0 your code for 1 2 2 2 prints two YES. Add a continue in the first if block
•  » » » 10 days ago, # ^ |   0 :(
 » 10 days ago, # |   +16 The best contest of 2022! Orz thanhchauns2
 » 10 days ago, # |   0 Interesting E. I come up with it just after the contest finished:(
 » 9 days ago, # |   +4 Any particular reason for C being of 1750 points?, I think it was not that hard and could have been of 1250 or 1500 points.
•  » » 9 days ago, # ^ |   +1 We expected it could be a hard D2C, and turned out to be really easy.
 » 9 days ago, # |   0 Hi everybody! Yesterday I passed this interesting contest, but something confused me. Why were my two previous attempts ignored on the third problem? And because of this, I lost +100 points.Please answer!
•  » » 9 days ago, # ^ | ← Rev. 2 →   0 After you get AC, for every resubmission of that problem you will lose 50 points and the pervious submissions of the problem will be skipped.
 » 9 days ago, # |   0 Really good questions. Thanks for the contest
 » 9 days ago, # |   0 Use greedy strategy, problem D could be solved within 2^(n-1) queries? this submission https://codeforces.com/contest/1713/submission/167314546 assert queries * 2 less or equal 2^n
 » 9 days ago, # |   -14
 » 9 days ago, # | ← Rev. 2 →   0 In problem D, In the test case given, can't 2 win the contest?1 2 3 4 5 6 7 82 4 5 72 7 2The final win array becomes = [0, 3, 0, 1, 1, 0, 2, 0] Can someone explain this.... any point I'm missing?
•  » » 9 days ago, # ^ |   0 Yes, it can. But it gives the right answer 7, so it is accepted, even though its logic may be nonsense at all, i.e. the tester only cares about the final answer, rather than the logic behind.
•  » » » 9 days ago, # ^ |   0 you should definitely care about the logic behind it, otherwise you will never understand how CP works and solve problems.
 » 9 days ago, # |   0 wish there were stronger pretests :c
 » 9 days ago, # |   0 Nice
 » 8 days ago, # |   +9 Expected Brood War themed problems.thanhchauns2 didn't deliver.As a consequence, I had a terrible performance. Lowest rating in almost 2 years :(
•  » » 8 days ago, # ^ |   +8 Unfortunately, all problems with Brood War theme is either saved or removed. The set is entirely different from the first. I feel so sorry about this.
 » 2 days ago, # |   0 Shit interactive problem