PROBLEM LINK:Author: Ivan Safonov Tester: Suchan Park Editorialist: Suchan Park DIFFICULTY:EasyMedium 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_{i2 .. 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 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:
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.
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_{i2..i+2}$. Specially, if $i = N$, we only need to consider $A_{N2}$ and $A_{N1}$. It immediately suggests a dynamic programming solution. We should define a recurrence like this:
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:
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 4th row is used ($\texttt{minSum}[i1, +, +] + 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:
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 $(i1, ?, ?)$, there are only two possiblities: $(i1, +, )$ and $(i1, +, +)$. 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.
This question is marked "community wiki".
asked 20 May '18, 14:15

The tester's solution has a link to the fake binary search problem's solution please fix it. This is the link to the solution by @tncks0121 answered 20 May '18, 16:19
