Hint
Hint
Solution
Hint
Solution
1839C - Insert Zero and Invert Prefix
Hint
Hint
Hint
Solution
Hint
Hint
Solution
Hint
Hint
Hint
Hint
Solution
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Codeforces Round #876 (Div. 2) Editorial
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$$$.
Rev. | Lang. | By | When | Δ | Comment | |
---|---|---|---|---|---|---|
ru3 |
![]() |
valerikk | 2023-06-03 20:11:15 | 0 | (опубликовано) | |
ru2 |
![]() |
valerikk | 2023-06-03 20:10:56 | 1 | Мелкая правка: 'и первых $$n - 1$ эл' -> 'и первых $n - 1$ эл' | |
ru1 |
![]() |
valerikk | 2023-06-03 20:10:05 | 2044 | Первая редакция перевода на Русский (сохранено в черновиках) | |
en11 |
![]() |
valerikk | 2023-06-03 20:01:08 | 0 | (published) | |
en10 |
![]() |
valerikk | 2023-06-03 19:56:50 | 2 | Tiny change: 'oiler>\n\n[probl' -> 'oiler>\n\n\n[probl' | |
en9 |
![]() |
valerikk | 2023-06-03 19:54:30 | 17 | Tiny change: 'each round, connect ' -> 'each round of the game, connect ' | |
en8 |
![]() |
valerikk | 2023-06-03 19:53:26 | 615 | ||
en7 |
![]() |
valerikk | 2023-06-03 19:47:24 | 45 | ||
en6 |
![]() |
valerikk | 2023-06-03 19:46:39 | 298 | ||
en5 |
![]() |
valerikk | 2023-06-03 19:43:25 | 46 | ||
en4 |
![]() |
valerikk | 2023-06-03 19:42:14 | 415 | ||
en3 |
![]() |
valerikk | 2023-06-03 19:39:38 | 172 | ||
en2 |
![]() |
valerikk | 2023-06-03 19:37:02 | 18 | ||
en1 |
![]() |
valerikk | 2023-06-03 19:36:22 | 371 | Initial revision (saved to drafts) |
Name |
---|