Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Kuroni's blog

By Kuroni, history, 4 weeks ago, In English,

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 02.02.2020 17:05 (Московское время).

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:

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:

  1. tourist

  2. fateice

  3. ksun48

  4. Um_nik

  5. WZYYN

Div. 2:

  1. izone

  2. Infoshoc

  3. CouponKaka-ChutteNahiHai

  4. lzh12139

  5. liqing

Thank you everyone and I hope to see you again!

 
 
 
 
  • Vote: I like it
  • +739
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

hope for SHORT STATEMENT problems and hope for strong pretests !

good luck every body !

»
4 weeks ago, # |
  Vote: I like it +376 Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +50 Vote: I do not like it

smh weeb announcement

»
4 weeks ago, # |
  Vote: I like it +85 Vote: I do not like it

you're lacking in newbie testers :\

»
4 weeks ago, # |
  Vote: I like it +74 Vote: I do not like it

Kuroni oRZ.

»
4 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

Highly recommended for participation. Both for the weeb and the problemset.

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

2.5 hours or 2 hours?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    2.5, the round's information will be updated soon.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It seems you forgot to update the round's information in the calendar. There are two CF R 616 (Div. 1) with different duration.

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Thanks guys for making new problems. By the way

Happy Lunar New Year from Vietnam !
»
4 weeks ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

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.

»
4 weeks ago, # |
Rev. 4   Vote: I like it -40 Vote: I do not like it

evadava round orz bruh wrong announcement

»
4 weeks ago, # |
  Vote: I like it +198 Vote: I do not like it

Can't recommend the problems enough!

»
4 weeks ago, # |
  Vote: I like it +59 Vote: I do not like it

""AC" (this is also the motto of this contest)"

hmm

yes

the floor here is made out of floor

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -41 Vote: I do not like it

    what are you talking about? AC is a discord server! how did you reach red

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

why there is no a newbie tester?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -46 Vote: I do not like it

    don't copy comment

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      I have not read previous comments :( I am sorry if it is repeated :(

»
4 weeks ago, # |
  Vote: I like it -66 Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +49 Vote: I do not like it

This blog is more colourful than my life.

»
4 weeks ago, # |
  Vote: I like it +108 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +65 Vote: I do not like it

    He must have exposed one of Codeforces' secrets

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +83 Vote: I do not like it

    Well, maybe Mike doesn't like when you mention his name.

    Oh, wait...

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    Maybe it was a reply to a now-deleted comment

»
4 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

Hi my fellow weeb-kun :')

»
4 weeks ago, # |
  Vote: I like it -29 Vote: I do not like it

In 2.5 hours may be 7 problems would better!

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

I'm ready for colour change-)

»
4 weeks ago, # |
  Vote: I like it +323 Vote: I do not like it

Contest 616 is a palindrome contest on 0202 2020

»
4 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

I hope to be an expert after this contest.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Div 1 A == ( Div 2 C or Div 2 D ) ?

»
4 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

Competing on birthday! :)

»
4 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

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 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Palindrome day(0202 2020) and Palindrome contest number(616) on the 10th birthday of codeforces :)

»
3 weeks ago, # |
Rev. 2   Vote: I like it +176 Vote: I do not like it

This is gonna be the first contest on Codeforces gamma.

»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Happy birthday Codeforces!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

All the best everyone! Looking forwards to some really amazing contests this February!

»
3 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

I hate interactive problems :')

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Unusual 2.5h

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes, this is palindrome roundxD.

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

There are more than 1400 participants in Div.1 contest for the first time.

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

I feel like I'll solve 1-2 problems again. Well, I don't care, I'm in.

»
3 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Oh my Contribution :O

»
3 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

How to solve more than 1 problem in these contest :( I think I need a Div 4 or Div 5 for myself :|

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

the weebs have killed my rating :sobs :sobs

»
3 weeks ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

Hope to become expert today. Pray for me. Eagerly waiting to see that blue color in own profile

»
3 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Apparently I cannot write trivial programs (div 2 #1). Why even bother...

»
3 weeks ago, # |
  Vote: I like it +101 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve D2-E? Was this DSU + small to big + 2-coloring?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes, but you can also preprocess with DFS to get the colorings.

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve C?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve Div1.C?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -27 Vote: I do not like it

    How to solve Div1.A?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I believe there is another contestant in division 1 with the same issue. This is most likely a bug in the platform.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      well i solved problem c and d this time! but yep its fine! thanks though! hope so it does not affects my rating!

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Very fast system testing :)

»
3 weeks ago, # |
  Vote: I like it +104 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

How to solve Div2 B?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    If your later solution passes pretest, it overrides the earlier one (that one would be considered "Skipped" thenceforth).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the purpose of the word "fixed" in the hack format in Div1D?

»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    WTf, really?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    If that's true, I guess I'm a lucky quacker!!

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      yes, really xd

      $$$700$$$: 70085790

      $$$600$$$: 70080411

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Hacked.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          What about 1500? (assuming it doesn't TLE :P)

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            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 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Statement says you have to choose it before the process starts

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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 weeks ago, # ^ |
          Rev. 2   Vote: I like it +5 Vote: I do not like it

          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 weeks ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Yes you should persuade the first min(k,m-1)

»
3 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

The theme of the contest was really good.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone tell me why this is giving WA. Here's the Solution .Thank You in advance.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like 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..

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I agree with you

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    "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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When will ratings get updated?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Kuroni plzz do it asap... system testing was quite fast but rating change has taken a large sum of a time..

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      I am not Codeforces admin how can I do it :(

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It changed the moment you commented though xD

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same question

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve B? i couldn't understand the editorial of it. why suffix/prefix come here? what is the idea behind it?

»
3 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

is something wrong with ratings?

»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it -41 Vote: I do not like it

Such a waste of time !! Only if else based problems

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

The return of the king! MWM couldn't stop tourist to win the round, now poor MiFaFaOvO is second.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I wanted to sleep well at nights... Seems I won't. :)

»
3 weeks ago, # |
Rev. 2   Vote: I like it +90 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

TOO ( ´ ▽ ` )ノ MANY (*´▽`*) EMOJI ヽ(〃・ω・)ノ IN :D THE o(≧∇≦o) CONTEST ( ͡° ͜ʖ ͡°)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there anyway to get the "system testing" test cases downloaded after the contest. I mean all test cases ..

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Oops, my bad luck on problem A :( Passed test 10 on pretests, failed the same test on the system test.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Div1C in $$$O(n ^ 2)$$$ : 70081179.

It is $$$O(n ^ 2)$$$ bc function "add" sometimes works in $$$O(size + b.size)$$$.