1839C - Insert Zero and Invert Prefix
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
The first and last elements are always equal to $$$1$$$.
There are at least $$$\lceil \frac{n - 1}{k} \rceil$$$ ones among the first $$$n - 1$$$ elements.
Try to solve the problem if all $$$a_i$$$ are equal.
1839C - Insert Zero and Invert Prefix
After every operation, the last element of $$$b$$$ is equal to $$$0$$$.
If the last element of $$$a$$$ is $$$0$$$, then you can always achieve $$$b = a$$$ with some sequence of operations.
Try to solve the problem if $$$a$$$ consists of $$$k$$$ ones followed by single zero.
Consider the set of balls that were never moved by operations of type 2.
The relative order of these balls never changes, so their colors must form an increasing sequence.
Consider the graph with $$$n$$$ vertices $$$1, 2, \ldots, n$$$, and on each round of the game, connect vertices $$$i$$$ and $$$j$$$. What can you say about this graph?
This graph is a tree.
Vertices of a tree can be divided into two parts, such that all edges connect vertices from different parts.
If the second player won the game, then sums of elements in both parts were equal in initial array $$$a$$$.
Hello, Codeforces!
I invite you to participate in Codeforces Round 876 (Div. 2), which will be held on Jun/03/2023 17:35 (Moscow time).
The round will be rated for participants with rating lower than 2100. Participants with higher rating can participate in round unofficially.
You will be given 5 problems and 2 hours to solve them. I recommend you to read all problems. One of the problems will be interactive, so please read guide for interactive problems before the contest.
All problems are authored by me.
I would like to thank:
Score distribution: 500 — 1000 — 1500 — 2250 — 2750.
Good luck to all participants!
Editorial has been published.
Winners:
Unofficial winners:
First-to-solve:
Name |
---|