Thanks for participation!
The official solution of E is $$$O(n)$$$. If your solution of E has a larger complexity, I recommend reading the tutorial.
Hint 1
Solution
Hint 1
Hint 2
Solution
1988C - Increasing Sequence with Fixed OR
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Editorial of Codeforces Round 958 (Div. 2)
Thanks for participation!
The official solution of E is $$$O(n)$$$. If your solution of E has a larger complexity, I recommend reading the tutorial.
The optimal sequence of operations is very simple.
The optimal sequence of operations is adding $$$k-1$$$ 1-s into the set each time, at the same time decreasing $$$n$$$ by $$$k-1$$$. This implies that the answer is $$$\lceil \frac{n-1}{k-1}\rceil$$$.
I failed to find a Div2-A level proof. If you have a simpler proof please share it in the comments.
Consider the number of elements that is $$$\equiv 1\pmod{(k-1)}$$$ in the set. The number of such elements increase by at most $$$k-1$$$ in each operation, and the aforementioned sequence of operation achieves the maximum increment.
"Most sequences" can be transformed into $$$[1]$$$. Conditions for a sequence to be un-transformable is stringent.
Find several simple substrings that make the string transformable.
We list some simple conditions for a string to be transformable: - If 111 exists somewhere (as a substring) in the string, the string is always transformable. - If 11 appears at least twice in the string, the string is always transformable. - If the string both begins and ends with 1, it is always transformable. - If the string begins or ends with 1 and 11 exists in the string, it is always transformable.
These can be found by simulating the operation for short strings on paper.
Contrarily, if a string does not meet any of the four items, it is always not transformable. This can be proved using induction (as an exercise).
1988C - Increasing Sequence with Fixed OR
Rev. | Lang. | By | When | Δ | Comment | |
---|---|---|---|---|---|---|
en21 | feecIe6418 | 2024-07-16 07:22:51 | 6 | |||
en20 | feecIe6418 | 2024-07-16 05:49:22 | 62 | |||
en19 | feecIe6418 | 2024-07-16 05:48:50 | 1091 | |||
en18 | feecIe6418 | 2024-07-15 19:36:12 | 122 | Tiny change: ' tutorial.\n\n[probl' -> ' tutorial. Also,\n\n[probl' (published) | ||
en17 | feecIe6418 | 2024-07-15 17:12:46 | 43 | |||
en16 | feecIe6418 | 2024-07-15 17:12:02 | 923 | |||
en15 | feecIe6418 | 2024-07-15 17:05:36 | 312 | |||
en14 | feecIe6418 | 2024-07-15 17:04:24 | 393 | |||
en13 | feecIe6418 | 2024-07-15 17:03:42 | 157 | |||
en12 | feecIe6418 | 2024-07-15 17:02:35 | 15252 | |||
en11 | feecIe6418 | 2024-07-15 16:59:21 | 134 | |||
en10 | feecIe6418 | 2024-07-15 16:57:35 | 1017 | |||
en9 | feecIe6418 | 2024-07-15 16:53:24 | 1847 | |||
en8 | feecIe6418 | 2024-07-15 16:46:51 | 2079 | |||
en7 | feecIe6418 | 2024-07-15 16:42:33 | 578 | |||
en6 | feecIe6418 | 2024-07-15 16:30:06 | 1300 | |||
en5 | feecIe6418 | 2024-07-15 16:24:51 | 2 | Tiny change: 'ormable:\n- If 111' -> 'ormable:\n\n- If 111' | ||
en4 | feecIe6418 | 2024-07-15 16:24:30 | 949 | |||
en3 | feecIe6418 | 2024-07-15 16:15:07 | 330 | |||
en2 | feecIe6418 | 2024-07-15 16:12:20 | 15390 | |||
en1 | feecIe6418 | 2024-07-15 16:08:28 | 15298 | Initial revision (saved to drafts) |
Name |
---|