On Apr/23/2022 17:05 (Moscow time), we will host Codeforces Global Round 20.

**Note the unusual timing, it is 30 minutes earlier.**

This is the second round of the 2022 series of Codeforces Global Rounds. The rounds are open and rated for everybody.

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

Thanks to XTX, which in 2022 supported the global rounds initiaitive!

All problems were written and prepared by errorgorn, maomao90 and oolimry.

We would like to thank the following people who made this round possible:

- antontrygubO_o for coordinating our round and somehow only rejecting 2 div2As.
- oolimry for contributing to national defence and keeping Singapore safe.
- dario2994 for being the best tester. The perfect tester does not exist but I think dario2994 comes really close to it.
- tqbfjotld, gamegame,dorijanlendvaj, dario2994, kclee2172, Monogon, nvmdava, TheScrasse, jamessngg, pavement, iLoveIOI, AlperenT, icypiggy, timreizin, Myrcella, DeMen100ns, QuangBuiCPP, bWayne, chicken337, joelau for testing the round and providing useful feedback.
- MikeMirzayanov for Codeforces and Polygon.

You will have **3 hours** to solve **9 problems, one of which is divided into two subtasks**.

The scoring distribution is **250-500-750-1000-1500-(1250+1250)-2750-3000-4000**. GLHF!

Also, please upvote the blog so that I can get more contribution than antontrygubO_o.

PS: We would like to take this opportunity to congratulate rotavirus or antontrygubX_y on getting married. Wishing you lots of love and happiness.

Edit: Editorial is released. Even if you have solved a problem, we encourage you to read the editorial as you might learn something new from it.

Honestly, you should definitely participate in this contest. Problems are very good.

Also, as the only tester with sunglasses on, please give me contribution.

Global Round 20? Sounds like sphere-earther propaganda to me--get me a Global Flat!

Jkjk, see you all on the scoreboard, I'm hyped for another chance to earn my purple back :)

Who knows, you might even earn the legendary blue :)

At least red is chromatically closer to purple than yellow

Back to red again!!!

Why is gravity not having effect on your glasses?

Pikachu is pulling it up with electric force

My coolness is what keeps them in place. Don't you see my suit?

No offence though

Is it possible to advance the start time of the contest to start at

13:00 UTCsuch that it does not overlap with the HackerEarth Circuits April'22 contest which starts at16:00 UTC?How do you become a tester as an unrated user?

The most interesting part is how you get listed before lgms

tqbfjotld orz

by becoming IGM from alt acc xD

unusual timings not so usual nowadays.

12:00 UTC — 13:40 UTC ABC249

14:05 UTC — 17:05 UTC GR20

16:00 UTC — 18:00 UTC SRM828

Busy day! (And the last hour of GR is the first hour of SRM (coding phase))

Could you please tell what contest is SRM828?

Top coder single round match?(topcoder.com)

I'd also like to know about GR20 please

GR 20 is Global Round 20 i.e. the competition announced in this post :)

As a tester, good luck.

As the setter who did not get to write the announcement :(, please compensate me with more upvotes than the announcement.

Just post the editorial then :)

As a tester, screw you maomao90

As a tester I can tell the problems are curated and very interesting. Shoutout to the authors and antontrygubO_o

All the best to everyone!

Could you please shift that at least one hour earlier to avoid clash with TopCoder round?

Surely Mike would change the contest time to prevent any clashes (Clueless)

Axaxaxaxaxa

What's funny here?

Good luck to everyone!

This contest will be my first step toward a sacred goal

Best of Luck! I hope you do well :)

It would be almost impossible for me to not :P

9 problems and 3 hours! This will be tough

Chill, our concern in div 2 is usually the first 4/5.

Eat Sleep

get positive ratingrepeatSo Many contests back to back. Contest after iftar and My condition...

I hope I could get to 1500 again after this contest

As a stupidest tester, GLHF everyone :3

you weren't stupid enough to make code that would help improve pretests lmao. don't be so harsh on yourself

Is it rated?

It is rated for everybody as mentioned in the blog.

No permutation problems since errorgorn is an author? :)

Oh no, you're too wrong

sadlyfCongratulations rotavirus early-morning-dreams

All the best! May you get the color that you are looking for!

I don't want color, I want T-shirt

like for any other Codeforces contest, I am excited for this too!!

errorgorn thanks for the round!

Congratulationsearly-morning-dreams and rotavirus...মানুষের সুখ কখনও চিরস্থায়ী হয় না, একদিন না একদিন তার বিয়ে হয়ে যায়...May the joy of your new life be filled with laughter, smiles, kisses, hugs, respect, understanding, and faithfulness...

Happy Wedlock!Should beginners take part in global contests?

yes

Can anyone tell me why my submission is working fine locally but not in cf 154251073.

I know such things happens when we access unallocated memory, but not getting where I'm wrong here...

`vector.size()`

returns an unsigned integer and if we subtract a value bigger than that unsigned integer from it then it doesn't result in a negative integer but some bigger value(near the max value of an unsigned int). The same happens in your case. It's always advised to typecast it to int.ExampleCodeOutput4294967295

AC Submission after typecasting

Thanks a lot!

Congratulations rotavirus and early-morning-dreams

Should be or instead of and

Is this contest Rated?

Yes, it is rated for all.

I request you to make out 1 minute from your very busy schedule to read the blog. Its clearly mentioned "The rounds are open and rated for everybody."

The only reason I wake up everyday is to be there when an unrated account called antontryvirus AKs a hard Codeforces Global as its very first round.

WAon2Forces :(

swe

I never solved a single problem this contest on the first try. I got A on my 6th try, B on my 4th, and C on my 3rd. So if you think you had a bad contest, think again. -150 and newbie level performance (just 2 contests ago, I was candidate master)

HackedForces :(

After the best result ever I go back to pupil. And I told myself that God will forgive me if one round is skipped.

Welcome Codeforces! I am mister Bebra.

ConstructiveForces

I just wanna say that problem C was

EvilGot a weird bug on D, thought my algo was correct :(

same everyone has WA test 2 but i got on 3 and I felt it was correct too

same

How to solve E?

Spent 11 minutes to solve A. Spent 26 minutes to solve F1.` Yes ! Welcome to the constructive algorithms hell!.

Isn't problem I just a simple application of Endless Road trick?

Apologies. I wasn't aware that the trick had been used before. It turns out the exact same trick was used in some Petrozavodsk contest which gamegame pointed out only 5 days ago.

We did not really have a replacement problem for a global round last so we had not choice but to use this problem instead. I think even knowing such problems exist, setting this problem was ok since there is a non-trivial greedy observation before you can use this trick. But maybe to you, this greedy step is trivial. Hopefully you still enjoyed the rest of the problem set :/

MikeMirzayanov check my bro fuckyou for code obfuscation of greatest caliber (i looked at his submissions on hacking), he also had submissions skipped in the past

In last hour, finally, I recalled I haved give the same idea with pH in codeforces round. (https://codeforces.com/contest/1329/problem/D). and antontrygubO_o ever said my problems is dirty. :(

Yes, I am really sorry, I couldn't recall this problem even though I have upsolved it :( And no tester could remember it either.

Overall it was a nice contest, but I think problem H was too easy

I got stuck on D for exactly two hours and I didn't even pass it after passing E and F1. Holy ****ing ****.

Now my solution for E is also hacked. Beautiful.

Shouldn't the output of AAABABB is "NO" for problem B??

you can go from "" to "AB" to "A^AB^B" to "A^AAB^ABB"

Insert AB

Insert AAB at position 2, making the string AAABB

Insert AB at position 3, making the string AAABABB

You can add good strings in the following way s = "" s = "**AB**" s = "A**AB**B" s = "A**AAB**ABB

You firstly add AB (AB), then insert between A and B string AAB (AAABB), then after the second A insert AB (AAABABB) and there you have your resulting string

if the initial string is AAB you can insert AB after second A so the string now is AAABB then insert AB again after the second A also so the result will be AAABABB

You can make it by

A_B

AAAB_B ->inserting AAB

AAABABB ->inserting AB

No, it shouldn't.

A A B->A AA BB->A A A BA BBF1 was fun to try, but I couldn't do it after an hour. Hope to learn from solutions, good round!

So what exactly was there in Problem D's TC 3?

yes, I want to know as well

I am more curious coz I am getting runtime error on TC3, everything in code looks right.

if you solved it with 2 pointers 154747684 like me, then you should've considered the case if (ptrA < n || ptrB < n) then ans will be "No".

Took me 1 hour trying random solutions till I decided to

randomlytry what I described above. Was surprised to see AC.Try testcase like

This gives YES if only checked for blocks, but ignoring the freqs.

Turns out, I just had to replace an 'if' with a 'while' keyword.

1,000,000x :face-palm:Contest Submission.

Practice Submission.

I am getting memory limit exceeded in F1, but everything looks fine.

I am using set with a custom comparator function. And yes, I am removing elements from the set as well.

Solve functionsubmission link : https://codeforces.com/contest/1672/submission/154765626

Your comparator is not well-behaved. For example, if

`a = (0, 0), b = (2, 0), c = (1, 1)`

you have`a < c`

and`c < b`

but`b < a`

. There is no weak ordering over`a, b, c`

consistent with it.Thanks, so is there any way to modify the comparator or should I think of new logic?

The pretest of E is very weak. if you set the upper bound of binary search as 4e6, you will get FST because there is no maximum data in pretest. The correct upper bound is 2000*2000+2000-1=4001999.

The upper bound is 10^9 for width. It's written in the

`interaction`

section of the statement.He meant the maximum possible width you can need to fit everything in one line. This value is at most $$$2000 N + N-1$$$.

Ohh, my bad. I didn't use that.

Also, if you binary search with l = 0 instead of l = 1, you'll get FST, which is what happened to most people

It's doesn't matter because 4e6 is enough for the final answer. 2000 * 2000 is the real upper bound.

Yeah I got FST exactly because of this. It really doesn't feel good.

There's no way my solution of E will pass! I just threw in some "if can't improve current answer" to decrease the number of queries in normal cases. It still probably has a countertest.

Too many FSTs in E afraid me :(

Note the unusual timing, it is 30 minutes earlier.I didn't notice it -> came to contest 20mins late -> only managed to code and solve F1 5mins after contest end! What a sad day.

It's probably better to put the corner cases in pretests:(.

Thank you for maliciously and intentionally adding the test "1 1" to systests. Hope you sleep well at night.

I want to also make a comment on the morality of this. Normally, pretests are deemed (socially, though not rigorously through some legislation) as some tests that should cover most of the problem, passing them rendering the contestant a feeling of almost completeness. Should there be a very specific case, almost tailored to the code of the contestant, that is a byproduct of the code they written (and the bugs coming from their ideology), that test would be made a system test.

Now, to get accepted on a problem, that usually means that the code you written is completely correct, as there are no visible or relevant flaws (this is though, not really the case when seeing unordered_map get TLE in systests).

To get Wrong Answer in one problem (or to give such a verdict to a participant), it means that.. they haven't solved the problem. The AC/WA system doesn't, thus, make a visible difference to those that almost solve a problem and those far from a solution.

So, to sum up, is it morally correct to deem a solution failing on such a

systemtest as "Incorrect", and to ruin the score and future rating of some participant as such?I agree with everything you said, our ideologies on systest are the same but I did not exclude the test "1 1" from the pretests intentionally. I will admit that it is entirely my mistake that that test is not inside the system tests. Actually there is a another strong test that isn't in sample which is $$$n=2000$$$ and $$$l=[2000,2000,\ldots]$$$.

I don't really want to write some long story about why this entire fuck up happened but I was not aware that the test would cause many FSTs since no tester had that bug and my other pretests were used to kill some other scam related to DnC.

During the contest I seriously considered removing that from the systest and manually add the test afterwards via hacks since I agree it's not very nice to FST due to some trivial bug. But in the end, I made no changes to the systest.

I think you misunderstand what pretests and systests are on codeforces. When we prepare problems, we have to set systests and pretests. Because of the limitations of the judge, we can only set a small subset of tests to be the prestests. So the test "1 1" was in the systests

beforehand.I hope you understand this was a human error and its not like I intentionally wanted to see 20% of the contestants FST. I can tell you, no problemsetter wishes to see 20% of the contrestants FST.

Possibly my exprimation was a bit cloudy: I meant that failing system tests is usually because of some very tiny detail that may only occur in one or tso codes.

Nevertheless, what can I say besides that I am also sorry that this happened. It is really a shame when to a very well prepared and qualitative contests something like this happens. In any case, keep up the good work (but not the systests)

SpoilerThank you for assuming that "solving" means to think through a problem and thrn ironising that fapt.

Ok, my turn:

Thank you. For so long, I had a wrong perspective on systests, but now that I check, I observed that more than half of those that FST'ed wrote the exact same code as you. They definitely deserve it. In a programming competition, the way you write your code matters. Now I understand this view.

Sincerely,

Thank you author, after 18 months practicing on codeforces, now I have become master now, and will reach 2200+ rating, with

only pythonlanguage. So excited !Maybe I should write a blog on how to practice in codeforces with python language and avoid TLE, anyone interested?

Excellent work! I would absolutely love to read your blogs, please let me know if you end up writing them.

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

so i see that in problem B, if we replace every

`A`

with a`(`

and every`B`

with a`)`

, it becomes a "valid bracket sequence problem", why the solution works for both, can anyone elaborate ?, thanks in advance.It's not exactly the same though, you can have more A's than B's, but the idea is similar

CF is the most right place for political manifests!!

rainboy was the first one to solve problem I, I just want to know why he does not skip problems from back and solve other problems? Even in Global contests.

It's not about rating, it's about sending a message

what a message ?

Problem F1 be like I would like to explain the concept of derangement of a permutation.

Examples: A derangement of 1 2 3 can be 3 1 2, but 3 2 1 is not a derangement of 1 2 3 because 2 is still in its correct position.

Sometimes for an array, a derangement is not possible. Let us take an example.

Consider the array of numbers 1 2 1. Try writing the remaining permutations of this array, at least 1 element will retain its position.

Statement: If an element occurs more than 'half the size' number of times in an array then the derangement of that array is not possible.

Proof: Consider, an array of n elements. If there exists an element with a frequency that is greater than n / 2(take it as real division). Then the given array cannot be deranged because if we pick that particular element and try filling the remaining numbers into its original position, we will run out of numbers. For example, in the case of 1, 2, 2, 2, 3 In order for 2 to not be in its original set of positions, we need 1 and 3, which are the remaining distinct elements in the array, to fill in for 2. But there are 3 positions and only 2 numbers to occupy, hence every position will not be occupied, hence no derangement is possible. That concludes our proof.

When a derangement is possible, how do we construct it? Consider the case when elements are sorted. If we calculate the maximum frequency that a number has in an array, we can rotate the array by that amount and get the derangement of the given sorted array.

How is that possible?

Consider the n elements of a sorted array, a1, a2, ....., an. If we rotate the array by the maximum frequency, we are sure that the elements with the maximum frequency are not going to retain their original position as the series of similar numbers will be shifted ahead. For example, if we have, 1, 1, 2, 2, maximum frequency here is 2 and rotating by 2 yields 2, 2, 1, 1. In the forward direction, the ones are all ahead of the last one in the original permutation. So, in the forward direction, the array has kind of shifted right. No element will retain its position. You can try rotating 1, 1, 2, 2, 2, 3 by 3 to get a better feel or try out as many examples you want. As long as derangement is possible, and you rotate the array by maximum frequency, the new permutation of that sorted array is deranged.

Now how does this help in deranging an unsorted array? Simple, when you sort the array, keep the positions of each occurrence of the number with it. For example, for the array 1, 1, 6, 7, 8, 9, 1, 2, 2 the sorting would be (1, 1), (1, 2), (1, 7), (2, 8), (2, 9), (6, 3), (7, 4), (8, 5), (9, 6). Now when you rotate the sorted array by the maximum frequency, you will get the derangement of the sorted array, not of the actual one. So, keep an auxiliary array of the same size and go through the sorted array that stored the indices, sequentially from beginning and fill that index of the auxiliary array with the value of the rotated array that is equal to that retained index alongside the value(in the sorted array that is not rotated, look at the example). In a way, you are using the derangement of the sorted array to fill in the position of the numbers in the unsorted array. Let us consider an example. The array is 2, 1, 1, 2, 1, 3, 4, 5. If we sort the array and retain the indices, we have (1, 2), (1, 3), (1, 5), (2, 1), (2, 4), (3, 6), (4, 7), (5, 8). Now since the maximum frequency is 3(1 occurs thrice), we rotate this sorted array by 3, based on the first element. We now get, 3, 4, 5, 1, 1, 1, 2, 2.

3 goes to position 2 as in the corresponding array, the element is (1, 2)

4 goes to position 3 as in the corresponding array, the element is (1, 3)

5 goes to position 5 as in the corresponding array, the element is (1, 5)

1 goes to position 1 as in the corresponding array, the element is (2, 1) and, so on.

We get the following output, 1, 3, 4, 1, 5, 1, 2, 2 which is a derangement. If you observe carefully, the sorted version is just being modified, if a number x comes in position of y in case of sorted array, it just replaces y in its position in case of an unsorted array.

You didn't solve the problem. You just got lucky. There is nothing special about deranegements. Let $$$a=[1,2,3,4]$$$. A derangement is $$$b=[2,1,4,3]$$$ but it only has sadness $$$2$$$. Although your construction indeed works, the justification is totally wrong.

If you forget where you can see Global Rounds 2022 standings then I remind https://clist.by/standings/codeforces-global-rounds-2022-34697905/

The main idea of Problem G is the actually the same as this problem.

I'm so dumb that I didn't read the problem during contest...

Thanks

Did you use ideone? Is there any way your code could have been leaked without you knowing? Those solutions are absolutely identical, only the variable names have been changed, so it's not surprising they have been flagged.

How can I know who will get the prize?

Congratulation to Candydate Master SpadeA261.

Orange in unofficial list and purple in official lol

Today is truly a Candy Date. :D

ค้ค้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้

Unofficial T-shirt winners list (FINAL)Well, it looks like enough time has passed and the standings have been finalized, yet the official winners list hasn't been released yet, so it's time to

~~farm contribution~~post the unofficial list again!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,`1672`

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

It took a bit longer than usual, but congratulations to tshirts winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.

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

get_tshirts.pyrandgen.cpp