You are not logged in. Please login at www.codechef.com to post your questions!

×

CHSIGN - editorial

4
2

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

  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$.
  4. But wait, it seems familiar!
  5. $B[1] + B[2] + B[3] + B[4] = (B[1] + B[2]) + (B[3] + B[4]) > 0 + 0 = 0$
  6. $B[2] + B[3] + B[4] + B[5] = (B[2] + B[3]) + (B[4] + B[5]) > 0 + 0 = 0$
  7. ...
  8. $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$
  9. In other words, by inspecting all substrings of length 2, we can automatically check all substrings of length 4 has positive sum.
  10. 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
  11. ...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.

This question is marked "community wiki".

asked 20 May '18, 14:15

tncks0121's gravatar image

2★tncks0121
13211
accept rate: 0%

edited 22 May '18, 18:19

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 20 May '18, 16:19

pieliedie's gravatar image

5★pieliedie
1044
accept rate: 20%

edited 20 May '18, 16:23

1

Thanks, fixed :D

(21 May '18, 05:37) tncks01212★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,631
×2,165
×1,668
×106

question asked: 20 May '18, 14:15

question was seen: 2,591 times

last updated: 22 May '18, 18:19