NonZero PrefSuf Sums#12971

NonZero PrefSuf Sums (Editorial)

Author:

Anton Trygub

Solved by:

First to solve:

Fizičari

Let’s analyze when does array [a_1, a_2, \ldots, a_n] satisfy the conditions of the problem.

  1. If a_1+a_2+\ldots +a_n = 0, then it’s a NO. Now, assume a_1+a_2+\ldots+a_n>0 (otherwise just negate all elements).

  2. If array contains at most one nonzero value, it’s a NO.

  3. Let the sum of positive elements be , and the sum of negative elements be , with P>N. Denote S=P-N. If we order all positive elements first, and then all negative, then all prefix sums will be positive, so we only have to worry about suffix sums. Alternately, we only need to order positive elements so that no prefix sum equals exactly .

  4. If not all positive elements are equal, then it’s always possible to order positive elements in such a way, so it’s a YES. Indeed: assume there are some positive elements x\neq y. First, as many other positive elements as you can so that no prefix sum is . If we could order all of them, then we put in one order or another, making sure new prefix sum is also not . Otherwise, there are some elements remaining, but we can’t append any more without getting sum exactly , which means all remaining elements are equal to some . Then put or (whichever is \neq t), then , then all remaining positive elements: we successfully avoided .

  5. Now assume all positive elements are equal to some . If is not divisible by , we can still put all positive elements, and then all others, so in that case the answer is also YES. So now we assume that P, S, N are divisible by .

  6. Assume some negative number isn’t divisible by . Then let’s put first, then all s, then all remaining elements. Note that every prefix sum is either positive or not divisible by , and every suffix sum is also either negative or not divisible by , so the answer in this case is also YES.

  7. Otherwise, all numbers are divisible by . So let’s divide everything by , and assume that x = 1 from now on.

  8. Let’s think about the prefix sums a bit more deeply. We want each prefix sum (except the first and last one) to be \neq 0, S. They also start with , and end with . In addition, whenever prefix sums increase, they increase by exactly (since that’s the only positive elements we have). So, if they ever get negative, in order to get to , they would have to cross at some point.

  9. So, the arranging process looks as follows. We start with , and then at every step we can either use , increasing sum by , or use some negative number , decreasing sum by . We cannot ever get to or (except first or last position), so we have to always remain in the [1, S-1] range. So, if there exists some negative number <-(S-2), the answer has to be NO.

  10. It’s easy to see that otherwise such an arrangement always exists: just place s until sum doesn’t exceed S-1, and then use some negative number.

Now, we need to write for this. Once again, let’s break this down into small steps.

  1. Total number of arrays is (2m+1)^n.

  2. Calculate number of arrays \in [-m, m]^n with sum , you can do this in O(mn^2), subtract it.

  3. Need to calculate only number of bad arrays with positive sum (then multiply it by and subtract).

  4. Iterate over positive element . We know all elements have to be divisible by , so we need to solve the instance with positive elements equal to , and all elements now being in [-\frac{m}{x}, \frac{m}{x}].

  5. Iterate over: number of ones , and sum of negative elements with N<P. Then all negative elements have to be up to S-2=P-N-2. So, we need to count the number of arrays of length n-P of nonnegative numbers with sum with elements not exceeding P-N-2.

  6. We will use more general dp for this: dp[len][sum][lim]: the number of arrays of length with sum and all elements in [0, lim]. We can code this in O(MAXX^4), where MAXX = max(n, m). Indeed, transitions are simple: calculate values for from to , every time iterate how many values equal to you are adding.

Total runtime: max(m, n)^4 with a very good constant (can actually be done faster but we reduced constraints enough).