errorgorn's blog

Codeforces Global Round 20
By errorgorn, 3 years ago, In English

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

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.

Announcement of Codeforces Global Round 20
  • Vote: I like it
  • +861
  • Vote: I do not like it

Comments Comments (139)
| Write comment?
»
3 years ago, # |
  Vote: I like it +156 Vote: I do not like 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.

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

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

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

    Why is gravity not having effect on your glasses?

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

      Pikachu is pulling it up with electric force

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

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

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

    No offence though

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

Is it possible to advance the start time of the contest to start at 13:00 UTC such that it does not overlap with the HackerEarth Circuits April'22 contest which starts at 16:00 UTC?

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

How do you become a tester as an unrated user?

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

unusual timings not so usual nowadays.

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

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

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

    Could you please tell what contest is SRM828?

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

      Top coder single round match?(topcoder.com)

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

      I'd also like to know about GR20 please

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

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

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

As a tester, good luck.

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

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

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

    Just post the editorial then :)

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

As a tester, screw you maomao90

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

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!

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

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

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

Good luck to everyone!

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

This contest will be my first step toward a sacred goal

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

9 problems and 3 hours! This will be tough

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

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

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

Eat Sleep get positive rating repeat

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

So Many contests back to back. Contest after iftar and My condition...

6dj9ns

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

I hope I could get to 1500 again after this contest

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

As a stupidest tester, GLHF everyone :3

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

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

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

Is it rated?

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

    It is rated for everybody as mentioned in the blog.

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

No permutation problems since errorgorn is an author? :)

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

Congratulations rotavirus early-morning-dreams

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

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

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

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

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

errorgorn thanks for the round!

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

Congratulations early-morning-dreams and rotavirus...

মানুষের সুখ কখনও চিরস্থায়ী হয় না, একদিন না একদিন তার বিয়ে হয়ে যায়...

May the joy of your new life be filled with laughter, smiles, kisses, hugs, respect, understanding, and faithfulness...

Happy Wedlock!

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

Should beginners take part in global contests?

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

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

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

    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.

    Example

    AC Submission after typecasting

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

Congratulations rotavirus and early-morning-dreams

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

Is this contest Rated?

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

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

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

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.

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

WAon2Forces :(

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

    swe

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

      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)

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

    HackedForces :(

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

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

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

Welcome Codeforces! I am mister Bebra.

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

ConstructiveForces

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

I just wanna say that problem C was Evil

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

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

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

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

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

How to solve E?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Insert AB
    Insert AAB at position 2, making the string AAABB
    Insert AB at position 3, making the string AAABABB

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

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

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

    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

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

    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

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

    You can make it by

    A_B

    AAAB_B ->inserting AAB

    AAABABB ->inserting AB

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

    No, it shouldn't. A A B -> A A A B B -> A A A B A B B

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

F1 was fun to try, but I couldn't do it after an hour. Hope to learn from solutions, good round!

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

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

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

    yes, I want to know as well

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

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

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

    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 randomly try what I described above. Was surprised to see AC.

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

    Try testcase like 

    4
1 2 1 1 
1 1 2 1

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

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

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 function

submission link : https://mirror.codeforces.com/contest/1672/submission/154765626

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

    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.

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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.

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

Too many FSTs in E afraid me :(

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

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.

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

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

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

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

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

    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 system test as "Incorrect", and to ruin the score and future rating of some participant as such?

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

      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.

      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.

      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.

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

        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)

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

        Thank 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,

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

Thank you author, after 18 months practicing on codeforces, now I have become master now, and will reach 2200+ rating, with only python language. So excited !

Maybe I should write a blog on how to practice in codeforces with python language and avoid TLE, anyone interested?

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

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

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

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

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

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.

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

    It's not exactly the same though, you can have more A's than B's, but the idea is similar

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

CF is the most right place for political manifests!!

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

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.

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

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

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

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.

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

    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.

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

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

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

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

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

Thanks

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

    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.

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

How can I know who will get the prize?

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

    Congratulation to Candydate Master SpadeA261.

    Orange in unofficial list and purple in official lol

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

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

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

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

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

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 1672 1 ecnerwala
2 1672 2 tourist
3 1672 3 maroonrk
4 1672 4 snuke
5 1672 5 ksun48
6 1672 6 DearMargaret
7 1672 7 potato167
8 1672 8 Vercingetorix
9 1672 9 Endagorion
10 1672 10 hank55663
11 1672 11 jiangly
12 1672 12 QAQAutoMaton
13 1672 13 djq_cpp
14 1672 14 Petr
15 1672 15 pashka
16 1672 16 maspy
17 1672 17 Rewinding
18 1672 18 Maksim1744
19 1672 19 hos.lyric
20 1672 20 ugly2333
21 1672 21 Amoo_Safar
22 1672 22 hehezhou
23 1672 23 TLEwpdus
24 1672 24 Ormlis
25 1672 25 QuietBeautifulThoughts
26 1672 26 mango_lassi
27 1672 27 sumitacchan
28 1672 28 AndreySergunin
29 1672 29 Laurie
30 1672 30 rama_pang
53 1672 53 budalnik
96 1672 96 18Michael
148 1672 148 caoyue
171 1672 171 0wuming0
186 1672 186 ShuiLaoshi
231 1672 231 orz_dengyaotriangle
250 1672 250 temp06
252 1672 252 BARBARIANNNNN
271 1672 271 oreo816
301 1672 301 davidlee1999WTK
307 1672 307 L7-56
386 1672 385 Pidaxing
388 1672 388 SpadeA261
418 1672 418 Thrasio
419 1672 419 Ami_Nafi
439 1672 439 I_love_Michel_Sardou
444 1672 444 laundaryman
448 1672 448 m_99
454 1672 453 WUST_KING
499 1672 499 Grigori

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

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

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.py
randgen.cpp
List place Contest Rank Name
1 1672 1 ecnerwala
2 1672 2 tourist
3 1672 3 maroonrk
4 1672 4 snuke
5 1672 5 ksun48
6 1672 6 DearMargaret
7 1672 7 potato167
8 1672 8 Vercingetorix
9 1672 9 Endagorion
10 1672 10 hank55663
11 1672 11 jiangly
12 1672 12 QAQAutoMaton
13 1672 13 djq_cpp
14 1672 14 Petr
15 1672 15 pashka
16 1672 16 maspy
17 1672 17 Rewinding
18 1672 18 Maksim1744
19 1672 19 hos.lyric
20 1672 20 ugly2333
21 1672 21 Amoo_Safar
22 1672 22 hehezhou
23 1672 23 TLEwpdus
24 1672 24 Ormlis
25 1672 25 QuietBeautifulThoughts
26 1672 26 mango_lassi
27 1672 27 sumitacchan
28 1672 28 AndreySergunin
29 1672 29 Laurie
30 1672 30 rama_pang
53 1672 53 budalnik
96 1672 96 18Michael
148 1672 148 caoyue
171 1672 171 0wuming0
186 1672 186 ShuiLaoshi
231 1672 231 orz_dengyaotriangle
250 1672 250 temp06
252 1672 252 BARBARIANNNNN
271 1672 271 oreo816
301 1672 301 davidlee1999WTK
307 1672 307 L7-56
386 1672 385 Pidaxing
388 1672 388 SpadeA261
418 1672 418 Thrasio
419 1672 419 Ami_Nafi
439 1672 439 I_love_Michel_Sardou
444 1672 444 laundaryman
448 1672 448 m_99
454 1672 453 WUST_KING
499 1672 499 Grigori
→ Reply