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, Ari, Kuroni, gamegame, and hugopm.
Now, here are some people I would love to mention:
Thank you isaf27 for being a super helpful, diligent, and humorous coordinator ヽ(〃･ω･)ﾉ
Thanks to McDic, nvmdava, dorijanlendvaj, antontrygubO_o, sdssudhu, and farmersrice for helping with the preparation of the tasks.
Thanks to Sofie_Ever, mcfr, MathisHammel, thenymphsofdelphi, neko_nyaaaaaaaaaaaaaaaaa, Endagorion, bjn, Capricornmean, xuanquang1999, Jefe, low_, ngkan, pandourson, mth1908, toshinaritong, EPN, zscoder, minhducsun2002, I_love_Michel_Sardou, 300iq, Noam527, AkiLotus, paquechee, and MofK for testing and giving feedback as well as suggestions to the rounds.
Thanks to MikeMirzayanov for the wonderful Codeforces and Polygon systems that made this contest possible.
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!
hope for SHORT STATEMENT problems and hope for strong pretests !
good luck every body !
Is there some kind of portal, which I'm not aware of, through which one becomes a tester for a CF round?
Hey Savior-of-Cross, how come your comment got deleted? I don't think you violated any rules?
MikeMirzayanov was he muted for orzing? ._.
Yes that is true, people get muted for orzing :(
orz
what is orzing???
No wonder i am not green
No wonder you're blue
It's when a lot of people tell someone how much they admire him, in public instead of by PM.
PM-ing orz is a thing too :(
hello sirs, i hope the round will have statements as short as the announcement.
With that said, you deserve WA invite xD.
smh weeb announcement
you're lacking in newbie testers :\
And unrated testers, too.
R̶a̶t̶i̶s̶t̶ ̶s̶e̶r̶v̶e̶r̶ ̶a̶n̶d̶ ̶.̶.̶.̶
I'm their newbie tester for your record <(")
I cried to them a lot on easy problems...
being a newbie is the best
Especially when you failed in a challenge
nice challenge i will try it for 2021
And headquarter testers
Kuroni oRZ.
Kuroni oRZ
Kuroni oRZ
Kuroni oRZ
Kuroni oRZ
Kuroni oRZ
Kuroni oRZ
sto Kuroni orz
orz doesn't make any sense if you write it with capital R...
small o means small brain
Or a fat body.
or a FAT head
Highly recommended for participation. Both for the weeb and the problemset.
2.5 hours or 2 hours?
2.5, the round's information will be updated soon.
It seems you forgot to update the round's information in the calendar. There are two CF R 616 (Div. 1) with different duration.
Thanks guys for making new problems. By the way
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.
evadava round orzbruh wrong announcementso... were you going to orz your own round?
orz rotavirus
Can't recommend the problems enough!
""AC" (this is also the motto of this contest)"
hmm
yes
the floor here is made out of floor
what are you talking about? AC is a discord server! how did you reach red
why there is no a newbie tester?
don't copy comment
I have not read previous comments :( I am sorry if it is repeated :(
This blog is more colourful than my life.
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?
He must have exposed one of Codeforces' secrets
Well, maybe Mike doesn't like when you mention his name.
Oh, wait...
Maybe it was a reply to a now-deleted comment
Hi my fellow weeb-kun :')
ヽ( ･∀･)ﾉ
Contest 616 is a palindrome contest on 0202 2020
I hope to be an expert after this contest.
But for that ,you will have to participate.
Div 1 A == ( Div 2 C or Div 2 D ) ?
Competing on birthday! :)
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.
Palindrome day(0202 2020) and Palindrome contest number(616) on the 10th birthday of codeforces :)
This is gonna be the first contest on Codeforces gamma.
Happy birthday Codeforces!
All the best everyone! Looking forwards to some really amazing contests this February!
I hate interactive problems :')
y?
z?
Unusual 2.5h
Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).
Yes, this is palindrome roundxD.
because 20200202 is a palindrome
There are more than 1400 participants in Div.1 contest for the first time.
I feel like I'll solve 1-2 problems again. Well, I don't care, I'm in.
Oh my Contribution :O
How to solve more than 1 problem in these contest :( I think I need a Div 4 or Div 5 for myself :|
Hope to become expert today. Pray for me. Eagerly waiting to see that blue color in own profile
congrats~
Thanx
Apparently I cannot write trivial programs (div 2 #1). Why even bother...
How to solve D2-E? Was this DSU + small to big + 2-coloring?
Yes, but you can also preprocess with DFS to get the colorings.
How to solve C?
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.
How to solve Div1.C?
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)).
Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).
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!
I believe there is another contestant in division 1 with the same issue. This is most likely a bug in the platform.
Very fast system testing :)
How to solve Div2 B?
Editorial is available :)
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}$$$.
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?
If your later solution passes pretest, it overrides the earlier one (that one would be considered "Skipped" thenceforth).
What was the purpose of the word "fixed" in the hack format in Div1D?
ksun48 how did you come up with $$$700$$$? I've tried $$$600$$$, which isn't enough, but $$$700$$$ is ok. Did you guess that?
WTf, really?
If that's true, I guess I'm a lucky quacker!!
yes, really xd
$$$700$$$: 70085790
$$$600$$$: 70080411
Hacked.
What about 1500? (assuming it doesn't TLE :P)
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.
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?
Statement says you have to choose it before the process starts
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
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.
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 ?
Yes you should persuade the first min(k,m-1)
The theme of the contest was really good.
Can anyone tell me why this is giving WA. Here's the Solution .Thank You in advance.
0 2 1 0 The output should be Yes.
how??
Got it
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, shouldn`t 9 be the answer then..
"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."
When will ratings get updated?
Kuroni plzz do it asap... system testing was quite fast but rating change has taken a large sum of a time..
I am not Codeforces admin how can I do it :(
It changed the moment you commented though xD
Same question
is something wrong with ratings?
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 ?
Such a waste of time !! Only if else based problems
The return of the king! MWM couldn't stop tourist to win the round, now poor MiFaFaOvO is second.
I wanted to sleep well at nights... Seems I won't. :)
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? ...
Congrats :D
TOO ( ´ ▽ ` )ﾉ MANY （*´▽｀*) EMOJI ヽ(〃･ω･)ﾉ IN :D THE o(≧∇≦o) CONTEST ( ͡° ͜ʖ ͡°)
Is there anyway to get the "system testing" test cases downloaded after the contest. I mean all test cases ..
Oops, my bad luck on problem A :( Passed test 10 on pretests, failed the same test on the system test.
Div1C in $$$O(n ^ 2)$$$ : 70081179.
It is $$$O(n ^ 2)$$$ bc function "add" sometimes works in $$$O(size + b.size)$$$.