Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### Kuroni's blog

By Kuroni, history, 3 years ago,

Hello Codeforces o(≧∇≦o) I'm glad to introduce you to Codeforces Round #616 (Div. 1) and Codeforces Round #616 (Div. 2), which will take place on Feb/02/2020 17:05 (Moscow time).

Each division will contain 6 problems, and you will have 2.5 hours to solve them. There might be interactive problems, feel free to learn about them here. The problems were created by 265918, Sexpert, Kuroni, gamegame, and hugopm.

Now, here are some people I would love to mention:

The statements were made as clear as possible for your best experiences. Moreover, we sneakily included a theme in the problemset, and each problem will have an easter egg that is the clue to the theme. If you have AC'd every problem, be sure to search for the theme（*´▽｀*)

Additionally, most of us are in a Discord server dedicated to competitive programming called "AC" (this is also the motto of this contest). We will be on the server after the contest to discuss the problems with you. You can find the server here!

I wish you all have good luck and high ratings ( ´ ▽  )ﾉ

UPD1: Here is the score distribution:

• Div. 2: 500 1000 1500 2000 2750 3000

• Div. 1: 500 1000 1750 2500 3000 3250

UPD2: Here is the editorial, including easter egg solutions!

UPD3: Thank you everyone for participating :D Here are the final standings:

Div. 1:

Div. 2:

Thank you everyone and I hope to see you again!

• +739

 » 3 years ago, # |   -6 hope for SHORT STATEMENT problems and hope for strong pretests !good luck every body !
 » 3 years ago, # |   +376
•  » » 3 years ago, # ^ |   +82 Is there some kind of portal, which I'm not aware of, through which one becomes a tester for a CF round?
•  » » » 3 years ago, # ^ |   +51 Hey IntoTheNight, how come your comment got deleted? I don't think you violated any rules?
•  » » » » 3 years ago, # ^ |   +64 MikeMirzayanov was he muted for orzing? ._.
•  » » » » » 3 years ago, # ^ |   0 Yes that is true, people get muted for orzing :(
•  » » » » » » 3 years ago, # ^ |   +18 orz
•  » » » » » » 3 years ago, # ^ |   0 what is orzing???
•  » » » » » » » 3 years ago, # ^ |   -13 No wonder i am not green
•  » » » » » » » » 3 years ago, # ^ |   -10 No wonder you're blue
•  » » » » » » » » 3 years ago, # ^ |   0 You have my respect blue sir
•  » » » » » » » 3 years ago, # ^ |   0 It's when a lot of people tell someone how much they admire him, in public instead of by PM.
•  » » » » » » » » 3 years ago, # ^ |   0 Ah, I see now.Thanks
•  » » » » » » » » 3 years ago, # ^ |   0 PM-ing orz is a thing too :(
•  » » 3 years ago, # ^ |   +104 hello sirs, i hope the round will have statements as short as the announcement.
•  » » » 3 years ago, # ^ |   +6 With that said, you deserve WA invite xD.
 » 3 years ago, # |   +50 smh weeb announcement
 » 3 years ago, # |   +85 you're lacking in newbie testers :\
•  » » 3 years ago, # ^ |   0 And unrated testers, too.
•  » » 3 years ago, # ^ |   -14 R̶a̶t̶i̶s̶t̶ ̶s̶e̶r̶v̶e̶r̶ ̶a̶n̶d̶ ̶.̶.̶.̶
•  » » 3 years ago, # ^ |   +3 I'm their newbie tester for your record <(")I cried to them a lot on easy problems...
•  » » 3 years ago, # ^ |   +3 being a newbie is the best
•  » » » 3 years ago, # ^ |   +11 Especially when you failed in a challenge
•  » » » » 3 years ago, # ^ |   +11 nice challenge i will try it for 2021
•  » » 3 years ago, # ^ |   +3 And headquarter testers
 » 3 years ago, # |   +74 Kuroni oRZ.
•  » » 3 years ago, # ^ |   +47 Kuroni oRZ
•  » » » 3 years ago, # ^ |   +42 Kuroni oRZ
•  » » » » 3 years ago, # ^ |   +42 Kuroni oRZ
•  » » » » » 3 years ago, # ^ |   +45 Kuroni oRZ
•  » » » » » » 3 years ago, # ^ |   +33 Kuroni oRZ
•  » » » » » » » 3 years ago, # ^ |   +15 Kuroni oRZ
•  » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   -16 sto Kuroni orz
•  » » » » » » » » » 3 years ago, # ^ |   -7 Kuroni oRZ
•  » » 3 years ago, # ^ |   0 orz doesn't make any sense if you write it with capital R...
•  » » » 3 years ago, # ^ |   +79 small o means small brain
•  » » » » 3 years ago, # ^ |   +46 Or a fat body.
•  » » » » » 3 years ago, # ^ |   -46 or a FAT head
 » 3 years ago, # |   +30 Highly recommended for participation. Both for the weeb and the problemset.
 » 3 years ago, # |   +11 2.5 hours or 2 hours?
•  » » 3 years ago, # ^ |   +19 2.5, the round's information will be updated soon.
•  » » » 3 years ago, # ^ |   0 It seems you forgot to update the round's information in the calendar. There are two CF R 616 (Div. 1) with different duration.
 » 3 years ago, # |   +16 Thanks guys for making new problems. By the way Happy Lunar New Year from Vietnam ! 
 » 3 years ago, # | ← Rev. 2 →   +31 Kuroni How kind of you to come to #purgatory to discuss the problems with noobs like us! You are great sir! P.S: #purgatory in AC is one of my favourite places everrrr.
 » 3 years ago, # | ← Rev. 4 →   -40 evadava round orz bruh wrong announcement
•  » » 3 years ago, # ^ |   +16 so... were you going to orz your own round?
•  » » 3 years ago, # ^ |   +4 orz rotavirus
 » 3 years ago, # |   +198 Can't recommend the problems enough!
 » 3 years ago, # |   +59 ""AC" (this is also the motto of this contest)"hmmyesthe floor here is made out of floor
•  » » 3 years ago, # ^ |   -41 what are you talking about? AC is a discord server! how did you reach red
 » 3 years ago, # |   +12 why there is no a newbie tester?
•  » » 3 years ago, # ^ |   -46 don't copy comment
•  » » » 3 years ago, # ^ |   +7 I have not read previous comments :( I am sorry if it is repeated :(
 » 3 years ago, # |   -66
 » 3 years ago, # |   +49 This blog is more colourful than my life.
 » 3 years ago, # |   +108 How come the first one "Mike just messages me at random times (although I usually decline ...)" of Benq's comments is gone? Is that a codeforces bug?
•  » » 3 years ago, # ^ |   +65 He must have exposed one of Codeforces' secrets
•  » » 3 years ago, # ^ | ← Rev. 2 →   +83 Well, maybe Mike doesn't like when you mention his name. Oh, wait...
•  » » 3 years ago, # ^ |   +35 Maybe it was a reply to a now-deleted comment
 » 3 years ago, # |   +37 Hi my fellow weeb-kun :')
•  » » 3 years ago, # ^ |   +27 ヽ(　･∀･)ﾉ
 » 3 years ago, # |   -29 In 2.5 hours may be 7 problems would better!
 » 3 years ago, # |   -8 I'm ready for colour change-)
 » 3 years ago, # |   +323 Contest 616 is a palindrome contest on 0202 2020
 » 3 years ago, # |   -6 I hope to be an expert after this contest.
•  » » 3 years ago, # ^ |   0 But for that ,you will have to participate.
 » 3 years ago, # | ← Rev. 2 →   +1 Div 1 A == ( Div 2 C or Div 2 D ) ?
•  » » 3 years ago, # ^ |   0 DIV 2 C.
 » 3 years ago, # |   +43 Competing on birthday! :)
 » 3 years ago, # |   +20 Today is very special day. The date is 02-02-2020 (02022020) which is a palindrome number. Hope everyone will do well in contest on this day. Happy coding.
 » 3 years ago, # | ← Rev. 2 →   0 Palindrome day(0202 2020) and Palindrome contest number(616) on the 10th birthday of codeforces :)
 » 3 years ago, # | ← Rev. 2 →   +176 This is gonna be the first contest on Codeforces gamma.
 » 3 years ago, # |   +16 Happy birthday Codeforces!
 » 3 years ago, # |   0 All the best everyone! Looking forwards to some really amazing contests this February!
 » 3 years ago, # |   -14 I hate interactive problems :')
•  » » 3 years ago, # ^ |   -9 y?
•  » » » 3 years ago, # ^ |   +6 z?
 » 3 years ago, # |   0 Unusual 2.5h
 » 3 years ago, # |   0 Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).
 » 3 years ago, # |   0 Yes, this is palindrome roundxD.
•  » » 3 years ago, # ^ |   +8 because 20200202 is a palindrome
 » 3 years ago, # |   +4 There are more than 1400 participants in Div.1 contest for the first time.
 » 3 years ago, # |   +4 I feel like I'll solve 1-2 problems again. Well, I don't care, I'm in.
 » 3 years ago, # |   -11 Oh my Contribution :O
 » 3 years ago, # |   +12 How to solve more than 1 problem in these contest :( I think I need a Div 4 or Div 5 for myself :|
 » 3 years ago, # |   0 the weebs have killed my rating :sobs :sobs
 » 3 years ago, # | ← Rev. 2 →   +19 Hope to become expert today. Pray for me. Eagerly waiting to see that blue color in own profile
•  » » 3 years ago, # ^ |   0 congrats~
•  » » » 3 years ago, # ^ |   0 Thanx
 » 3 years ago, # | ← Rev. 2 →   +5 Apparently I cannot write trivial programs (div 2 #1). Why even bother...
 » 3 years ago, # |   +101
 » 3 years ago, # |   +6 How to solve D2-E? Was this DSU + small to big + 2-coloring?
•  » » 3 years ago, # ^ |   +1 Yes, but you can also preprocess with DFS to get the colorings.
 » 3 years ago, # |   +7 How to solve C?
•  » » 3 years ago, # ^ |   0 Bruteforce on how many people will you force to take from the front, then bruteforce on how many people may take from front, and each possible outcome see what is the maximum thing you can take.
 » 3 years ago, # |   +7 How to solve Div1.C?
•  » » 3 years ago, # ^ |   -27 How to solve Div1.A?
•  » » 3 years ago, # ^ |   0 for k times remove 0 to k elements from left, and k to 0 elements from the right.From the remaining queue they can remove arbitrarily elements until position m is reached. Brute force all such pairs for min(max(left, right)).
 » 3 years ago, # |   0 Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).
 » 3 years ago, # |   0 even though i am a registered contestant,whenever i submit a solution it says you are not registered! I dont know whats happening! any help will be appreciated!
•  » » 3 years ago, # ^ |   0 I believe there is another contestant in division 1 with the same issue. This is most likely a bug in the platform.
•  » » » 3 years ago, # ^ |   0 well i solved problem c and d this time! but yep its fine! thanks though! hope so it does not affects my rating!
 » 3 years ago, # |   +9 Very fast system testing :)
 » 3 years ago, # |   +104
 » 3 years ago, # |   -13 How to solve Div2 B?
•  » » 3 years ago, # ^ |   +5 Editorial is available :)
•  » » » 3 years ago, # ^ |   0 Thank you!
 » 3 years ago, # |   0 Is $\mathcal{O}(n \sqrt{n} \log n)$ fast enough to pass in E?The total number of edges that change in the tree over the course of the algorithm is $\mathcal{O}(n \sqrt n)$, which can be proven with the potential function $P = \sum_{i = 1}^{n} |T_{i}|$ where $T_{i}$ is the subtree of node $i$:The potential increases by at most $n$ at every step, and if at some step we change $2k$ edges, then the potential decreases by $\binom{2k}{2} - 2\binom{k}{2} \approx \frac{1}{2} \binom{k}{2}$, which is quadratic in $k$. If $\sum_{i = 1}^{n} k_{i}^{2} \leq n^{2}$, then $\sum_{i = 1}^{n} k_{i} \leq n \sqrt{n}$.
 » 3 years ago, # |   0 I have a question: I sent problem B in the 20th minute and then I sent another solution in time 2:40:00 but the time it gives me is the second one, it should not be the shortest time to be accepted?
•  » » 3 years ago, # ^ |   +16 If your later solution passes pretest, it overrides the earlier one (that one would be considered "Skipped" thenceforth).
 » 3 years ago, # |   0 What was the purpose of the word "fixed" in the hack format in Div1D?
 » 3 years ago, # |   +14 ksun48 how did you come up with $700$? I've tried $600$, which isn't enough, but $700$ is ok. Did you guess that?
•  » » 3 years ago, # ^ |   0 WTf, really?
•  » » 3 years ago, # ^ |   +36 If that's true, I guess I'm a lucky quacker!!
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 yes, really xd$700$: 70085790$600$: 70080411
•  » » » » 3 years ago, # ^ |   +10 Hacked.
•  » » » » » 3 years ago, # ^ |   0 What about 1500? (assuming it doesn't TLE :P)
•  » » » » » » 3 years ago, # ^ |   +10 Hacked easily...Again, the testset is sooo strong. But don't worry, it's impossible to predict all the solutions. Also, in this problem, Massey is the last thing ever that comes to the mind, especially when there are almost no testers.
 » 3 years ago, # |   +2 In Div2C 6 4 2 2 9 2 3 8 5 if you not control first person then if first person chooses 2 then you will force other two to take 5 and 8 respectively and you will end up at 9 if first person chooses 5 then you will force other two to take 2 and 8 respectively and you will end up at 9 so in both cases you will get x as atleast 9. why it is not possible?
•  » » 3 years ago, # ^ |   0 Statement says you have to choose it before the process starts
•  » » » 3 years ago, # ^ |   +6 could you explain it :D ?i think this statement doesn't add any new info ? what if i choose it correct to reach the same answer as Ssgss
•  » » » » 3 years ago, # ^ |   +1 This approach requires you to know the choice taken by the first person. It's possible that before the process starts you persuade them to take 5, 8 but first person ends up taking 3, which forces you to take 2.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +5 so should i force the first person ?edited: after a while i got it. but there is something => "you have to choose it before the process starts" it equals persuade first min(k,m-1) doesn't it ?
•  » » » » » » 3 years ago, # ^ |   +1 Yes you should persuade the first min(k,m-1)
 » 3 years ago, # |   +32 The theme of the contest was really good.
 » 3 years ago, # | ← Rev. 2 →   0 Can anyone tell me why this is giving WA. Here's the Solution .Thank You in advance.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 0 2 1 0 The output should be Yes.
•  » » » 3 years ago, # ^ |   0 how??
•  » » » » 3 years ago, # ^ |   0 Got it
 » 3 years ago, # |   +1 In problem c for test case 1 6 4 2 2 9 2 3 8 5 let 1st person be the not-controlled person, and 2nd,3rd be the controlled persons, so after first person finishes scenario will be - 9 2 3 8 5 or 2 9 2 3 8 now for 2nd and 3rd person i can well control them to choose elements such that i get 9 in both cases, shouldnt 9 be the answer then..
•  » » 3 years ago, # ^ |   0 I agree with you
•  » » 3 years ago, # ^ |   +11 "Before the process starts, you may ...""Once the process starts, you cannot persuade any more people, and you cannot change the choices for the people you already persuaded."
 » 3 years ago, # |   0 When will ratings get updated?
•  » » 3 years ago, # ^ |   0 Kuroni plzz do it asap... system testing was quite fast but rating change has taken a large sum of a time..
•  » » » 3 years ago, # ^ |   +11 I am not Codeforces admin how can I do it :(
•  » » » » 3 years ago, # ^ |   0 It changed the moment you commented though xD
•  » » 3 years ago, # ^ |   0 Same question
 » 3 years ago, # |   0 how to solve B? i couldn't understand the editorial of it. why suffix/prefix come here? what is the idea behind it?
 » 3 years ago, # |   +18 is something wrong with ratings?
 » 3 years ago, # |   +14 I was cyan when I was taking this contest and before I became blue I registered for the upcoming Div.3 contest and now in the registrants list my Handle doesn't have a little star next to it and I don't think I'm the only one So my question is that is the contest gonna be rated for people like me or not ?
 » 3 years ago, # |   -41 Such a waste of time !! Only if else based problems
 » 3 years ago, # |   +10 The return of the king! MWM couldn't stop tourist to win the round, now poor MiFaFaOvO is second.
 » 3 years ago, # |   0 I wanted to sleep well at nights... Seems I won't. :)
 » 3 years ago, # | ← Rev. 2 →   +90 In a palindromic round(#616) on a palindromic day(20200202), my rating changed from a palindrome(2882) into another palindrome(2992). A lovely coincidence!I hope it would have been 3003 instead of 2992, though...Anyway: Happy birthday, Codeforces! (Perhaps it's a bit late? ...
•  » » 3 years ago, # ^ |   0 Congrats :D
 » 3 years ago, # |   +5 TOO ( ´ ▽ ` )ﾉ MANY （*´▽｀*) EMOJI ヽ(〃･ω･)ﾉ IN :D THE o(≧∇≦o) CONTEST ( ͡° ͜ʖ ͡°)
 » 3 years ago, # |   0 Is there anyway to get the "system testing" test cases downloaded after the contest. I mean all test cases ..
 » 3 years ago, # |   +6 Oops, my bad luck on problem A :( Passed test 10 on pretests, failed the same test on the system test.
 » 3 years ago, # |   0 Div1C in $O(n ^ 2)$ : 70081179. It is $O(n ^ 2)$ bc function "add" sometimes works in $O(size + b.size)$.