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
1988C - Increasing Sequence with Fixed OR
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Proof_by_QED | 146 |
| 3 | Um_nik | 146 |
| 5 | Dominater069 | 144 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
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.
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 |
|---|


