Ex - Negative Cost Editorial by en_translator
For convenience, we flip the signs of each \(C_i\) than the input so that move \(i\) increases the magic power by \(C_i\). Also, let \(L \coloneqq 300\) (the maximum absolute value of \(C_i\) under the constraints).
For a sequence of moves \(A = (a_1, a_2, \ldots, a_l)\), let us call \(\sum_{i = 1}^l C_{a_i}\) the balance of \(A\), and \(\sum_{i = 1}^l D_{a_i}\) its damage. Also, we call a sequence of moves \(A\) an effective sequence if all the balances of the prefixes of \(A\) are non-negative, that is, starting with a magic power of \(0\), all the moves in \(A\) can be sequentially made. This problem asks to find the minimum possible length of an effective damage with damage at least \(H\).
An effective sequence is said to be basic if all the balances of the prefixes of \(A\) are strictly less than \(2L\). A concatenation of effective sequences is obviously effective; especially, so is that of basic effective sequences.
Conversely, for any effective sequence \(A\), there is a concatenation of basic effective sequences that is equivalent to \(A\) (i.e. that has the same length and damage.)
Proof
On an effective sequence $A = (a_1, a_2, \ldots, a_l)$, consider swapping $a_{p+1}$ and $a_{p+2}$ as long as there is a $p$ such that $\sum_{i = 1}^p C_{a_i} \geq L, C_{a_{p+1}} \geq 0$, and $C_{a_{p+2}} \lt 0$. By the condition $\sum_{i = 1}^p C_{a_i} \geq L$ of the swapped elements, this swap does not spoil the effectiveness of the sequence. Let $B = (b_1, b_2, \ldots, b_l)$ be the resulting effective sequence when this procedure stops. Let $q$ be the maximum $i$ with $C_{b_i} \lt 0$; then $B$ is a concatenation of $(b_1, b_2, \ldots, b_q)$, and $(l-q)$ sequences of length $1$, $(b_{q+1})$, $(b_{q+2})$, $\ldots$, and $(b_l)$. By definition of $B$, these effective sequences are all basic.Moreover, any basic effective sequence \(A\) is equivalent to another of length at most \(2L\).
Proof
We show it by induction of the length. When $A = (a_1, a_2, \ldots, a_l)$ has the length of $(2L+1)$ or greater, then some $p$ and $q$ with $0 \leq p \lt q \leq 2L$ satisfy $\sum_{i = 1}^p C_{a_i} = \sum_{i = 1}^q C_{a_i}$ by the pigeonhole principle. Decomposing $A$ into two sequences $X \coloneqq (a_1, a_2, \ldots, a_p, a_{q+1}, a_{q+2}, \ldots, a_l)$ and $Y \coloneqq (a_{p+1}, a_{p+2}, \ldots, a_q)$, $X$ is a basic effective sequence shorter than $A$, so by the assumption of the induction, it is equivalent to a concatenation of several basic effective sequences, $W_1W_2 \ldots W_w$. Also, sorting $Y = (a_{p+1}, a_{p+2}, \ldots, a_q)$ in ascending order of $C_{a_i}$ preserve equivalence and effectiveness. As shown above, the resulting effective sequence is equivalent to a concatenation of some effective sequences, $Z_1Z_2\ldots Z_z$; since the length of $Y'$ is less at most $2L$, so are those of $Z_1, Z_2, \ldots, Z_z$. Therefore, $A$ is equivalent to a length-$2L$-or-less concatenation of basic effective sequences $W_1W_2 \ldots W_wZ_1Z_2\ldots Z_z$.Thus, this problem can be solved by considering concatenating basic effective sequences of length \(2L\) or less to make it have a damage of at least \(H\). Moreover, for \(i = 1, 2, \ldots, 2L\), it is sufficient to use the basic effective sequence \(A^{(i)}\) of length \(i\) with the maximum damage. The damage \(d_i\) of \(A^{(i)}\) for each \(i\) can be found with a dynamic programming (DP) where:
\(\mathrm{dp}[i][j] = \) (the maximum damage of a basic basic sequence of length \(i\) and balance \(j\))
in a total of \(O(NL^2)\) time.
Hence, this problem is boiled down to:
There are \(2L\) combos. For \(i = 1, 2, \ldots, 2L\), combo \(i\) costs \(i\) (i.e. needs \(i\) moves) and gives a damage of \(d_i\). Find the minimum total cost required to give a total damage of \(H\) or greater.
Take a combo with the maximum damage per cost \(d_i / i\), and let us call it the best combo. Intuitively, the best strategy to give much damage with fewer cost is to use the best combo as many times as possible. Actually, there is an optimal sequence of combo where the other combos are used less than \(2L\) times.
Proof
Let combo $z$ be the best combo. Consider a sequence of combos $V$ containing at least $2L$ non-best combos. By rearranging the combos, we can assume that the first $2L$ combos, thus the first $z$ combos, are not the best one. For $i = 0, 1, 2, \ldots, z$, let $s_i$ be the sum of costs of the first $i$ combos; then there are $i$ and $j$ with $0 \leq i \lt j \leq z$ and $s_i \equiv s_j \pmod{z}$ by the pigeonhole theorem. Then, replacing the $(i+1)$-th, $(i+2)$-th, $\ldots$, and $j$-th combos with $(s_j-s_i)/z$ copies of the best combo does not change the total cost of $V$ and reduce the total damage of $V$, while reducing the number of non-best combos in $V$.Therefore, we can assume that non-best combos are used strictly less than \(2L\) times.
Let us fix the total cost \(x\) for the non-best combos, and \(M_x\) be its maximum possible total damage; then the best combo should be made exactly \(\lceil (H-M_x) / d \rceil\) times, which can be computed in an \(O(1)\) time, where \(d\) is the damage of the best combo. Since the non-best combo is made less than \(2L\) times, and the cost of each combo is \(2L\) or less, so there are \(O(L^2)\) distinct candidates of \(x\). Thus, the optimal solution can be found in a total of \(O(L^2)\) time by brute-forcing all possible \(x\).
Additionally, \(M_x\) for all \(x\) that we need can be computed at once with a dynamic programming with the following DP table:
\(\mathrm{dp2}[i][j] =\) (the maximum total damage when combos \(1, 2, \ldots, i\) are made any number of times for a total cost of \(j\))
in a total of \(O(L^3)\), using the method of unbounded knapsack problem.
Therefore, the problem can be solved in a total of \(O(NL^2 + L^3)\) time.
posted:
last update: