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:

- DmitryGrigorev for the great coordinating and helping us with preparing problems.
- Our testers: gamegame, dorijanlendvaj, fedoseev.timofey, tfg, fastmath, Allvik06, Pechalka, Alexdat2000, pakhomovee, Frankenween, philmol, Ultrasanic, tox1c_kid, Viktoriuss and Urvuk3 for their feedback, especially tfg for finding mistakes in the statements.
- MikeMirzayanov for codeforces and polygon platform!
- KAN for his contribution to this round as well.

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:

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

AIs not partipicating again?

Call in Google)

Or apply for a job in Google and ask your boss)

:/...

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.

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

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

ლ(´ڡ`ლ)

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:Proposing to rename master rank to maestro for EvgeniyPonasenkov

unfortunately only russians can understand this

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

(* ^ ω ^)

cutea

here before atilla gets negative contribution

I decided not to type it (sorry for people who didn't get the context)

contextlmao

Programmers if the AI fails to beat them

Programmers who create the AI :

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.

hello

No.

Tbh it gives those t-shirts some prestige right?

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 ?

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

(づ｡◕‿‿◕｡)づ ❤

:-))

Mangooste orz for authoring two concecutive rounds.

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

I wish everyone to increase their rank)

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

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

SpoilerAuto comment: topic has been updated by Mangooste (previous revision, new revision, compare).`DmitryGrigorev for the great coordinating and helping us with preparing probles.`

typo in problems

Edit: fixed

Thank you! Fixed.

Will it contain any interactive problem?

No.

nice

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.

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

Will this round be rated?

Yes, it is rated for everyone.

ok, thank you

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

NANOGrav

I hope I will enjoy it！

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

Best of luck, all

Thanks, you too

this one goes out to all my fellow noobs:

"The final result for each participant is equal to the sum of points

hegets in the four roundsheplaced the highest."so

shedoesn't get any result?Is registration during contest not allowed?

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

I wasted on A. Took less time on B and C than A

Yeah, maybe this contest will make me a pupil

What other rules are on Codeforces?

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

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

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

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

"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.

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

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$$$.

Could you explain please how does this give us the correct answer? I still don't really get 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.

Thanks a lot!

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

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?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.

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

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.

I used

`map`

and also passed pretests. Hope I wouldn't fail system test.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?

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

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

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.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.

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

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

How to solve G?

wxhtzdy orz

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

What's the ideal time complexity to solve E?

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

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)).

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)How to solve B?

$$$dp[i][j][k] := $$$ the maximum

costto split $$$b[i, ..., j]$$$ into k subsegmentsminus 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.

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.

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.

(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.

Weak and useless samples!

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

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?

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

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 :/

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

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.

Feedback on the problems:

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

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.

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?

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

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

After this, I feel so dumb. :(

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

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.)

it's only visible to the judges, and if they found that there is actually a mistake they will announce 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

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:

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".

haha, I was guilty of this, good observation!

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

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.

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.

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

sorry I read the wrong number.It's O(n).

I have something like

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

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

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?

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

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.

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 .

... and then sort in

non-decreasingorder the prefix ...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.

solution is to just check if the array is sorted.

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

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

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

pretest in E is so weak...

+1 to this

One would think that a max test would be

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

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.

i find that. I just calc ans like

`(i+j)*p.w`

instead of`(u+v)*p.w`

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

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

Same

Got two submission wrong for it :)

Same, I lost my expert for it :)

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

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

https://codeforces.com/contest/1637/submission/146157321

Could you rejudge the submission please? Thanks in advance!

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 :(

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

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

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.

nice proof, thanks

Fast Rating Change!!

Apparently, there was no plagiarism in this contest. The ranks during the contest are same as final standings. In the last educational round, Mike said that there would be a recheck and ratings would be updated after removing cheaters, and apparently, ratings never got updated. https://codeforces.com/blog/entry/99483?#comment-883045

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

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$$$.

oh shoot didn't notice that detail thanks a lot

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

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.

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

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.

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 :)

great round overall :)

If you believe that

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

Proofpic about being handsome?

SpoilerI want to join :D

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

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

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

Unofficial T-shirt winners listUpdate 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.cpp3) Run the Python script

`winners.py`

, replacing the number in`contest = []`

with the ID of the contest in question (in this case,`1637`

):winners.pyBoth 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:

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

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

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.

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

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.pyrandgen.cpp