PROBLEM LINK:
Author: Ivan Safonov
Tester: Suchan Park
Editorialist: Suchan Park
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Simple dynamic programming
PROBLEM:
You are given a sequence of positive integers A_1, A_2, \cdots, A_N. You are allowed to negate some elements, as long as the sum of any substring of length \ge 2 is positive. Your goal is to do this job to minimize the total sum of the resulting sequence.
QUICK EXPLANATION:
It is sufficient to check substrings of length 2 and 3. Therefore, when we decide what should be the sign of A_i, we need to think about only A_{i-2 .. i+2}. Define \texttt{minSum}[i, suffix] as the minimum sum of the resulting sequence, when the sequence was A_{1..i} and the sign of the last 2 elements are suffix. Possible $suffix$es are ++, +- and -+, and you can find an obvious recurrence. After that, reconstruct the answer by storing how the transitions happened, or recalculate the transitions and find the suitable position.
EXPLANATION:
Before diving in to finding the optimal solution, let’s find an efficient way to find whether a given sequence B satisfies the condition “the sum of any substring of length \ge 2 is positive.” In other words, we have to check whether all of these conditions should be satisfied:
- any substring of length 2 has positive sum
- any substring of length 3 has positive sum
- any substring of length 4 has positive sum
- …
- any substring of length N-1 has positive sum
- any substring of length N has positive sum
If we do it naively, we need to check at least O(n^2) pairs (since there are that amount of substrings) and it is too slow. Let’s analyze what the naive algorithm is doing.
- any substring of length 2 has positive sum: This is equivalent to B[1] + B[2] > 0, B[2] + B[3] > 0, B[3] + B[4] > 0, …, B[n-1] + B[n] > 0.
- any substring of length 3 has positive sum: This is equivalent to B[1] + B[2] + B[3] > 0, B[2] + B[3] + B[4] > 0, B[3] + B[4] + B[5] > 0, …, B[n-2] + B[n-1] + B[n] > 0.
- any substring of length 4 has positive sum: This is equivalent to B[1] + B[2] + B[3] + B[4]> 0, B[2] + B[3] + B[4] + B[5] > 0, …, B[n-3] + B[n-2] + B[n-1] + B[n] > 0.
- But wait, it seems familiar!
- B[1] + B[2] + B[3] + B[4] = (B[1] + B[2]) + (B[3] + B[4]) > 0 + 0 = 0
- B[2] + B[3] + B[4] + B[5] = (B[2] + B[3]) + (B[4] + B[5]) > 0 + 0 = 0
- …
- B[n-3] + B[n-2] + B[n-1] + B[n] = (B[n-3] + B[n-2]) + (B[n-1] + B[n]) > 0 + 0 = 0
- In other words, by inspecting all substrings of length 2, we can automatically check all substrings of length 4 has positive sum.
- any substring of length 5 has positive sum: We can use the same argument above: Since 5 = 2 + 3 and we checked all substrings of length 2 and length 3, we can automatically check this condition
- …and further: We can make any natural number by adding 2s and 3s.
In short, we know whether the condition is correct by inspecting only substrings of length 2 and length 3. This means, when we decide whether A_i becomes negative or not, we only need to consider A_{i-2..i+2}. Specially, if i = N, we only need to consider A_{N-2} and A_{N-1}. It immediately suggests a dynamic programming solution. We should define a recurrence like this:
- \texttt{minSum}[i, p, q]: minimum sum of the resulting sequence, when the sequence was A_{1..i} and the sign of A_{i-1} is p and the sign of A_{i} is q.
For example, \texttt{minSum}[5, +, -] means the sum of the resulting sequence by somehow negating some elements of A_{1..5}, and A_{4} is not negated and A_{5} is negated.
The base cases are:
- \texttt{minSum}[2, +, +] = A[1] + A[2]
- \texttt{minSum}[2, +, -] = \begin{cases}A[1] - A[2],& \text{if } A[1] - A[2] > 0 \\ \infty, & \text{otherwise} \end{cases}
- \texttt{minSum}[2, -, +] = \begin{cases}-A[1] + A[2],& \text{if } -A[1] + A[2] > 0 \\ \infty, & \text{otherwise} \end{cases}
After that, let’s try to write all 8 = 2^3 possible signs of 3 last elements, and find the transitions between states.
For simplicity, I ommitted states with two continuous - signs. Now, what we have to do is, to check whether the sums of last 2 and 3 elements (changed signs according to the table above) are all positive, and if it is true substitute the value of ‘before’ to ‘after’.
After filling the table for all 2 \le i \le N, we have to reconstruct the answer. This can be done, by storing which transitions was used to construct the optimal sequence, by making an additional array \texttt{rev}[i,p,q]. For example, if the transition of the 4-th row is used (\texttt{minSum}[i-1, +, +] + A[i] \rightarrow \texttt{minSum}[i, +, -]), store ‘+,+’ to \texttt{rev}[i, +, -]. Then, from i = N down to i = 2, we can track how the transitions were made, and assign the signs according to q. In pseudocode:
i = N
p, q = (best p, q that gives optimal sum)
while(i >= 3) {
sign of A[i] is q.
(p, q) = rev[i, p, q]
i = i - 1
}
sign of A[1] is p.
sign of A[2] is q.
Or, since there are only a handful amount of transitions, we can just recompute all the possible transitions and pick the best one. For example, if we are at (i, -, +) and trying to find (i-1, ?, ?), there are only two possiblities: (i-1, +, -) and (i-1, +, +). Compute each of the values, and find one that matches with the optimal sum. The solution down there is implemented in this way.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.
