Mangooste's blog

Codeforces Global Round 19
By Mangooste, history, 3 years ago, translation, In English

Hello, Codeforces! (づ｡◕‿‿◕｡)づ ❤

On Feb/12/2022 17:35 (Moscow time) we will host Codeforces Global Round 19.

It is the first round of a 2022 series of Codeforces Global Rounds supported by XTX Markets. The rounds are open and rated for everybody.

The presents for this round:

  • 30 best participants get a t-shirt.
  • 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The presents for the 6-round series in 2022:

  • In each round top-100 participants get points according to the table.
  • The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
  • The best 20 participants over all series get sweatshirts and place certificates.

The problems were written and prepared by Mangooste, TeaTime, __JustMe__ and EvgeniyPonasenkov.

We are very thankful to people, who made this round possible:

You will have 2.5 hours to solve 8 problems. And we recommend you to read all the problems!

The score distribution will be announced closer to the start of the round.

UPD: The scoring distribution: 500 — 1000 — 1500 — 2000 — 2500 — 3250 — 4000 — 4000

UPD: Editorial.

Congratulations to the winners:

  1. tourist
  2. Um_nik
  3. Maksim1744
  4. heno239
  5. ksun48
  6. Vercingetorix
  7. jiangly
  8. SomethingNew
  9. Laurie
  10. VivaciousAubergine
Announcement of Codeforces Global Round 19
  • Vote: I like it
  • +1029
  • Vote: I do not like it

Comments Comments (164)
| Write comment?
»
3 years ago, # |
  Vote: I like it +334 Vote: I do not like it

We tried our hardest to make interesting tasks. We hope you will enjoy solving our problems as much as we did enjoy creating them (づ｡◕‿‿◕｡)づ

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

AIs not partipicating again?

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

    Call in Google)

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

      I think google developers are sure that AI will get place in first 5000 rank so it's useless to participate in contests now and they wait until they make enough progress to participate in a contest that they can get a good rank.

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

I still have PTSD from the last round having cute text emoticons in the announcements.

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

    ଘ(੭*ˊᵕˋ)੭* ੈ♡‧₊˚!

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

    hmm same. I couldn't solve D1 B and later got my A hacked, which I couldn't fix by the end of the contest either.

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

Proposing to rename master rank to maestro for EvgeniyPonasenkov

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

    unfortunately only russians can understand this

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

As a tester I really enjoyed solving and upsolving problems from this contest. Hope you too!

(* ^ ω ^)

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

cutea

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

Programmers if the AI fails to beat them

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

I was looking forward to a rated round but then a notification reminded me that I tested a round recently ;(

GLHF everyone though, let us all :sip: at this special contest.

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

    hello

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

      No.

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

      Tbh it gives those t-shirts some prestige right?

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

        yes, definitely, but what is the advantage to give it to the same people again. Either way distributing it among 1000 and 50 shirts is more encouraging to people. Those in top 1000 also have some prestige right ?

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

          But after its increased to 1000, someones gonna say why not increase it to 2000 and so on

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

(づ｡◕‿‿◕｡)づ ❤

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

Mangooste orz for authoring two concecutive rounds.

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

Why is there no mention of XTX Markets in the announcement? (edit: now added)

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

I wish everyone to increase their rank)

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

    If wishes would've worked this way, I would be a lgm by now.

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

Are AI accounts participating? Bet these AI bots did not recover well from the last round

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

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

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

    DmitryGrigorev for the great coordinating and helping us with preparing probles.

    typo in problems

    Edit: fixed

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

Will it contain any interactive problem?

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

Good luck everyone!

Hope you enjoy the tasks ♡!!!

P.S. Actually, it takes a lot of hard work to prepare every task properly, so upvote the initial post as a sign of respect for the contest setters.

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

I add rating every time I join Global Round, hope you so. Really enjoy. :)

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

Will this round be rated?

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

Hoping for a nice round!

I will be not able to participate in contests for a long time after this round because of the new term. TAT

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

NANOGrav

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -43 Vote: I do not like it

I hope I will enjoy it！

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

hoping to first time get rank under 1500 in div 2.

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

Best of luck, all

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

this one goes out to all my fellow noobs:

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

"The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest."

so she doesn't get any result?

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

Is registration during contest not allowed?

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

I wasted too much time on B and C ... overthinking sucks man!

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

Yeah, maybe this contest will make me a pupil

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

Solved C in 30 minutes, solved D in 80 minutes, and then solved E in 20 minutes. What a disbalance!! Problem D isn't quite good, because you need just guess, that you have to minimize |sum(a)-sum(b)|. Rest was good, Liked problem E

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

    You don't need to guess, dp[i][sum] = 1..i, sum = sum of a, it's easy to calculate the answer.

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

    I figured that minimization actually but couldn't able to implement can anyone tell how to minimize |sum(a)-sum(b)|?

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

      Find all the possible sum(a) instead (using variation of knapsack algo)

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

    "You need to guess".

    I don't think there is any guesswork to this problem.

    Expand $$$(a_i + a_j)^2$$$ as $$$a_i^2 + a_j^2 + 2 \cdot a_i \cdot a_j$$$. Clearly the two square terms will occur regardless of which array you are in.

    Toying around with equations a bit, we can realize sum $$$2 \cdot a_i \cdot a_j$$$ over all $$$i \lt j$$$ is just $$$(\sum{a_i})^2 - \sum{(a_i^2)}$$$.

    The second part is again constant regardless of which array we put it in. So now we clearly want to minimize $$$(\sum{a_i})^2 + (\sum{b_i})^2$$$ which is identical to your condition.

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

      Simple and clear. Sad that I did not get the equations.

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

    you don't have to guess, just $$$dp[i][sum]$$$ — min cost of $$$a[0...i]$$$ + $$$b[0...i]$$$ after doing swaps on first $$$i$$$ positions and sum of $$$a[0...i]$$$ is $$$sum$$$.

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

      Could you explain please how does this give us the correct answer? I still don't really get it.

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

        after going through other people's code and reading the editorial i found out that my solution is pretty retarded, since i did not realize some parts of the cost are independent, but whatever:

        first let's assume we have just one array, for example $$$[1, 2, 4]$$$ and add $$$x$$$ to the end of it, how does the cost change?

        $$$old cost + (1 + x)^2 + (2 + x)^2 + (4 + x)^2$$$, which if we rewrite is $$$old cost + x^2 + 2x + 1 + x^2 + 4x + 4 + x^2 + 8x + 16$$$. (just $$$(a + b)^2 = a^2 + 2ab + b^2$$$, which is what i should have realized earlier, because it means $$$a^2$$$ and $$$b^2$$$ are independent, but since i solved for one unknown, i did not realize that, anyways)

        you can generalize that expansion to $$$i * x^2 + x * 2 * \displaystyle\sum_{j=0}^{i-1} a_j + \displaystyle\sum_{j=0}^{i-1} a_j^2$$$.

        now let $$$dp[i][sum]$$$ have 3 values, the minimum cost and then $$$\displaystyle\sum_{j=0}^{i-1} a_j^2$$$ and $$$\displaystyle\sum_{j=0}^{i-1} b_j^2$$$.

        The last two values are the retarded part, since they could be completely omitted, because each $$$a_i^2$$$ is counted $$$n - i$$$ times in the final cost. ($$$0$$$-indexed and same for all of $$$b_i$$$).

        Anyways, first let's set all the of the states to $$$\{\infty, \infty, \infty\}$$$.

        Base cases are $$$dp[0][a_0] = dp[0][b_0] = \{0, a_0 * a_0, b_0 * b_0\}$$$.

        Now the transition are:

        • $$$dp[i+1][sum + a_i] = min(dp[i+1][sum + a_i], \{dp[i][sum][0] + f(i, a_i, sum, dp[i][sum][1]), dp[i][sum][1] + a_i * a_i, dp[i][sum][2] + b_i * b_i\})$$$

        • $$$dp[i+1][sum + b_i] = min(dp[i+1][sum + b_i], \{dp[i][sum][0] + f(i, b_i, pref_i - sum, dp[i][sum][2]), dp[i][sum][1] + b_i * b_i, dp[i][sum][2] + a_i * a_i\})$$$

        $$$pref_i = \displaystyle\sum_{j=0}^{i} a_j + \displaystyle\sum_{j=0}^{i} b_j$$$ — sum of first $$$i$$$ values of $$$a$$$ and $$$b$$$.

        $$$f(i, x, sum, sumOfSquares) = i * x^2 + 2 * x * sum + sumOfSquares + a_i * a_i$$$ — cost of adding $$$x$$$ to the end of an array with length $$$i$$$ and sum of it's elements and sum of squares of each of it's elements. (you can see the independent part of the cost being independent in this function too lmao, can't believe i have not noticed this while solving the problem for the first time in contest)

        answer is then minimum of $$${dp[n][sum]}$$$ for all $$$sum$$$ from $$$0$$$ to $$$\displaystyle\sum_{i=0}^{n-1} a_i + b_i$$$.

        I know, it's extremely retarded. But that's how i solved it during the contest (i can finally solve harder tasks than before, but most of the time it is this kind of an overkill for some reason) and you asked for it so ¯\_(ツ)_/¯.

        if you have any questions, feel free to ask. but for your sanity, i recommend simply reading the editorial.

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

    I solved B really quickly but took an hour on C and had to leave the contest before I had a chance to solve D

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

Somehow, you can pass pretests in E if you use unordered_map, but not gp_hash_table, is it intended? I thought gp_hash_table should be way faster... Also, my solution seems to be $$$O(n \log n)$$$ and is already quite close to the time limit, was it intentional that $$$O(n \sqrt n)$$$ doesn't pass? Or did it pass for others?

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

    You can solve it in $$$O(n \sqrt n)$$$ without unordered sets, though the TL is pretty tight even then.

    I had to replace a map of vectors with a single vector of pairs to pass pretests since the constant factor difference in iterating over them was too heavy.

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

    My $$$O(n \sqrt n)$$$ passed pretests in 967/2000 ms

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

    Mine passed pretests with O(n root(n) ), but i dont use any maps or hash tables for the bottleneck part of the code, e.g. the (n root(n) ) part doesnt use any maps, i map the values to [1 ... n] beforehand.

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

    I used map and also passed pretests. Hope I wouldn't fail system test.

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

    My $$$O(n \sqrt n)$$$ almost got TLE on pretest (1965/2000ms). Why $$$n \le 3 \times 10^5$$$ and 2s TL if $$$O(n \sqrt n)$$$ is intended?

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

    My $$$\mathcal{O}(m\log^2n)$$$ solution with segment tree gave TLE twice before it passed all the pretests.

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

    The problem is likely the hash function you are using. See this comment.

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

      Yeah... I spent like an hour optimizing my $$$O(n \sqrt n)$$$ thinking it's the problem. But just replacing gp_hash_table with unordered_map was enough in the first place and I just wasted a lot of time trying to circumvent it.

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

    I'm kind of surprised to see that the TL was so tight for others since my $$$O(n\sqrt{n}\log{(n+m)})$$$ solution passed in 530 ms.

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

      Read -is-this-fft-'s comment. It may be a non-sqrt solution.

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

        Oh you're right. It's $$$O(n\log{(n+m)})$$$. That's really interesting.

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

How to solve G?

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

wxhtzdy orz

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -16 Vote: I do not like it

never mind this is trash i had no time to think about it well

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

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

What's the ideal time complexity to solve E?

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

    O(n * lg(n) + m * lg(m))

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

    I solved it in O(N*sqrt(N)) with the ideia that if the sum of elements is equal N the number of different is O(sqrt(N)).

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

    I solved it in O(nlogn + mlogm) complexity (or something like that) and the "logn" and "logm" factors come from the C++ STL maps and sets I used, as well as the STL sort function. If you really want, you could replace the maps and sets with their hash-based counterparts and the STL sort with a count sort and get a linear time complexity... (I think)

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

How to solve B?

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

    $$$dp[i][j][k] := $$$ the maximum cost to split $$$b[i, ..., j]$$$ into k subsegments minus j-i+1 (which means $$$dp$$$ includes only the sum of $$$MEX$$$ part).

    base case: $$$dp[i][j][1] = MEX(b_i, ..., b_j)$$$

    transition: $$$dp[i][j][k] = \max(dp[i][x][1] + dp[x+1][j][k-1]) \ \ \forall x \in [i, j)$$$

    time complexity for calculating $$$dp$$$ is $$$O(n^4)$$$, then add up the solutions for all subsegments.

    for a subsegment $$$[i, j]$$$ we care about the $$$k$$$ s.t. $$$dp[i][j][k] + j-i+1$$$ is the max.

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

    For each a[i], I set its value to 2 if a[i] is 0 else 1. Then for each number, multiply its value by the number of subsegments it is in and add that to your answer. Finally, print your answer.

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

    notice that max cost on a subsegment is simply length of subsegment + number of 0's in subsegment. Just sum this value over all subsegments to get answer.

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

    (One of) the best way(s) to break each subarray is always to break it into single elements. It brings the length of subarray plus number of zeroes in it. So the result is the sum of lengthes of all possible subarrays plus number of occurencies of zeroes in all of them. With given constraints, it is possible to brute force it.

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

Weak and useless samples!

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

Imagine implementing $$$O(n \sqrt{n})$$$ in E (and doing constant factor optimization to get it to pass) only to realize afterwards the easier $$$O(n \sqrt{n} \log{n})$$$ solution somehow runs faster — 146115870

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

    How do you come with the sqrt solution in E? I still don't quite get it. So basically we can just store the frequency of all numbers and bruteforcing each possible pairs?

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

      because there are at most $$$O(\sqrt{n})$$$ distinct cnt values.

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

E was only about realizing we need to keep max 2 elements per count (max O(sqrt(n)) candidates )? Such low number of submissions completely threw me off :/

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

    Did your solution work? I think you need more than 2 elements per count in case those two elements form a bad pair.

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

For problem D, it took me a long time to realize that the given cost is $$$(a_1 + ... + a_n) ^ 2 + (n - 2) * (a_1 ^ 2 + ... + a_n ^ 2)$$$, and the second part doesn't affect the answer.

But if I just guess "minimizing $$$|sum(a) - sum(b)|$$$", which is actually intuitive, then I can submit a solution much quicker. However, I don't think guessing is a good way to solve problems.

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

Feedback on the problems:

  • A: Ok.
  • B: The idea is nice, the way you decided to transform the idea into a problem, so-so. Would have been cleaner with $$$n=100\,000$$$ and just asking for the value of the array (instead of the sum over whatever).
  • C: Good problem. The moment I read it, I thought I was going to get stuck and in fact I got stuck (at least I am consistent). For me, this was much harder than D.
  • D: Very standard, solved immediately after reading.
  • E: Very good problem. I had to think and when I noticed that $$$cnt$$$ can have at most $$$\sqrt{n}$$$ values and this was sufficient to solve the problem, I was somewhat happy.
  • F: Cute problem. This felt easy, most likely because I was lucky and noticed immediately that rooting the tree at the highest vertex is useful.
  • G: (unexpectedly) Cool problem. The first thought reading it is "who cares?". Then, when I saw the point of the problem (which was shown to me by a backtracking), I changed my mind. I solved this in contest apart from the limit on the number of queries (because I was doing something incredibly stupid), solved 3 minutes after the end of the round. I enjoyed solving it.
  • H: Not read.

I enjoyed a lot the contest because the problems at "my level" (i.e., E, F, G) were very nice. Thanks to the authors.

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

    Agreed. Despite having a solution to G but writing stupid buggy code and not being able to fix it in time, I really liked the round. My favourite problem was F (with my implementation, it was a data structure problem!) but I liked E as well.

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

    I got stuck at D for 1.5 hrs... Can I know how you mean by "very standard"? What's the first thought/idea after you read the problem?

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

    can you please tell why problem D is very standard. Thanks

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

    Thank you for participating and for positive feedback about this round. I am glad you like problem G!

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

After this, I feel so dumb. :(

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

    Next time you feel that way, just click through my profile. It will make you feel better about yourself.

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

If we comment via the "ask a question" link during the contest, is it visible to everyone or just the commentor/ judges? I made a mistake where I thought there was a problem flaw where there was none and I didn't know whether or not to apologize because I didn't want to disrupt anyone who was still coding.

Also, if it is public, is there a better way to bring things like these up?

Thanks to all, and especially to the judges for a wonderful round (and for putting up with the annoyance I may have caused you.)

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

    it's only visible to the judges, and if they found that there is actually a mistake they will announce it

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

      Thank goodness!!! I was afraid I had disrupted the competition for no reason. I still looked foolish, I guess, just not in front of quite so many people. XD

      Thank you for reply. +1

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

E is interesting in the sense that based con some conversations I bet there are a lot of people who wrote an $$$O((n + m) \log n)$$$ or similar non-sqrt solution without realizing it.

My solution is basically this:

1 for (int cx = 1; cx <= n; cx++) {
2   for (int x : wcnt[cx]) { // the list of things with cnt[x] = cx
3     for (int cy = 1; cy <= cx; cy++) {
4       // try the best non-forbidden y with cnt[y] = cy
5     }
6   }
7 }

Trivia question: how many times is line 4 hit? Answer: it is in fact $$$O(n)$$$. For a fixed $$$x$$$, the number of times line 4 is executed is the frequency of $$$x$$$, so in total we visit line 4 once for every element in the array.

I believe this proof can be adapted to several people who proudly claimed to have passed E in $$$O(n \sqrt n)$$$ or even $$$O(n \sqrt n \log n)$$$ with "no constant optimizations".

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

    haha, I was guilty of this, good observation!

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

    can u explain me test case 3 2 1 4 5 in problem A ,as it can be sorted by prefix and suffix

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

      You are not asked to find whether you can sort the array, but if you can make the operation so that the array is NOT sorted. Thus, choosing the prefix formed by the first two numbers and the suffix with the last 3 numbers would solve the testcase.

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

    I figured out the approach but I failed the system test because I had a typo in the break condition where I wrote ans>(cx+cy)(x*y) instead of (cx+cy)*(x+y). My solution when I replaced the * and submitted after the contest.

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

    But your program actually is O(n sqrt(n)). I generate a data and your program updates ans 329094649 times.

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

    I have something like

    for (int x: unique_numbers) {
   for (int cnt_y: existing_cnts) { // no cnt_y <= cnt[x] check
      // find first non-forbidden y with cnt[y] = y
   }
}

    Which works fast-ish as well. Do you understand if it's faster than O(n sqrt(n)) as well?

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

      I initially thought just this this would be faster too, but it looks like this is still $$$\Theta(n \sqrt n)$$$.

      The complexity is the number of distinct frequencies, multiplied by the number of distinct values. For a given $$$n$$$ we can construct a bad case like this. Let $$$a$$$ be the number of distinct frequencies. Make a number with frequency 1, a number with frequency 2, ..., a number with frequency $$$a$$$, then add numbers with frequency 1 until we have filled the array. The number of distinct numbers is $$$a + n - \frac12 a(a + 1)$$$; the complexity will then be

      $$$a \left( a + n - \frac12 a(a + 1) \right).$$$

      Using calculus to maximize it for $a > 0$ shows that we can pick $$$a$$$ to get $$$\Theta(n \sqrt n)$$$ runtime.

      EDIT: I tried to hack you and got unexpected verdict. People tell me this is due to a tester (?) solution failing. Maybe tests are indeed weak here?

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

        It got rejudged. Almost 3x from the worst real test, but still passing :)

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

I enjoyed this contest, it required a lot of observation, and problem C felt like a troll :D

took many tries and observations to figure it out, but eventually i solved it.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

In problem A. 3 2 1 4 5 can be sorted as 3 2 1 and 4 5 are sorted individually so ans will be no ,but many has written solution as if there is increasing array ans will be yes. can anyone explain me this test case .

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

    ... and then sort in non-decreasing order the prefix ...

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

    I did the same mistake at first and wasted stupidly 1 hour on A. What you should do is find a value len for which the array is not going to be sorted at the end, if found then YES otherwise NO.

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

Nice round! E was cute but I was a bit dumb on it.

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

For me, Problem C is harder than D and E. But liked the observation in C the most.

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

did the 700th upvote:) nice problems , loved problem D

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

pretest in E is so weak...

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

    +1 to this

    One would think that a max test would be 

    1
300000 0
1 1 1 ... 1 1

    but that has no solutions. so instead if you had done

    1
300000 0
2 1 1 1 ... 1 1

    you would have made the simplest max test. and yet not a single test in the pretests had an element occur more than 800 (which was a constant in my code) times.

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

      i find that. I just calc ans like (i+j)*p.w instead of (u+v)*p.w and it passed pretest:(

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

F is cool, create interesting&fresh task on tree is giga hard nowadays, so thanks to authors :)

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

Didn't use long long in C. (T_T)

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

MikeMirzayanov My submission on E got TLE on system test. But the exactly same code passed after the contest.

link: https://mirror.codeforces.com/contest/1637/submission/146139122
https://mirror.codeforces.com/contest/1637/submission/146157321

Could you rejudge the submission please? Thanks in advance!

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

    The test case where I TLEed only takes 1871ms. The volatility is more than 129ms, which is a bit huge. I felt really bad about this :(

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

Spent too much time on C but solution is concise and pleasant 146131266

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

How to prove that "minimum power of two at least n" is the minimum achievable value in G?

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

    If we "undo" two numbers $$$x,y$$$ then two numbers become $$$\frac{x+y}{2},\frac{x-y}{2}$$$, so we can never get rid of any odd prime factor of the final value.

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

Fast Rating Change!!

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

Can somebody please point out whats happening? I used modified knapsack in D and here are two submissions Solution 1 AC Solution 2 WA The only difference between them is that I sorted arrays a and b before knapsack in solution 2 but that should not affect the answer. Can somebody point out the reason? Thanks in advance

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

    You can only swap $$$a_i$$$ and $$$b_i$$$ for some $$$1 \le i \le n$$$, not $$$a_i$$$ and $$$b_j$$$ for some $$$1 \le i, \ j \le n$$$.

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

      oh shoot didn't notice that detail thanks a lot

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

      Can you suggest what changes would have to be made if any index swapping was allowed?

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

        I did this for half the contest. I solved using 3d dp and bitset to achieve $$$O(n^3A/64)$$$ (A = maximum element). Basically finding out all possible sums when you select $$$n$$$ out of the $$$2n$$$ elements provided.

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

Very cool round, thanks a lot to authors! Problems F, G were especially cool

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

    One of the best rounds I have seen in a while, thanks a lot to the authors! Can't tell about GH, but I just loved how natural most of the problems were. Here's some specific feedback:

    A: this is the one I liked the least, fits too well into a recently-overused "implement the least complicated solution that passes sample testcases", and understanding the statement somewhat takes more time than coming up with the solution.

    B: absolutely an amazing problem for its position. Allows a simple mathematical solution, but there is also a straightforward DP if you don't feel like proving anything..

    C: an adhoc, but a rather natural one, and the solution is quite neat, too.

    D: a more standard DP problem that requires some algebraic manipulation. Nice to see some DP in a Global Round.

    E: cute algorithmic problem, a bit more on the standard side too. This idea has appeared before in some Div1D based on Moscow State Olympiad (or something like that), nonetheless still a nice task!

    F: woah, this was brilliant! I failed to notice that "root in maximum" makes the life a lot easier, and instead implemented an overcomplicated DP which had a bug in the end. I'm amazed that you managed to find such a simple-statement algorithmic challenge that's fresh.

    Unlike some other GRs, this one really had a great balance in difficulty and topics. I hope that we will continue seeing more of your rounds! Mangooste et al.

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

Shout out to kal013 for becoming the highest rated Indian of all time on cf by beating amnesiac_dusk.

PS: I've been following both of them since I started cp :)

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

great round overall :)

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

If you believe that

  • top-10 by cf rating as of now
  • top-1 at codeforces global round 19 by atcoder penalty rules
  • top-1 at being the most handsome guy in our ICPC team

legendary overtrained upsolver Maksim1744 will win the next ICPC WF, then make sure to join his official fan group!

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

When I take part in global round, it makes me feel sad every time.

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

The description of this contest's problem is very bad！

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

Truth be told,really really bad.I have never seen the bad description like this

→ Reply
»
3 years ago, # |
← Rev. 10   Vote: I like it +112 Vote: I do not like it

Unofficial T-shirt winners list

Update 2: It looks like cheaters have been removed, and the standings have been updated. As such, the full list of winning handles has been added.

Going forward, I'll post only the list places of winners (in a compact format) shortly (~12h) after the contest. While not as useful, you can still check to see if you're close to becoming a T-shirt winner. Once the standings have been updated to remove cheaters, I'll post the full list of winning handles.

Update 1: Since cheaters have not been removed yet, the standings is not final and is subject to change. As a result, this list of winners will probably change significantly. The list place of winners won't change, but the winning handles will. For now, I have removed the winning handles outside the top 30, and I will update the list once cheaters have been removed.

Since the official announcement isn't here yet and I'm an impatient person, I've decided to find out who won the t-shirts for myself.

As always, you can do the following steps to get the t-shirts winners of Global Rounds:

1) Download testlib.h from Mike's github repo.

2) Use it to compile randgen.cpp :

randgen.cpp

3) Run the Python script winners.py, replacing the number in contest = [] with the ID of the contest in question (in this case, 1637):

winners.py

Both of these scripts are taken from the official winners announcements in previous Global Rounds, but if you have any doubts on their legitimacy you can always check these results against the official ones later.

With that out of the way, congratulations to the (unofficial) t-shirt winners:

List place Contest Rank Name
1 1637 1 tourist
2 1637 2 Um_nik
3 1637 3 Maksim1744
4 1637 4 heno239
5 1637 5 ksun48
6 1637 6 Vercingetorix
7 1637 7 jiangly
8 1637 8 SomethingNew
9 1637 9 Laurie
10 1637 10 VivaciousAubergine
11 1637 11 Rewinding
12 1637 12 Petr
13 1637 13 ecnerwala
14 1637 14 Endagorion
15 1637 15 visiteur
16 1637 16 wxhtzdy
17 1637 17 Egor
18 1637 18 antontrygubO_o
19 1637 19 A-SOUL_Bella
20 1637 20 kal013
21 1637 21 kotatsugame
22 1637 22 Y25t
23 1637 23 never_giveup
24 1637 24 hos.lyric
25 1637 25 wk_tzc
26 1637 26 KrK
27 1637 27 peti1234
28 1637 28 conqueror_of_tourist
29 1637 29 hanbyeol_
30 1637 30 BigBag
87 1637 87 golikovnik
93 1637 93 satashun
105 1637 105 kektus
113 1637 113 olphe
116 1637 116 fanache99
166 1637 166 CaiLiyi
171 1637 171 huangxiaohua
175 1637 175 lucaperju
176 1637 176 magnus.hegdahl
224 1637 224 HoshimiOWO
228 1637 228 anpoli99
255 1637 255 liouzhou_101
279 1637 279 AghaParsa
302 1637 302 Colchoneta
347 1637 347 MagicalFlower
373 1637 373 MysteryGuy2
383 1637 383 RedMind
401 1637 401 nikgaevoy
425 1637 425 priemniygeniy
449 1637 449 aropan

P.S. If any contest organizer has any issue with early unofficial winners list like this one, feel free to contact me.

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

    Please note that most probably this list will change significantly after cheaters removal.

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

      Yeah that happened last time too, I will update the list when it happens.

      Next time it's probably best to wait 2-3 days before posting, but then not many people will be checking the thread and see the post.

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

I was accused of cheating, and after i have checked ADO/146139752, ChtotoSlabovato/146145769, 9_shuriken/146152539 i realised that the only thing we have in common is partition function which was found by me on the internet by link https://www.geeksforgeeks.org/partition-a-set-into-two-subsets-such-that-the-difference-of-subset-sums-is-minimum/. I was only copypasting from geekforgeeks, not from other contestants

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

Congratulations to tshirts winners! You will be contacted via private messages with instructions to receive your prize. Note that currently tshirts deliveries are significantly delayed due to multiple reasons, but we'll do our best to send the tshirts as soon as we can.

As usual, we used the following two scripts for generating random winners, seed is the score of the winner.

get_tshirts.py
randgen.cpp
List place Contest Rank Name
1 1637 1 tourist
2 1637 2 Um_nik
3 1637 3 Maksim1744
4 1637 4 heno239
5 1637 5 ksun48
6 1637 6 Vercingetorix
7 1637 7 jiangly
8 1637 8 SomethingNew
9 1637 9 Laurie
10 1637 10 VivaciousAubergine
11 1637 11 Rewinding
12 1637 12 Petr
13 1637 13 ecnerwala
14 1637 14 Endagorion
15 1637 15 visiteur
16 1637 16 wxhtzdy
17 1637 17 Egor
18 1637 18 antontrygubO_o
19 1637 19 A-SOUL_Bella
20 1637 20 kal013
21 1637 21 kotatsugame
22 1637 22 Y25t
23 1637 23 never_giveup
24 1637 24 hos.lyric
25 1637 25 wk_tzc
26 1637 26 KrK
27 1637 27 peti1234
28 1637 28 conqueror_of_tourist
29 1637 29 hanbyeol_
30 1637 30 BigBag
87 1637 87 golikovnik
93 1637 93 satashun
105 1637 105 kektus
113 1637 113 olphe
116 1637 116 fanache99
166 1637 166 CaiLiyi
171 1637 171 huangxiaohua
175 1637 175 lucaperju
176 1637 176 magnus.hegdahl
224 1637 224 HoshimiOWO
228 1637 228 anpoli99
255 1637 255 liouzhou_101
279 1637 279 AghaParsa
302 1637 302 Colchoneta
347 1637 347 MagicalFlower
373 1637 373 MysteryGuy2
383 1637 383 RedMind
401 1637 401 nikgaevoy
425 1637 425 priemniygeniy
449 1637 449 aropan
→ Reply