CHSIGN - editorial

dynamic-programming
easy-medium
editorial
may18

#1

PROBLEM LINK:

Practice

Contest

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 exttt{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.

  1. 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.
  2. 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.
  3. 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.
  1. 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
  2. …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:

  • exttt{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, exttt{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:

  • exttt{minSum}[2, +, +] = A[1] + A[2]
  • exttt{minSum}[2, +, -] = \begin{cases}A[1] - A[2],& ext{if } A[1] - A[2] > 0 \\ \infty, & ext{otherwise} \end{cases}
  • exttt{minSum}[2, -, +] = \begin{cases}-A[1] + A[2],& ext{if } -A[1] + A[2] > 0 \\ \infty, & ext{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 exttt{rev}[i,p,q]. For example, if the transition of the 4-th row is used ( exttt{minSum}[i-1, +, +] + A* \rightarrow exttt{minSum}[i, +, -]), store ‘+,+’ to exttt{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* 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.


#2

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


#3

Thanks, fixed :smiley:


#4

The editorial seems too complex, can someone explain it in a more simpler way?