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$$$.

"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).

Formulate the problem.

Some variables can't be large.

Suppose monster $$$i$$$ is killed in round $$$b_i$$$. Then, the total health decrement is the sum of $$$a_i\times b_i$$$. The "independent set" constraint means that for adjacent vertices, their $$$b$$$-s must be different.

Observation: $$$b_i$$$ does not exceed $$$\lceil \log_2 n\rceil +1$$$. In this problem, $$$b_i\le 20$$$ always holds for at least one optimal $$$a_i$$$.

By dp, we can find the answer in $$$O(n\log n)$$$ or $$$O(n\log^2 n)$$$, depending on whether you use prefix/suffix maximums to optimize the taking max part.

Bonus: Find a counterexample for $$$b_i\le 19$$$ when $$$n=300000$$$. (Pretest 2 is one case)