### Igorfardoc's blog

By Igorfardoc, history, 4 months ago,

#### Hi, Codeforces!

Vladithur and I are pleased to invite you to our Codeforces Round #769 (Div. 2), which will be held on Jan/30/2022 17:35 (Moscow time). This round will be rated for participants with rating lower than 2100.

We would like to express our great gratitude to:

You will have 2 hours to solve 5 problems, one of which is divided into two subtasks.

The scoring distribution is 500 — 1000 — 1500 — 2000 — (1500 — 1500)

We have tried to make clear statements and strong pretests for the problems and hope you will have fun and increase your rating!

Good luck!

Also, we would like to start the trend of evaluating the round's problems. We think it will give valuable feedback to authors and make future contests better. So please, vote for each problem after the round's end.

Problem A
Problem B
Problem C
Problem D
Problem E1
Problem E2

UPD: Editorial is here.

UPD2: Congratulations to the winners!

Div. 1 + Div. 2:

Div. 2:

• +394

 » 4 months ago, # |   +73 As a tester, I like all problems!
•  » » 4 months ago, # ^ | ← Rev. 3 →   -43 New alternating thread free contribution ++
•  » » » 4 months ago, # ^ |   +18 Soon, the absolute value of your contribution gonna pass monogon's.
 » 4 months ago, # |   +61 I can say that all the problems are very interesting to solve and the authors have done a great job inventing them.
 » 4 months ago, # | ← Rev. 2 →   +53 By the way, does dkirienko help you?If the answer is "yes" — is it meaning that participant can solve all problems using Python? :) SpoilerP.S. Sorry for Russian, the meaning is that Python is excellent :)
•  » » 4 months ago, # ^ |   +57 Even though the answer is "no", all problems can be solved using Python!
 » 4 months ago, # |   +46 Is the round going to be Starcraft-themed? :P
•  » » 4 months ago, # ^ |   +24 Unfortunately, no :)
 » 4 months ago, # |   +24 Hope all of you will get good rating after this round .
•  » » 4 months ago, # ^ |   +26 Of course we have 7"69" : )
•  » » » 4 months ago, # ^ |   +8 By the way, 769 is a prime number. Hope that means prime quality problems ;)
 » 4 months ago, # |   +78 Love the idea of per-problem feedback prompts! Although I wonder why people already started voting — are those testers or trolls? :P
•  » » 4 months ago, # ^ |   +38 Some of them are testers, and some of them are trolls, I think. But, I really hope they will revote after the round.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +96 I think it would be better if you have given this feedback voting option in editorial blog instead of announcement blog, Anyway it's a great initiative.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +20 I believe there are people like me who rarely open editorials.They should've just added the voting section after the end of the contest by editing the blog.
•  » » » 4 months ago, # ^ |   +7 And some of them — I believe — has a superpower to foresee the future
•  » » 4 months ago, # ^ |   +17 trollforces
 » 4 months ago, # | ← Rev. 5 →   +24 So please, vote for each problem after the round's end. you should have waited round to end for putting votes, now alot people will vote but forget to re-vote
 » 4 months ago, # | ← Rev. 2 →   +108 The people who vote for the Bad problem even before they see the problem are the same people who always ruin beautiful things!
•  » » 4 months ago, # ^ |   0 I think hey are just testing the new Codeforces feature. And that's just human nature to click here and there and move on.
•  » » 4 months ago, # ^ | ← Rev. 2 →   -24 Chup Mulle tumhari kaum terrorist hai bsdk you ruin and kill people Mullah Bc
 » 4 months ago, # |   +16 It is sad to see that some people have already voted "a bad problem" . Anyway, I wish everyone good luck for the contest!
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 true brother
 » 4 months ago, # |   +56 As a tester I think there should be a section to ask for contribution.
 » 4 months ago, # |   -18 Hello, I am a beginner who recently joined codeforces. Will there be a division 3 contest anytime soon? Thanks.
•  » » 4 months ago, # ^ |   +1 You should try participating in div 2 as well. Because div3 is a rarer thing than div2 :)
•  » » 4 months ago, # ^ |   +1 This is a normal and reasonable question, and I can't understand why there are so many downvotes. I doubt some users just downvote it blindly because there are already some downvotes and it's tempting to add more.
 » 4 months ago, # |   +16 I don't understand why is it possible to evaluate problems before the round, it would be good update later , but why now?
•  » » 4 months ago, # ^ | ← Rev. 6 →   +19 So, may be it is a good idea, but I actually do not see much of a difference, because there will always be trolls, and you will not get rid of them by moving the evaluation to the update or to the editorial. As for decent people, I think they will revote after the round, if at first they chose the wrong option.
 » 4 months ago, # | ← Rev. 2 →   -21
 » 4 months ago, # |   +18 nobody reads tags expect me
•  » » 4 months ago, # ^ |   +8 Hey! I do!
•  » » 4 months ago, # ^ |   0 except*
•  » » 4 months ago, # ^ |   0 everyone read tags
 » 4 months ago, # |   +32 As a tester, I do read tags!
 » 4 months ago, # | ← Rev. 2 →   +16 DELETED
•  » » 4 months ago, # ^ |   +28 I think it doesn't. This contest is held on 30/1 14:35 UTC, while COCI contest #4 is held on 29/1 14:00 UTC. Correct me if I'm wrong.
•  » » » 4 months ago, # ^ |   +13 oh sorry I misread the time thanks for correction
 » 4 months ago, # |   +7 Hope to get +69.
 » 4 months ago, # |   0 What about The people who vote for the Bad problem even before they see the problem!! what are u doing?!
•  » » 4 months ago, # ^ |   0 what if these votes came from the testers?
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +12 man just count the number of testers and votes. ez math bro. Also testers should not vote. they give the writers a direct feedback.
 » 4 months ago, # |   0 I guess it's time to be attentive,or otherwise my rating will stagger
 » 4 months ago, # |   +1 I appreciate the idea of collecting the feedback regarding individual problems. But I'm getting the feel that this way of collecting the feedback might lead to a lot of false statistics. The round hasn't started yet and already you can realize some surprising data.
•  » » 4 months ago, # ^ |   +10 I agree that it may collect false statistics, but regardless, it's a good step forward. Sometimes there are just bad problems, you can't deny that. And, I appreciate the effort of the authors to step forward and give chance for feedback. This says that the authors are careful and I hope we'll finally have some good problems, not just edge-case work.
•  » » » 4 months ago, # ^ |   +4 Indeed it is a pretty nice initiative to provide a platform for some constructive feedback wrt to problem set. I'm just suggesting some points of improvement to ensure some sort of validity in the poll results. Like opening the poll after the contest ends to begin with.
 » 4 months ago, # |   +58
 » 4 months ago, # |   +71 I suggest putting the voting buttons in the editorial. People should provide feedback only after they have seen the solution.
•  » » 4 months ago, # ^ |   0 I think people should only get to vote after they've had to work through the problem spec and implement successfully. It seems to me difficult to vote on a problem that one has not personally tried.
•  » » 4 months ago, # ^ |   +33 After being inspired by this I think we will have a huge benefit if we can vote for every single problem after we solved it (maybe there can be some rating restriction for example rating >= 1400). Thus, every problem except its rating difficulty will also have a number that corresponds to its pleasure to be solved and whether it's a good or a bad problem. I think this way both problem solvers and authors can take advantage of this.
•  » » 4 months ago, # ^ |   -11 Or maybe on the question itself. and You can only vote after solving the question. that may be better way Just a suggestion
 » 4 months ago, # |   0 This voting system might be helpful for solvers to get rid of some problems with stupid test cases. Nice
 » 4 months ago, # | ← Rev. 2 →   0 Voting on problems is a great idea and one that's long overdue. The voting mechanism should be incorporated directly into the contest pages instead of in a blogpost some may skip over. Also voting should only be available to those who go through the effort of figuring out the problem and implementing it, having dealt with edge cases and test case quality.
 » 4 months ago, # |   0 Great initiative!
 » 4 months ago, # | ← Rev. 2 →   0 when the contest hasn't even happened yet and the A problem already has 200 "good problem" votes
•  » » 4 months ago, # ^ |   0 Cuz it just has to be good
 » 4 months ago, # |   +3 new challenge for all contestants........good luck
 » 4 months ago, # |   +8 Interesting delete line.
 » 4 months ago, # |   0 Which is more easy problem A or problem E?I am new on codeforces. Plz tell me.
•  » » 4 months ago, # ^ |   +36 A
•  » » 4 months ago, # ^ |   0 E
•  » » » 4 months ago, # ^ |   0 Hey you, don't deceive people!
•  » » 4 months ago, # ^ |   +6 A
 » 4 months ago, # |   +6 Good luck!
 » 4 months ago, # |   0 Very excited for today's contest hope I will reach to pupil. HaHa!!
 » 4 months ago, # | ← Rev. 2 →   0 Wow! The authors of the round have avatars from Starcraft 2. We should participate!
 » 4 months ago, # |   0 Wowwwwwwwwwwwwwwwwww how can you add the likes?
•  » » 4 months ago, # ^ |   0 Here is a post from MikeMirzayanov.
 » 4 months ago, # |   -32 as a !tester , i am here to farm contribution.
•  » » 4 months ago, # ^ |   +10 You didn't clarify positive or negative contribution :)
 » 4 months ago, # |   0 I am not sure the categories for evaluating problems are right. Quite often the problems I fail to solve (or fail to solve without reading the editorial) are the most interesting (best?) problems.
 » 4 months ago, # |   -28 говно у вас идея с трендами
 » 4 months ago, # |   0 Is codeforces is crashing for others too?
•  » » 4 months ago, # ^ |   0 Occasionally
•  » » » 4 months ago, # ^ |   0 Hoping occasionally do not become frequently during contest.
 » 4 months ago, # |   0 Hoping for a contest which do not contain problems like previous Div2 C
•  » » 4 months ago, # ^ |   0 ah shit! here we go again
 » 4 months ago, # |   +13 Good timing of the Australian Open Final, has ended 20 minutes before the contest.
•  » » 4 months ago, # ^ |   +3 Unfortunatly, our compatriot Daniil Medvedev lose :(
 » 4 months ago, # |   +8 Good luck everyone
 » 4 months ago, # |   0 ALL the best guys..
 » 4 months ago, # |   +32 bitforces.
 » 4 months ago, # |   0 If I do multiple submissions, and all are passed then my score depends on my first submission or last submission
•  » » 4 months ago, # ^ |   +3 On the last submission that has passed pretests.
•  » » » 4 months ago, # ^ |   +1 Thanks
 » 4 months ago, # |   0 great round, loved the problems!
 » 4 months ago, # |   +4 Hint for task C?
•  » » 4 months ago, # ^ | ← Rev. 2 →   +8 SpoilerThere's no point using BIT OR operation more than once.
 » 4 months ago, # |   +6 I have no idea why my solution to B passed pretests :OO
 » 4 months ago, # |   +12 The fact that C=E1 in scoring distribution is strange for me.
 » 4 months ago, # | ← Rev. 2 →   +7 back to mathforces :(also thanks for very not misleading scoring of the last task
•  » » 4 months ago, # ^ |   +15 More like bitforces?
•  » » » 4 months ago, # ^ |   0 math includes bit and D was math also
•  » » » » 4 months ago, # ^ |   +8 I consider them as very different things and there's very little math in D IMO.
 » 4 months ago, # |   +6 Is C Ad-Hoc?
•  » » 4 months ago, # ^ |   +21 C is cancer
 » 4 months ago, # | ← Rev. 3 →   -24 DELETED
•  » » 4 months ago, # ^ | ← Rev. 3 →   +50 Which of the problems have endless corner cases? A: The edge cases are literally in the samples. B: No edges cases needed here since (n — 1) ^ largest bit always works. C: Not sure if there is a casework soln to this, but my solution just iterates on the value the final element will take and then you just need to check the smallest value $\geq a$ that is a submask of this element. I don't think anything is casework heavy here. D: My solution uses one nice observation + range queries, maybe the other solution is case work heavy which is unfortunate since range query structures shouldn't be required for a Div2D. E1: No case work here, just find distances and calculate the answer using a weird sort of prefix maximums / decreasing suffix maximum. E2: No clue, didn't solve it, but I doubt you're referring to this problem.
•  » » » 4 months ago, # ^ |   +3 There could be many different solutions for a single problem. If one takes the wrong direction, then that person might be stuck in many corner cases. I'm initially referring to my case solution for C but I'm also talking about things generally.
•  » » » » 4 months ago, # ^ |   +1 This is interesting. One of the things I hate about myself is that I find it hard to discard an idea, so I end up checking a lot of cases and overcomplicating problems unnecessarily and most of the time I will fail anyway. Checking the straightforward editorial for C after struggling is beautiful. I don't think the 4 cases about the bit values is something to be considered painful casework. My conclusion is that, most of the time, you should blame yourself. Writing simple solutions is part of practice.
•  » » » » » 4 months ago, # ^ |   +3 Yes, you are absolutely right. It took me some time to realize the importance of avoiding getting stuck in one direction. In most cases the problem should have a clean solution which doesn't require too many cases.
•  » » » 4 months ago, # ^ |   +29 Why is range queries bad for div2D?
 » 4 months ago, # |   +12 How to solve D without range query data structures? Btw I really like the monotonic observation. Its such an obvious fact that as we increase the number of elements the gcd will not increase, but it really did not strike me in relation to the problem.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +16 I kept a multiset of ban positions for each indices. For instance, a suffix gcd equals to $3$ at position $5$ bans position $7$.When we actually update a gcd, we maintain the set. Such updates will not be many as each time at least one of the gcds lose a factor.
•  » » 4 months ago, # ^ |   +7 I think the key observation is that given a[i], there can be at most around log2(a[i]) distinct gcds among gcd(a[i]), gcd(a[i — 1], a[i]), ..., gcd(a[0], ..., a[i]).So, combined with the monotonic observation, it's fine to maintain a partitioning of [0, i] into intervals, one for each distinct gcd. So in log2(i) time you can find the earliest position j such that gcd(a[j], ..., a[i]) is equal to its length. I guess you could also binary search but that's unnecessary.
•  » » » 4 months ago, # ^ |   0 Could you elaborate on how you would generate and maintain such a partitioning though? I can think of a way to do this in $O(n \cdot \sqrt{max(a)} + n \cdot \log(max(a)) \cdot \log\log(max(a)))$ but this is too slow. I basically can't figure out how to eliminate factorization for newly added factors from $a_i$.
•  » » » » 4 months ago, # ^ |   +8 As there are always $O(\log{n})$ entries, simple brute force takes $O(n\log^2{n})$. Code
•  » » » » » 4 months ago, # ^ |   0 Oops, I somehow missed the obvious point that similar suffixes cannot become different again, so just directly updating them each turn works.Thanks for the help.
•  » » » » 4 months ago, # ^ |   +8 Here is a correct submission that uses the idea above: https://codeforces.com/contest/1632/submission/144586184
•  » » 4 months ago, # ^ |   0 Sqrt decomp go brr
 » 4 months ago, # |   +11 There were so many submissions by unrated accounts around the same time. Were the solutions of first 4 problem leaked or something ?
 » 4 months ago, # |   +9 bit operation contest. lacked variety of problems...
•  » » 4 months ago, # ^ |   +66 The contest was a Bit-difficult
 » 4 months ago, # |   +6 I love problem D Spoilerthe idea of binary search was very neat!
•  » » 4 months ago, # ^ |   0 Realized just after the contest that, replacing a for loop with while(bs) will work like magicNice problem :)
 » 4 months ago, # |   +2 bitforces
 » 4 months ago, # | ← Rev. 2 →   0 Thanks for lightning editorial :) problem D was much interesting ,as it was a mixture of binary search with segment tree.
 » 4 months ago, # |   0 Very cool contest and interesting tasks!!!
 » 4 months ago, # | ← Rev. 2 →   0 Read at this bc I can't delete this comment: https://codeforces.com/blog/entry/99442#comment-882354
 » 4 months ago, # |   0 why O(n*log(n)*log(n)*log(A)) AC in D ?? 144574263
 » 4 months ago, # | ← Rev. 4 →   +20 More cheat today.we need to ban the cheat accounts,this kind of account makes imfair to cpWhat's more , I find that most of accounts which submitted their code in 01:59 of E were suspect of cheat.
•  » » 4 months ago, # ^ | ← Rev. 8 →   +16 some similar submissions I found for reference all of them entered the top 50, and some of them have cheated for three contests and still do not get bannededit: all above get banned now so I am going to post morethere should be a button for reporting cheat codes
•  » » 4 months ago, # ^ |   0 How do you know that he is cheating ?
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 They have a bunch of junk variables that do nothing as a way to circumvent being caught by CF's anti-cheating algorithms. I'm not sure of the purpose, but my guess is they plan on selling the accounts to people who want to promote their (fake) CF rank to employers.
 » 4 months ago, # |   0 How is this wrong for E1? I maintained an Euler tour and segment tree. If I want to connect node 1 to node x. So max distance here will be max((max distance in the subtree of node x — dis[x] + i), max in the remaining tree excluding the subtree). Finally I take min ans for each x. Can someone pls give a counter example where this fails?
•  » » 4 months ago, # ^ |   +20 Here is a case where your code will fail(if I have understood it correctly)91 22 33 44 55 66 74 88 9The correct answer for x = 1 is 3, but by yout logic it's 4
•  » » » 4 months ago, # ^ |   +5 Thanks for the test case
 » 4 months ago, # |   -7 Is this even possible to create a solution for D that exceeds time limit?
•  » » 4 months ago, # ^ |   0 I guess add all primes in the array
 » 4 months ago, # |   0 In question B ,if we take input 6,then according to editorial solution answer will be {3 2 1 0 4 5} but the optimal ans is {2 3 1 0 4 5}.
•  » » 4 months ago, # ^ |   +6 The problem asks us to minimize the maximum xor among pairs of adjacent elements. Both 3 2 1 0 4 5 and 2 3 1 0 4 5 have the same maximum xor of 0 ^ 4 = 4, so I don't think it really matters.
•  » » » 4 months ago, # ^ |   0 Got it, Thanks
 » 4 months ago, # |   0 Good contest
 » 4 months ago, # |   -9 You know what That's not the first time when system telling me that my code is same with another's one For the God's sake i don't even know what Ideone or something is, cause i solve problems on codeforces to practice, and i'am not going to steal any code. You know there are billion's of programmers and i don't realy think that every of them have different ideas.
 » 4 months ago, # |   +4 During the contest when I was solving problem c, I got the intuition that we can solve this in a total of three steps in these sequence 1. either increase a or b by some amount. 2. take the OR. 3. increase the b to match the value with the second step value. Although I was not able to prove it during the contest. I submitted it just based on some gut feeling. So I just want to know is this the case with other people too? or do you guys first prove your solution and then submit it?
•  » » 4 months ago, # ^ |   0 I think, these are presumptions, which we (unknowingly) make based on the problem complexity declared in scoring before the contest.
 » 4 months ago, # | ← Rev. 2 →   +5 MikeMirzayanov I'm not really sure where to put this, but I received these two messages:Attention!Your solution 144568353 for the problem 1632D significantly coincides with solutions Weierstrass/144555583, codebuster_10/144561876, 876pol/144568353, Winterfrost/144569022, xiaoququsd/144572170, Kanheyalal/144572862, dimss/144575074, Kawaii/144576113, matouzouken/144576356. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.Attention!Your solution 144557728 for the problem 1632C significantly coincides with solutions Weierstrass/144543081, codebuster_10/144548751, Kawaii/144549603, matouzouken/144551794, Winterfrost/144556519, 876pol/144557728, xiaoququsd/144562448, dimss/144563984, Kanheyalal/144564250. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.I wrote the code for both these submissions locally on vscode and I don't know any of the people mentioned in the message. Also, the codes don't seem that similar in the first place.However, just to be sure, the code for 1632C is fairly short and is just a false positive. I had also submitted a couple WA submissions before this one, so its not like I copied it off of someone.I got the code for the sparse table in 1632D from https://brilliant.org/wiki/sparse-table/, and the rest of the code is also short and is just two pointers.(also, sorry for tagging you)
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Why their is positive Plag check, submissions are not even similar at all ? MikeMirzayanov Please see to it. I ran both my submissions locally and use my own template, any of the given submissions does not seem to be similar to mine at all.
•  » » 4 months ago, # ^ |   0 I also received this message, and I think our codes are completely different (I even didn't use any existing templates).
 » 4 months ago, # |   +4 wow how many cheaters were removed? I should have got only +7 delta at the end of contest but now got +22
•  » » 4 months ago, # ^ |   0 SO CRAZY that one out of four accounts were cheaters in last round.
•  » » 4 months ago, # ^ |   0 I think that a good way to anti the cheater is to solve the problem faster than them. So whether they are cheating is unmeaningful.
 » 4 months ago, # |   0 bit are always so ingenious……
 » 4 months ago, # |   0 Number theory all around ! Mathforces T_T.
 » 4 months ago, # |   0 In the third problem, isn't b' the same as a'|b. But, it doesn't give me the correct solution. If anyone could explain.
•  » » 4 months ago, # ^ |   0 Consider a'=5 and b=10, taking b'=12 would be optimal as the value of a'|b' will be 13. But if you take b'=10, the value of a'|b' will be 15
 » 4 months ago, # |   0 Hi I am a newbie and would appreciate some assistance here. My submission fails with verdict Wrong answer on test 2. However when I click on my submission number I can only see test case 1 which is succeeding. My question is how can I see test case 2 ?
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 During the competition you will not be able to see private test cases. However, after the competition, you can resubmit your code and you will be allowed to see them.
 » 4 months ago, # |   0 I have a trouble understanding problem D example test case 3: input 7 2 12 4 8 18 3 6 output 0 1 1 1 2 2 2 I expect that for prefix (2 12 4 8) we will need only 2 replacements, but it's 1 according to exampleSpecifically, I see two separate pairs: GCD(2, 12) = 2 and GCD(4, 8) = 2. I expect that we will need to replace one value in each pairCan you help me?
•  » » 4 months ago, # ^ |   +1 GCD(4, 8) = 4. And we can change this prefix into 2 5 4 8.
 » 3 months ago, # |   0 Hi MikeMirzayanov, My id has been hacked and someone has submitted fraudulent copied solutions from my account. They have even changed the email address of the account to something random and I can't even recover it. I am sending this message from an existing session. Dm'ed you the details. Please help.