### Aris's blog

By Aris, 13 months ago,

Hello! Codeforces Round #764 (Div. 3) will start at Jan/10/2022 17:35 (Moscow time). You will be offered 7-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 7-8 problems and 2 hours and 15 minutes to solve them. One of the problems in this round is interactive. Don't forget to read the guide on interactive problems.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them)
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University team: MikeMirzayanov, MisterGu, myav, Gol_D, Aris, DmitriyOwlet and Vladosiya.

We would like to thank: itohdak, Yogi79, smtcoder, Ra16bit, Tlatoani, nigus, MrDindows, leaf1415, Kniaz, Alireza, mini4141, Jostic11, BitHashTech, An_yujin, oversolver и sodafago for testing the contest and valuable feedback. List of testers will be updated.

Good luck!

UPD: Here is a photo of our team answering your questions during the round:

UPD 2: Editorial

• +704

| Write comment?
 » 13 months ago, # |   +26 I wish every gray, become green! Good luck!
•  » » 13 months ago, # ^ |   +18 Can you please also wish for green to become cyan.
•  » » 13 months ago, # ^ |   +32 I wish every unrated become gray :heart_eyes:
•  » » 13 months ago, # ^ |   +13 The WA become AC!
•  » » » 13 months ago, # ^ |   +6 Sorry, system testing doesn't work like that
•  » » 13 months ago, # ^ |   0 thanks
•  » » 13 months ago, # ^ |   0 Sorry but I had different plans.
 » 13 months ago, # |   +10 Excited to participate in the first Div. 3 round of $2022$ and my first unrated round, yay!
•  » » 13 months ago, # ^ |   +7 Me too !
 » 13 months ago, # |   +3 Interactive problems in div.3 round are epic.Look forward to this contest!
 » 13 months ago, # | ← Rev. 5 →   -30 I hate Div 3 so boring
•  » » 13 months ago, # ^ |   +10 Grandmasters find Div.2 boring ...
 » 13 months ago, # |   +17 I wish my cyan color become blue!
•  » » 13 months ago, # ^ |   +6 You are blue already
•  » » » 13 months ago, # ^ |   +1 Nope , It's a Christmas effect :)
 » 13 months ago, # |   +10 Another permutation or binary search on problem C
 » 13 months ago, # |   +10 Will there be div 4 contests in the near future
 » 13 months ago, # |   -16 I tried solving a few interactive problems but got the idle limit exceeded! how to solve them?
•  » » 13 months ago, # ^ |   +1 I don't think there is any interactive problem that doesn't warn about flushing the output. Read the problem statement carefully from now on.
•  » » 13 months ago, # ^ |   0 There is a link in the announcement of the round about interactive problems
 » 13 months ago, # |   -14 Oh,no. I am very unhappy, because I will go to school on Tuesday. I want to have more rated, but I really won't have time. ):
•  » » 13 months ago, # ^ |   0 me too.. i will have online classes :)
•  » » » 13 months ago, # ^ |   +6 comeon dude, you gonna attend an online class.
•  » » 11 months ago, # ^ |   0 I don't even know there was a thing called coding when i'am in school
 » 13 months ago, # |   +1 The status of the problem I submitted 40 mins ago is still in queue. Is the same happening with all of you?
 » 13 months ago, # |   0 So excited to see blogs on Codeforces( this the second one). I haven't seen them for a year. (just a joke)
 » 13 months ago, # |   +1 I wish my cyan color become blue!
 » 13 months ago, # |   +2 I hope you done the best! Good luck for everyone!
 » 13 months ago, # |   0 Here we go again...............
 » 13 months ago, # |   0 First Div. 3 round in 2022!
 » 13 months ago, # |   +1 All the best :) everyone, stay hydrated.
 » 13 months ago, # |   0 I hope I do good ;)
 » 13 months ago, # | ← Rev. 2 →   0 wow you guys are having fun (photo)
 » 13 months ago, # |   +10 Thank you for this amazing round!
 » 13 months ago, # | ← Rev. 2 →   +70 G has more submissions let's solve it.can't solve G -> move to Fcan't solve F -> move to Ecan't solve E -> back to G ;_;
 » 13 months ago, # |   0 In the photo are all of these guys also the setters of this round or just for answering the question asked by everyone?
•  » » 13 months ago, # ^ |   +38 All the people in the photo are also the authors of the round
•  » » » 13 months ago, # ^ |   +2 And which is you if it s not a secret
•  » » » » 13 months ago, # ^ |   +30 I'm on the left
 » 13 months ago, # |   0 How to solve problem D, I just thought of putting all the occurances of each letter into a set , & do the process optimally for k times , can someone help me, I know my solution will fail at cases like aaaaaaa, k = 2.. :
•  » » 13 months ago, # ^ |   0 Hint — Binary search for the answer
•  » » » 13 months ago, # ^ |   +16 Binary Search is not necessary.Count freq of each character for i=1:26if (freq[i]%2==1) // one of the occurrences of this character can be part of a palindrome at the middle positionthe rest sigma(freq[i]/2) pairs of characters can be splitted evenly between each of the k palindromes.https://codeforces.com/contest/1624/submission/142239619
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Can be also solved greedily.Count occurences of letters in original string and count number of singles and doubles.(doubles — how many pairs of letters there are, singles — number of letters minus doubles * 2).Knowing singles and doubles values you can calculate solution.
•  » » 13 months ago, # ^ |   0 There's no need for maintaining sets, you only need the counts of the possible number of pairs you can form for all the letters. This divided and then multiplied by k (integer division) will give the number of pairs that will be assigned to each color. If there are still other letters which have not been selected in any of the selected pairs yet, you can add 1 such char to the string of each color (eg: cac). My Submission.
 » 13 months ago, # | ← Rev. 2 →   0 DAAAMN, I had so much fun solving E (although I didn't quite finish it).I thought that out of all solutions we were supposed to pick one that has least segments — which imo is even better problem (not sure if harder then original though).
•  » » 13 months ago, # ^ |   0 Actually my solution to that problems is O(n * m * n). Does anybody know how to solve this variant in better time?
•  » » » 13 months ago, # ^ |   0 I have idea :)
 » 13 months ago, # |   +1 I somehow frequently mess up the easier problems smh. Got 3 WAs on B when it was just basic implementation, and wasted a lot of time on D, when my first instinct was greedy with priority queue, but ended up trying to solve it with Binary Search unsuccessfully and finally solved it with my first instinct smh.Great problems though.
 » 13 months ago, # |   +8 It’s so great to solve all problems without a WA for the first time!
 » 13 months ago, # | ← Rev. 2 →   +25 Solved C using Kuhn's algorithm... LMAO :D If you are interested:142249902
•  » » 13 months ago, # ^ |   0 Same. The first thing that came to my mind after reading the problem is bipartite matching.
•  » » 13 months ago, # ^ |   +1 I solved it using priority queue :)
•  » » 13 months ago, # ^ |   +3 Could you explain your approach, please? I just don't see how's this problem about bipartite matching...
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 For each number a_i in the array, consider the set of numbers from 1 to n that appear when you keep doing floor(a_i/2).For example, a_i=25 and n=5, then the set is {1,3}.Then we have a bipartite graph of positions and the numbers that could go there. As we can only have one number in each position, this implies a bipartite matching in the graph.
 » 13 months ago, # |   0 how to solve F? Tried something close to a binary search but got WA.
•  » » 13 months ago, # ^ |   0 Yes. Just binary search.
 » 13 months ago, # |   +27 I felt crippled at binary search in F :))
•  » » 13 months ago, # ^ |   +13 F made me realise that if my usual binary search implementation isn't suitable for the problem, then I am screwed :)
 » 13 months ago, # |   +14 This round is amazing! I really enjoy the problems. Thank you very much :)
 » 13 months ago, # |   +3 Video Tutorial B:https://www.youtube.com/watch?v=W-y8gQFrFOYVideo Tutorial C:https://www.youtube.com/watch?v=6k8YudeK_04
 » 13 months ago, # | ← Rev. 2 →   +4 NOice:))
 » 13 months ago, # |   +7
 » 13 months ago, # |   +4 Why is G so simple, although I won't
 » 13 months ago, # |   +9 Interactive problems and BinarySearchForces.Name a more iconic duo. I'll wait.
 » 13 months ago, # |   +23 Why? Just why?? Spoiler
 » 13 months ago, # |   0 Got the binary search idea for D but did not know how to handle the odd case
•  » » 13 months ago, # ^ |   +1 I solved it now
 » 13 months ago, # |   +12 Don't know why but That photo looks like a team of hackers from some Hollywood movie lol :/
 » 13 months ago, # |   +8 What I learned from this contest . Take all inputs before even thinking of outputting an edge case How foolish can I be at times
 » 13 months ago, # |   +11 Then you can swap any two symbols painted in the same color as many times as you want. Imagine not noticing this line in problem D.
 » 13 months ago, # |   0 Are exceeded queries in interactive problems always tagged WA. I kept on thinking about issues with the logic when my solution was actually asking for an extra query than needed.
•  » » 13 months ago, # ^ |   +11 You can have something like this in your code. Now you get MLE if you ask more than 10 queries. if(asked>10){ vector check(MAX*MAX); } 
•  » » » 13 months ago, # ^ |   0 Thanks. Looks like a very useful trick.
•  » » » 13 months ago, # ^ |   +14 You can just keep an assert statement which will give you a runtime error if you exceed the query limit.
 » 13 months ago, # |   0 Hi
 » 13 months ago, # |   +5 Great round. I really enjoyed solving the problems, especially problem G.
 » 13 months ago, # |   +7 In F the condition that x < n was written on top, and I skip it so in 1h30m I can't reduce 11 queries to 10 queries lol :L rip everyone liked me :(
•  » » 13 months ago, # ^ |   0 In the exact same boat as you lol. Hurts a lot since it's a rated contest for me.
•  » » 13 months ago, # ^ |   -34 yea but howcome the answer for the first testcase is 3, it should be less than n right Aris?
•  » » » 13 months ago, # ^ |   +5 How about you read the goddamned statement before trying to point fingers nowhere? Spoilerthis command assigns x=x+cSurprise surprise, the value will and can change
•  » » » » 13 months ago, # ^ |   0 well the statement wasn't clear for me, it hurts to be polite !?
•  » » » » » 13 months ago, # ^ |   -9 Spoiler because i won't flood the page with useless writingDid reading the statement hurt as much?Really, I kinda grew tired of seeing comments toward some issue that has been carefully crafted, such as this contest / problem, being like " well, you know what, problem-author, I think that you are an idiot, the testers are idiots, and everybody that solved this problem are idiots (>500), and I really think I'm right ---- there is a grave inconsistency of some form in your statement that undermines the intended solution ". Really, there might be times when such grave mistakes might pass, but let's face it: this situation would never happen, especially with such a well written contest. Moreover, the excuse of "the problem statement wasn't clear for me" is so underwhelming. It's not as if the statement is about Alice and Bob visiting a pillow case shop where they have to cut pillow cases in half, and to some people it might not be obvious that for some reason you can't cut pillowcases along the thickness line or some stupid not-inherent observation like that — the problem statement is as formal as it can be written, every detail should be in the statement, so yet again, we find ourselves back at square one: "is it really the problem setters fault or is it mine?"If after rereading the statement many times, very carefully, you conclude that it could very much potentially be the problem setters fault, you should alert ''authorities'' and then point out the inconsistency. But that comment was unbased on any evidence, it was made only because youbwere too entitled to try and figure out the problem statement on your own, immediately after hitting bumps you decised to blame one of the problem setters. So, yeah, I do admit that I was rude, but probably I didn't offend the work of some people that spanned maybe weeks or months, and only some careless person.
•  » » » » » » 13 months ago, # ^ |   0 lool, did you even read whatever you pasted? I didn't offend anyone, I was asking a question, I didn't complain about the problem during/after the contest, I also didn't blame the problem writer, nothing happened like that.what I really see is you trying to mimic um_nik's attitude, and it just doesn't look good.
•  » » » » » » » 13 months ago, # ^ | ← Rev. 2 →   0 Yet againSo at this point, I'm either illiterate (which I'm not, since I was able to read the problem statement), you're trying to run away from conflict, or this ( "how come {this}, when {thing that should contradict the other}, right Aris ?" ) is some funny inside joke that I'm not in on.For my peace and quiet, I will assume the last although I strongly believe it is the second option, case in which I really hope you actually read what I wroteAlso, is forming an opinion, argumenting it (with proof, to show what I actually understood and what led me to that cause) and then asking the opposite party what is their argument really um_nik's behaviour? If so, damn, he should get a patent for "behaviour". Sorry for trying to point out anything, and moreover, sorry for not leading your example in making a shitty argument towards a possible point to assert my dominance over.. whatever
•  » » » » » » » » 13 months ago, # ^ |   +8 Congratulations you're not illiterate, because you were able to read the problem statement.Try to have peace in your life, good luck ;)
 » 13 months ago, # |   +4 Was problem G taken from somehwere? It has way too many submissions.
•  » » 13 months ago, # ^ | ← Rev. 2 →   +9 Apparently, the main idea for the problem was the same as one of the ideas used in one of the problems in yesterday's Codechef Snackdown Finals.
•  » » » 13 months ago, # ^ |   +4 hi bro
•  » » » 13 months ago, # ^ |   0 Right the logic is somewhat similar.
 » 13 months ago, # |   0 Nice Div.3 contest. Thank you!
 » 13 months ago, # |   0 Does "wrong answer Jury has answer, but participant doesn't (test case 3648)" means my answer is -1 but Jury is not or my answer is empty? Moreover, I just touch the length of segment must be 2 or 3 in problem E, but I implement it so complex, and finally get a wa2 without anymore clue... https://codeforces.com/contest/1624/submission/142294335
•  » » 13 months ago, # ^ |   0 Yes, it means that the jury was able to find an answer, but you could not. For example, consider this testcase. 1 2 3 000 000 000 The required phone number is just a duplicate of the existing numbers. Hence, an answer definitely exists. However, your code produces $-1$.
•  » » » 13 months ago, # ^ |   0 I get why my algorithm is fake. Thanks a lot~
 » 13 months ago, # |   -14 Video Solutions for anyone looking
 » 13 months ago, # |   +16 This round was very special for me because for the first time I have solved a problem in live contest. I loved it. I am happy and only I know how happy I am. We need more division 3 contest.
 » 13 months ago, # |   0 Got a binary search solution for F, but it gets W/A on 6th test. Can anyone explain mistate or send a test that fails https://codeforces.com/contest/1624/submission/142288442 Thanks!
•  » » 13 months ago, # ^ |   +3 Participant Jury InteractionJury printed n as: 5Jury has picked x as: 3Participant asked to add: 2, x has now become: 5Jury responded with 1Participant asked to add: 4, x has now become: 9Jury responded with 1Participant has guessed the current x as: 10The guess was incorrect.
 » 13 months ago, # |   +18 Amazing contest!The problems were very interesting, especially problem G!
 » 13 months ago, # |   +3 oops, I tried to do something more clever with F and figure out the bits one by one. was wondering why I was retarded for the past hour lol
 » 13 months ago, # |   0 I'am gray. But it is showing under 'only unrated' in my profile's contest page.
•  » » 13 months ago, # ^ |   0 just wait
 » 13 months ago, # |   +8 Upsolved E by matching a string using extended patterns (with code) within regexes (DFS simulation). Perl: 142302044.
 » 13 months ago, # |   +1 Solution to Problem C using "Max Flow" :)142222070Resource For Dinic's algorithm
•  » » 13 months ago, # ^ |   0 If someday there will be an super-algorithm to solve all problems, everyone will be using that !
•  » » » 13 months ago, # ^ |   +1 That will kill the very fun of problem solving
 » 13 months ago, # | ← Rev. 5 →   -15 nice contest
•  » » 13 months ago, # ^ |   +1 Input1 7 4 7 3 6 4 7 5  Expected OutputYES  Your OutputNO  CommentsWe already have $[3, 4, 5, 6, 7]$. We can create 2 by dividing 4, and we can create 1 by dividing 7 repeatedly.
 » 13 months ago, # |   0 O(32(n+m)) was not acceptable in problem G?
•  » » 13 months ago, # ^ |   0 My O(30 * M) code got accepted. https://codeforces.com/contest/1624/submission/142284695
•  » » » 13 months ago, # ^ |   0 Is it not O(30*(n+m))?
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   0 I am going through m edges for every bit so its O(30M). Your code gets accepted(1900ms) if you start with 29th bit.
•  » » » » » 13 months ago, # ^ |   0 Bad luck!
 » 13 months ago, # | ← Rev. 3 →   0 for E consider the following test case2 4127869357878output->23 4 13 4 1I wanted to ask whether the output is correct? that is can we repeat a particular segment?UPD-> Got it, read the announcement now:)
 » 13 months ago, # |   +1 Editorial?
 » 13 months ago, # |   0 Can somebody please explain me why I didn't get any rating for participation in this contest?I don't want to create a new post, so desperately hoping my comment here will get some attention.I'm a newbie in competitive programming and just recently joined Codeforces. I hoped to start acquiring rating and earning experience by participating in Div.3 contests. Even if this contest (#764) is the second contest I'm participating (the first one was Hello 2022 where I solved just one problem), I assumed I'm qualified to be rated in Div.3 contests. However, this one didn't affect my rating at all. Please, help me understand the rules of the system!
•  » » 13 months ago, # ^ |   0 Ratings haven't been updated yet. Normally in div3 rounds, there is a 12-hour hacking phase. When the hacking phase is done, ratings will be updated in a couple of hours.
•  » » 13 months ago, # ^ |   0 you can always wait until the record of this contest appears in your contest history.
 » 13 months ago, # |   0 I got wrong answer "wrong answer Jury has answer, but participant doesn't" in Problem E. I use greedy and kmp algorithm. I match target number as much as possible. Once match is one, i will backtrace one and rematch again. If it can't match target number or one of the segments is one, it will break and output "-1". My algorithm complexity would timed out. But is this algorithm is wrong? I try many tests and verify my answer is correct.
•  » » 13 months ago, # ^ |   0 No, this is correct, you must have made a mistake somwhere.I've done something very similar and it fails only on big tests (tle).
•  » » » 13 months ago, # ^ |   0 Okay, I overestimated your solution. To make up for my mistake here is a test where your solution is failing :).1 1 10 abcxcdxdcx abcdcdcdcd
•  » » » » 13 months ago, # ^ |   0 Thank you for your help :)
 » 13 months ago, # |   0 Still rating is not updated
•  » » 13 months ago, # ^ |   +3 it's system testing. I guess too many successful hacks.
 » 13 months ago, # |   +1 Again! I turned into a zombie after solving 2 problems
 » 13 months ago, # | ← Rev. 3 →   0 Are there any problems with the players ranked 212？Can anybody check it?
 » 13 months ago, # |   0 I saw someone was gonna stream the solution of these but I could not find it now, do you have that link?
•  » » 13 months ago, # ^ |   +6
 » 13 months ago, # |   0 Why this contest is unrated for me? Wasn't it rated for all participant under rating 1600?
•  » » 13 months ago, # ^ |   +1 Instead of killing your nerve cells in waiting you can always use CF predictor (it is quite accurate)
 » 13 months ago, # |   0 rating changes when??
•  » » 13 months ago, # ^ |   +13 after removing cheaters. Wait... :)
 » 13 months ago, # |   0 I know this isn't the intended solution of C, but can someone explain why this wouldn't work? My Submission (WA on 5).
•  » » 13 months ago, # ^ |   +4 Input1 8 8 1 5 6 1 8 6 7  Expected OutputNO  Your OutputYES  CommentWe already have $[1, 5, 6, 7, 8]$.We need to create $[2, 3, 4]$ from $[1, 6, 8]$.We can definitely create $[3, 4]$ from $[6, 8]$. But, you won't be able to create the remaining $2$.
 » 13 months ago, # |   +6 Time limit of Problem G is not java friendly ;(
 » 13 months ago, # |   0 This was my submission — 142369596 for 1624E - Masha-forgetful.The checker log gives me the following message: wrong answer Integer parameter [name=r] equals to 4, violates the range [1, 2] (test case 249) Does this mean that my code prints r = 4 for some line while the length of the number is 2? (correct me if I'm wrong)I can't seem to find my mistake. Any help would be appreciated!
•  » » 13 months ago, # ^ |   +7 No, it doesn't.You forgot to print the number of segments used if $m$ is 2 or 3.For example, one failing test case can be. 1 1 2 00 00 A possible answer is 1 1 2 1 but your code would produce 1 2 1 So, in the original testcase, the jury thinks that you're going to print $L$ segments, while you actually intended to print just one. Hence the WA.
 » 13 months ago, # |   0 This is my submission for problem E 142402622. The checker log gives the message wrong answer Answer phone is not "s" (test case 532). I am not able to understand the meaning of this message and also not able to find the bug in my code. Could somebody please help?
•  » » 13 months ago, # ^ |   +3 Input1 2 5 11110 10001 00100  A Valid Output2 3 4 2 1 3 2  Your Output2 2 4 2 2 3 2 ` CommentsSubstring $[2,4]$ in the second string is $[000]$ while the required phone number has a prefix $[001]$
 » 13 months ago, # |   +14 MikeMirzayanov my submission 142240970 coincides with 142233988 from bernardo_amorim, after looking at his code I think it was triggered because of the main, he have a similar style to mine and this problem is a classical 15 lines problem, I do not know this guy and I did not cheat in any way!!. Please remove the cheating accusation. I saw that he complained too here https://codeforces.com/blog/entry/8790?#comment-876676.
 » 13 months ago, # |   0 The hardest problem of this round: Figuring out what the pun in problem F's name is.I was like: "Interac-dive? But the problem has got nothing to do with diving"
•  » » 13 months ago, # ^ |   0 It's probably 'Interac-div-e' where 'div' stands for the division operation.
 » 13 months ago, # |   0 The girl on the bottom-left looks cute!
•  » » 13 months ago, # ^ |   +3 Agree with you :)