Tlatoani's blog

By Tlatoani, 7 months ago,

We hope all of you enjoyed the round! This round has been a long time in the making -- the oldest problem in it is H, which was actually originally proposed for the rounds that eventually became Codeforces Round #655 (Div. 2) and Codeforces Global Round 10.

The tutorial for E and implementations for all problems are now available.

A - Windblume Ode
B - Omkar and Heavenly Tree
C - Omkar and Determination
D - Omkar and the Meaning of Life
E - Moment of Bloom
F - Defender of Childhood Dreams
G - Omkar and Time Travel
H - Omkar and Tours
I - Omkar and Mosaic

• +349

By Tlatoani, 21 month(s) ago,

We hope you liked the problems! We apologize for the weak pretests for A and B -- that was a major oversight on our part. Hopefully you were still able to enjoy the contest regardless :)

We have to apologize to antontrygubO_o a bit here -- the rejection count mentioned in the editorial for Codeforces Round #655 (Div. 2) actually also included this round, as the problems from that round and problems A through G in this round were created together. We did have one more problem rejected after that round happened, bringing up the total to 73. For reference, here are the overall rejection counts for each problem:

Rejection Counts

Without further ado, here are the tutorials for each of the problems:

Solution (Kotlin) by golions
Solution (Java) by MagentaCobra
Solution (C++) by hugopm

Idea: MagentaCobra and qlf9

Preparation: MagentaCobra

Solution (Kotlin) by Tlatoani
Solution (Java) by MagentaCobra
Solution (C++) by tfg

Idea: MagentaCobra

Preparation: MagentaCobra

Solution (Kotlin) by Tlatoani
Solution (Java) by qlf9
Solution (C++) by tfg

Idea: qlf9

Preparation: qlf9

Solution (Kotlin) by Tlatoani
Solution (Java) by qlf9
Solution (C++) by Ari

Idea: Tlatoani

Preparation: Tlatoani

Solution (Kotlin) by Tlatoani
Solution (Java) by golions
Solution (C++) by hugopm

Idea: Tlatoani

Preparation: Tlatoani and golions

EDIT: The fact that the order of operations doesn't matter turned out to be harder to prove than I thought (thanks to the comments for pointing this out), so I decided to add the following proof:

If you have two sequences of maximal operations, then what we want to show is that they have to consist of the same operations (possibly in different orders). Since they are both maximal, they must either both be empty or both be nonempty. If they are both empty then we are done.

If they are both nonempty: consider the current state of the vector (before applying either sequence of operations). Since the sequences are nonempty, there is at least one operation $\alpha$ that can be immediately applied on the vector.

Here we should make the observation that applying an operation at some index cannot prevent operations at other indexes from being able to be applied (it can only allow other operations to be applied).

Therefore, applying other (different) operations cannot prevent operation $\alpha$ from being able to be applied, so operation $\alpha$ must occur in both sequences. From our observation, we can see that if, in either sequence, operation $\alpha$ does not occur initially, then operation $\alpha$ can be applied initially because by performing it earlier we are not preventing any of the operations in between from being applied.

Thus, the first operation of each sequence is now the same, so we can apply the same argument to the remainder of the sequence (since it must be finite).

Solution (Kotlin) by Tlatoani
Solution (Java) by qlf9
Solution (C++) by Devil

Idea: Tlatoani

Preparation: Tlatoani and qlf9

Solution (Kotlin) by Tlatoani
Solution (Java) by qlf9
Solution (C++) by mohammedehab2002

Idea: Tlatoani

Preparation: Tlatoani

Solution (C++) by zscoder
Solution (Java) by qlf9
Solution (Kotlin) by Tlatoani

Idea: zscoder

Preparation: zscoder

Solution (C++) by KLPP

Idea: KLPP

Preparation: KLPP

• +214

By Tlatoani, 21 month(s) ago,

Hi!

On Aug/16/2020 17:35 (Moscow time) we will host Codeforces Global Round 10.

This is the fourth round of a 2020 series of Codeforces Global Rounds. The rounds are open and rated for everybody.

The prizes for this round are as follows:

• The top 30 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 are as follows:

• In each round, the top 100 participants get points according to this table.
• The final result for each participant is equal to the sum of the points they got in the four rounds where they placed the highest.
• The top 30 participants over all series get sweatshirts and place certificates.

Thanks to XTX for supporting the global rounds initiative in 2020!

The problems in this round were prepared by KLPP, zscoder, qlf9, golions, MagentaCobra, and me. We would like to give a huge thanks to the following people:

We had a lot of testers as the problemset of the round changed significantly throughout testing! As a result of the huge amount of feedback, we think that we've managed to make the round really high quality and hope that you'll enjoy it :)

You will be given 3 hours to solve 9 problems. The score distribution will be announced at some point in time before the contest starts. Good luck!

UPD: Score distribution:

500 — 750 — 1000 — 1500 — 2000 — 2500 — 3000 — 3500 — 4000

UPD: Editorial

UPD: System tests have finished. We hope you liked the problems! We apologize for the weak pretests on A and B — that was a major oversight on our part. Hopefully you were still able to enjoy the contest regardless :)

Congratulations to the winners!