Kuroni's blog

Codeforces Round #616
By Kuroni, history, 5 years 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 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:

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

Comments Comments (137)
| Write comment?
»
5 years 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 !

→ Reply
»
5 years ago, # |
  Vote: I like it +376 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it +50 Vote: I do not like it

smh weeb announcement

→ Reply
»
5 years ago, # |
  Vote: I like it +85 Vote: I do not like it

you're lacking in newbie testers :\

→ Reply
»
5 years ago, # |
  Vote: I like it +74 Vote: I do not like it

Kuroni oRZ.

→ Reply
»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

2.5 hours or 2 hours?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
»
5 years 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 !
→ Reply
»
5 years 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.

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it -40 Vote: I do not like it

evadava round orz bruh wrong announcement

→ Reply
»
5 years ago, # |
  Vote: I like it +198 Vote: I do not like it

Can't recommend the problems enough!

→ Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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

    → Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

why there is no a newbie tester?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -46 Vote: I do not like it

    don't copy comment

    → Reply
    • »
      »
      »
      5 years 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 :(

      → Reply
»
5 years ago, # |
  Vote: I like it -66 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it +49 Vote: I do not like it

This blog is more colourful than my life.

→ Reply
»
5 years 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?

→ Reply
»
5 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Hi my fellow weeb-kun :')

→ Reply
»
5 years ago, # |
  Vote: I like it +323 Vote: I do not like it

Contest 616 is a palindrome contest on 0202 2020

→ Reply
»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

I hope to be an expert after this contest.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +43 Vote: I do not like it

Competing on birthday! :)

→ Reply
»
5 years 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.

→ Reply
»
5 years 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 :)

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +176 Vote: I do not like it

This is gonna be the first contest on Codeforces gamma.

→ Reply
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Happy birthday Codeforces!

→ Reply
»
5 years 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!

→ Reply
»
5 years ago, # |
  Vote: I like it -14 Vote: I do not like it

I hate interactive problems :')

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Unusual 2.5h

→ Reply
»
5 years 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).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes, this is palindrome roundxD.

→ Reply
»
5 years 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.

→ Reply
»
5 years 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.

→ Reply
»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Oh my Contribution :O

→ Reply
»
5 years 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 :|

→ Reply
»
5 years 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

→ Reply
»
5 years 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...

→ Reply
»
5 years ago, # |
  Vote: I like it +101 Vote: I do not like it

→ Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve Div1.C?

→ Reply
  • »
    »
    5 years 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)).

    → Reply
»
5 years 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).

→ Reply
»
5 years 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!

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Very fast system testing :)

→ Reply
»
5 years ago, # |
  Vote: I like it +104 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it -13 Vote: I do not like it

How to solve Div2 B?

→ Reply
»
5 years 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}$$$.

→ Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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).

    → Reply
»
5 years 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?

→ Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    WTf, really?

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      yes, really xd

      $$$700$$$: 70085790

      $$$600$$$: 70080411

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Hacked.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years 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.

            → Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Statement says you have to choose it before the process starts

    → Reply
    • »
      »
      »
      5 years 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

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
        • »
          »
          »
          »
          »
          5 years 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 ?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

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

            → Reply
»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

The theme of the contest was really good.

→ Reply
»
5 years 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.

→ Reply
»
5 years 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..

→ Reply
  • »
    »
    5 years 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."

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will ratings get updated?

→ Reply
  • »
    »
    5 years 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..

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It changed the moment you commented though xD

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same question

    → Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

is something wrong with ratings?

→ Reply
»
5 years 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 ?

→ Reply
»
5 years ago, # |
  Vote: I like it -41 Vote: I do not like it

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

→ Reply
»
5 years 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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years 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? ...

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
5 years 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 ..

→ Reply
»
5 years 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.

→ Reply
»
5 years 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)$$$.

→ Reply