Monogon's blog

Codeforces Global Round 12
By Monogon, history, 3 years ago, In English

¡Buenos días! (That's Spanish for "what's up homies")

On Dec/06/2020 17:35 (Moscow time) we will host Codeforces Global Round 12.

It is the sixth round of a 2020 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 2020:

  • 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 2020 supported the global rounds initiative!

The problems were written and prepared by smart Cuban Devil and stupid Americans fivefourthreeone and Monogon.

We would like to distribute our thanks equally to the following people who made this round possible.

You will have 3 hours to solve 8 problems (and 2 subtasks). If you want to lose rating, then we encourage you not to read all the problems.

May rating be distributed from each according to his ability, to each according to his needs!

UPD: Here's the score distribution. Good luck, have fun!

$$$500-750-(1000+750)-1750-2500-2750-3750-(2750+1750)$$$

UPD: Hope you enjoyed the problems! Editorial is posted.

UPD: System testing finished, congrats to the winners!

  1. Benq
  2. tourist
  3. jiangly
  4. IZONE
  5. ecnerwala
  6. Um_nik
  7. ksun48
  8. 244mhq
  9. maroonrk
  10. yosupo
Announcement of Codeforces Global Round 12
  • Vote: I like it
  • +1239
  • Vote: I do not like it

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

As a tester, Communism is a good and realistic economic and political system.

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

As a communist, Testing is a good way to contribute to competitive programming community.

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

    As a competative programmer, help me bring Monogon up to 200 contribution too.

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

      Greedy capitalist pig

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

        That's inswine! Please grant me hamnesty, for I wish to be a loyal comrade...

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

          Now that you edited your comment to request upvotes for me, the state, I will grant you hamnesty.

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

            I'm happy to see that this tail has a twist!

            It's great to see that I've been reborn into a SecondThread. Just minutes ago, I was a lowly HamString...

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

              OMG !! You are too close to become top contributor !!

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

            Woah, Nice flow of contribution right there. Which algo did you applied here Monogon??

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

      mission complete

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

    As a non-tester, I wish I knew more problemsetters to contact for testing.

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

    As a reader, I enjoy reading comments!!

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

How to improve contribution? Negative->positive

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

    Don't write comments like this.

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

      Ok.

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

      Did you actually remember his username from his 20 months old comment?!

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

        I think he first check my all comments why I have negative contribution and then he find it. actually the comment was 9 month ago and his post was 20 months ago

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

      I didn't understand why I am getting downvote for saying 'Ok'.

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

    You can break the ratism curse with good memes

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

An announcement written 4 days before the contest -> bad contest

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

As a tester,

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

I'm afraid I can't participate in it because I have to go back to school to have classes then :(

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

Since fivefourthreeone currently refuses to post here and gain contribution, please give him contribution!!

He is very orz and write problem good.

If you want to gain rating on this global round, upvote his posts!

https://codeforces.com/blog/entry/80268#comment-664350

https://codeforces.com/blog/entry/82050#comment-687962

https://codeforces.com/blog/entry/82288#comment-691417

https://codeforces.com/blog/entry/82468#comment-693597

https://codeforces.com/blog/entry/82468#comment-693602

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

    Forced Contribution xD

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

      Hey dude, same pinch!!!! I also keep my dp color same as that of my handle.

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

As a tester, give me contribution

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

I cannot wait for the opportunity to generously hand out rating to the needy in this upcoming Global Round!

I live to serve the community!

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

    I appreciate it, Agnimaster

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

      As a sole Java user myself, I appreciate YOU. :)

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

Why doesn't fivefourthreeone make a comment asking for contribution?

Because he doesn't have two!

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

"Your participation will directly contribute to the end of the long-standing Cuban-American rivalry."

You assumed there's an end :).

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

I actually anticipated an "As a problem setter ..." comment :(

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

    Contribution is overrated.

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

    Are you angry at Santa or Monogon? Why don't you and other members of your family have the santa hat on?

    Untitled.png

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

[deleted]

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

As a non-tester, give me negative contribution.

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

    Maybe, you should change it to "As a non-tester, give me non-negative contribution". xD

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

May the pretests be strong!

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

May the problem statements be short!

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

May the round remain rated forever!

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

I thought "Buenos días" is "Good morning" — from a terrible student failing Spanish Class xD

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

    Good Morning!

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

      Good morning . Congrats for 200 contribution.

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

        I think saying Congrats or Good morning is not the reason for downvote. What's wrong ?

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

          I have observed on codeforces people downvote by seeing your handle's colour. If you would have been red then even ur single "." can give you +50 upvotes.

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

I thought "what's up homies" in Cuba is said as "Que bola asere!"

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

As a tester ... ( You know what's next [^-^] )

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

As a tester, Monogon asked me to test just so I could write a comment in this blog saying that the problems are fun.

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

    As a setter, I can confirm that you are a tester and I forgot to update the tester list.

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

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

I feel bad for namanbansal013. He has negative contribution just because he made video editorials for some problems. Come on people, he ain't getting monetary benefits for making editorials. Neither has he posted some random shit "as a tester" comment (that doesn't make any sense) just to farm contribution in any of the rounds he tested. No tester should have negative contribution

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

Hope not to become expert again XD

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

I rarely write a comment but it is really annoying that people upvotes a comment just by seeing handle's colour

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

As a tester, Monogon asked me to test just so I could write a comment in this blog saying that the problems are fun.

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

Monogon is one of my favourite writers :)

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

Its weird how newbies and pupils most of the time gets downvoted because of their comments (which I agree are really bad sometimes) but from last few contests high rated beings just commenting literally anything like "As a tester" comments and still getting upvotes.

Like once errichto said- "This comment section is shit"

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

Congrats Monogon on 200 contribution!!

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

Whatafuck!!!

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

I am a newbie here and haven't given many contests yet. Can someone please explain what are subtasks that are mentioned in the above post. Does that mean we will have 10 questions in total?

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

    It means that 2 of the problems will be split into an easy version and a hard version.

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

Glad to see saurabhyadavz as a tester of this contest from my city.

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

The problems were written and prepared by smart Cuban Devil and stupid Americans fivefourthreeone and Monogon

That's harsh XD

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

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

    Downvote above comment and make downvoteception when someone click it

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

As a cuban, I am very proud of the cuban testers and writers & after living in "communism" for long time, I just wanna say that "It sucks" :)

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

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

    You can't improve if you don't participate in the contests :)

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

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

As a non-tester,I am pretty sad that I missed my chance to get contribution with saying "As a tester".

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

Monogon orz!

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

    We have actually prepared 2 entirely different problem-sets. One which Errichto will surely get huge +, and the other he will surely get huge -. The one we choose will depend on whether he gives in to my demands.

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

      7 geometry problems?

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

        Can you make some geometry videos in your YouTube channel ?

        Personally I think some of competitive programmers see the geometry as the hardest thing in CP

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

It should be: from each according to his ability, to each according to his work!

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

Hello Comrade Problem-setters. It pleases me greatly that rating redistribution will finally become a reality on Codeforces. I'd like to ask how exactly each user's need for rating will be determined.

Sincerely, Comrade Contestant Darcy

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

can i get some upvotes/contribution please , today is my birthday !!

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

Will the problems be available in Spanish?

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

"May rating be distributed from each according to his ability, to each according to his needs!" *his or her

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

This is the first global contest that I am going to participate in. Is a global contest harder than Div.2? Can you tell me the difference between a global round and other rounds? Also, is a global round rated for me?

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

    Global is rated for you. Typically, Globals are harder than Div. 2 because it is combined Div 1 and 2. Globals are known for their interesting high quality problems, although I'm not sure what differentiates them from regular Div. 1 + Div. 2.

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

For a Chinese primary school student, the start time is too late:(

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

    This is the usual start time on codeforces!

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

2 points left Monogon

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

Why Errichto didn't Host a single contest on Codeforces in last one year.

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

    Why do you think the default for me is to produce a CF contest every year? It takes new ideas and a lot of time.

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

Screenshot-2020-12-06-164243.png
Now this actually strikes chills down my spine

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

    Are you new to Global round ? Every global round has the same length of 3 hrs and total 8 problems (or maybe more)

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

Now all makes sense ... He's the emo spiderman.

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

    Why don't you all memers put your shitty memes inside spoilers. Just cluttering the comments section with shit

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

Well, hope the problems are not too difficult for me :)
By the way, when can we see the scoring distribution?

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

    Alright .. Maybe E is still too difficult for me, not feeling good :(

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

I can smell maths from here .

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

I hope I am not going to mess it up again.

Capture.png

→ Reply
»
3 years ago, # |
  Vote: I like it -61 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +4 Vote: I do not like it
  • Yesterday : Tourist win hackercup
  • Today : May be cross highest codeforces rating ( if all goes well )

Best weekend for tourist

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

For me, this round was very tough. I don't even solved B even after 3 hours :(

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

So I couldn't solve C1, but on the bright side, I figured out how to make a sound while breathing inwards by making monkey noises for the past 20 minutes!

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

I hate every contest with subtasks specially in the first 3 problems.

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

What is probability of a person like Me(an average mind) thinking the same puzzle in same way as a Red coder thinking randomly in his Leisure time?? is that 1/6e4 like that??

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

Solve F in 20 minutes Can't solve C2 or D in 2 hours.

How it works???

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

    I think a lot of people spent time with c or d so just a small group of contestans read problems up to F

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

    I am not sure of the system tests at the moment, but binary search worked for $$$D$$$, with just checking for $$$k = 1$$$ separately (actually I did check for the first $$$10$$$ arbitrarily). Find minimum $$$k$$$ for which the goodness holds, then all $$$k$$$'s till $$$n$$$ from this point will hold. Checking for a permutation is trivial, and sliding window minimum is also very standard.

    I hope system tests pass for me.

    I did find $$$C$$$ much harder than $$$D$$$ though.

    Update: Accepted
    Solution: 100575348

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

This is really tough problemset :|

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

How to solve C2?

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

    First, split the matrix on three groups:

    0120120
1201201
2012012
0120120
1201201
2012012
0120120

    where group[i][j]=(i+j)%3

    Then choose such two different groups where number of 'O' in the first group + number of 'X' in the second group <= k/3. Such pair of groups always exists. Finally, in the first group all 'O' replace by 'X' and in the second group all 'X' replace by 'O'

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

      I took all masks 1 <= mask <= 6(not all 0 and not all 1) and decided for each remainder MOD 3 of (i + j) what I want it to be(X or O). I simply computed how many cells I need to change and if it's enough, output. This doesn't always find solution and u can prove it by simple math. I didn't figure out that you could ignore one remainder. Oh well

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

Seriously now, who decides the difficulty for these contests?

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

    Apparently the difficulty permutation has quite a high cost.

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

Am I the only one who thinks problems like F are not very interesting? They are very guessable (I was very disappointed to find out that my random hunch about what the answer might be was entirely correct) and reduce to a small number of pretty typical greedy arguments. Although it is an ad-hoc problem (which can be promising), it still is not a very interesting problem to solve.

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

    What's your "easily guessable" hunch? I spent like at least half an hour in contest thinking of all the ways to get rid of dominant segment endings, before realising that most of them were no better than shoving them somewhere inside another segment and forgetting about them.

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

    well i think it shouldnt be the F problem. and also yes i think the hard part of the solution was to actually build the answer. if the problem wants the actual permutation it could be nice problem for F in my opinion.

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

      I don't know, that might be a quite painful implementation. But it would definitely redeem the guessability (and maybe the problem).

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

I Hate the Tic-Tac-Toe grid
UPD: after see the editorial., i understood that was a good learning problem. but c & d can be replace their place.

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

Interesting problem set, but I solved C1 and C2 in a very similar way to this problem

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

    I thought of that problem but could't find the relation, can you elaborate?

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

      Sure! In the other problem, you increase the numbers based on the parity of the sum i + j. In C1, you can do the same, but only for positions (i, j) that have (i + j) % 3 = 0. This does work, but sometimes can go over k / 3. So you can check all remainders and try to flip all position (i, j) that have (i + j) % 3 = r. C2 is very similar, I'll let you figure it out.

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

        Thanks, the editorial is also out and I can understand the relation now.

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

    Thanks for the reference, I also remember the similar problem but could not find it.

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

C1 and C2 spoiled this contest for me :-(

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

What the hell was up with this problem $$$C$$$ this time, huh?!
It has become hard these days to find a contest which feels fine in terms of difficulty distribution.

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

I loved the problemset, especially E was very interesting (for me, I have never seen such a reduction to shortest path before).

However, the contest was also very demoralising as I watch myself struggle to solve something more than a thousand people could do :(

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

Toughness == Trickyness

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

How do you solve C1?

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

That difficulty jump between B and C1 tho D:

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

Why not just call this a Division 1? Sucks when you bait contestants with a trivial A, and then bump up the difficulty level significantly (C appears to be insanely difficult). Oh well.

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

Me after coding all kinds of stupid stuff for C for 2 hours clown

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

Does greedily converting 'X' which provides most number of winning configs work in C1?

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

C2 was really beautiful.

Hint for those who are stuck:
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Used that for C1, couldn't prove that it'd work for C2. How to do that? I'm struck in this area.
    Color $$$0$$$ -> $$$2$$$ X, $$$2$$$ O, Color $$$1$$$ -> $$$2$$$ X, $$$2$$$ O, Color $$$2$$$ -> $$$2$$$ X, $$$2$$$ O

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

      Make sure that no cell with colour 1 contains a X, and no cell with colour 2 contains an O (or colours 2 and 3, or 3 and 1, with whichever one you need the least swaps).

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

During this contest, I proved strictly more than one of my solutions by stating "This sounds very elegant and passes pretests, QED".

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

    the difference between a mathematician and a programmer

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

    "And there is no hack in the first page"

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

I wish Lenin could participate in this round... Problem E ٩(╬ʘ益ʘ╬)۶

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

So, what did "antontrygubO_o for inspiration!" mean? I assumed some ideas for some problems ideas had come from antontrygubO_o, which is tiny (but nonzero) information, but I was kind of confused when I saw the standings showing that name.

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

Pretest seems to be made very strong by the preparers! Thanks!

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

I guess this contest is made only for Legendary Grandmasters. Difficulty level at its peak!

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

The hardest Tic-Tac-Toe ever

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

Tic-Damn-Toe

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

Any heuristic which passed C1/C2 (different from editorial)?

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

Problem D

If number of occurrences of some number (let's call it i) is 0 then all compressions for all k=1...n-i+1 aren't permutations

If number of occurrences of i more than 1 then all compressions for all k=1...n-i aren't permutations

If there are numbers to the left and to the right of i that both greater than i then all compressions for all k=2...n-i aren't permutations. For this checking do the cycle and keep l and r — left and right bounds of subsegment of array that is not considered yet. If position of current i is not equal to l+1 or r-1 then break the cycle. Else move the left or right bound.

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

    I used binary search + segment tree. have a look 100580701

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

      I didn't complete my implementation yet, but with sparse table it can be done even simpler and faster. Still using binary search of course.

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

      This is just 2-3 simple cycles, O(n)

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

    Coincides with my solution

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

As a contestant I want rating++

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

.

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

where r the rating changes XD

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

Have a look at those videos.A person uploaded videos during the contest... A- youtube.com/watch?v=oKA9mzrEkJU&ab_channel=AbhinavKumar B- https://www.youtube.com/watch?v=PyBte0lSc6I&t=73s&ab_channel=AbhinavKumar

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

It is a draw!

Capture187771b7393dba12.png

Spoiler

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

D saved this contest for me, phew.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
for C1 why this code is giving wrong ans
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I'm not sure , but in ~~~~~ if(cnt1<cnt2 and cnt1<cnt3) for(int i=0;i<n;i++) cout<<tvec1[i]<<endl; else if(cnt2<cnt1 and cnt2<cnt3) for(int i=0;i<n;i++) cout<<tvec2[i]<<endl; else for(int i=0;i<n;i++) cout<<tvec3[i]<<endl; ~~~~~ your ifs are wrong , because there is a possibility that cnt1 == cnt2 and cnt1 < cnt3 but your code will use 3 , while he should use 1 or 2.

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

    Idk where is the mistake, I was just curious whether I can find a WA in less than three attempts. Here is my very first attempt lol :D

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

Global rounds standings may look like https://clist.by/standings/codeforces-global-rounds-2020-18730990/.

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

Congratulations to the t-shirt winners!

List place Contest Rank Name
1 1450 1 Benq
2 1450 2 tourist
3 1450 3 jiangly
4 1450 4 IZONE
5 1450 5 ecnerwala
6 1450 6 Um_nik
7 1450 7 ksun48
8 1450 8 244mhq
9 1450 9 maroonrk
10 1450 10 yosupo
11 1450 11 snuke
12 1450 12 atomicenergy
13 1450 13 Rebelz
14 1450 14 tatyam
15 1450 15 Swistakk
16 1450 16 Egor
17 1450 17 hos.lyric
18 1450 18 kort0n
19 1450 19 sunset
20 1450 20 majk
21 1450 21 antontrygubO_o
22 1450 22 ugly2333
23 1450 23 Maksim1744
24 1450 24 stevenkplus
25 1450 25 hitonanode
26 1450 26 Amoo_Safar
27 1450 27 LayCurse
28 1450 28 _h_
29 1450 29 TeaPot
30 1450 30 KAN
32 1450 32 Golovanov399
85 1450 85 Savior-of-Cross
92 1450 92 sstrong
116 1450 116 Series_205
131 1450 131 Jimanbanashi
150 1450 150 Qing_Yang
155 1450 155 emorgan
184 1450 184 cuom1999
205 1450 204 goodbaton
218 1450 218 gangpenwang
239 1450 239 bekzhan29
249 1450 249 201831990439
290 1450 290 Ujimatsu
293 1450 293 AnotherRound
307 1450 307 Farhod
314 1450 314 BSBandme
327 1450 327 aytel
412 1450 412 arbuzick
414 1450 414 kalimm
415 1450 415 matt64
→ Reply