MODSUB - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Prefix sums

PROBLEM:

You’re given an array A.
Count the number of indices i satisfying the following condition:

  • You’re allowed to replace A_i by any integer X.
  • After replacement, it should be possible to turn A into [0, 0, \ldots, 0] by performing the following operation repeatedly:
    • Choose an index i and subtract 1 from both A_i and A_{i+1}.

EXPLANATION:

Let’s analyze when a fixed array can be turned into [0, 0, \ldots, 0].

Looking at index 1, the only way to change the value of A_1 is to subtract 1 from A_1 and A_2 together.
This, of course, must be done exactly A_1 times to make A_1 become 0.
So we must have A_2 \ge A_1, since if it were smaller then A_2 would end up negative and can then never reach 0.

After doing this, we look at index 2.
Since index 1 already contains 0, now the only way to change the value at index 2 is to operate on indices 2 and 3.
The current value at index 2 is (A_2 - A_1), and thus we need A_2 - A_1 \le A_3 to hold for the final result to be possible at all.

Similar reasoning for further indices tells us that we need:

  • A_3 - A_2 + A_1 \le A_4
  • A_4 - A_3 + A_2 - A_1 \le A_5
    \vdots
  • A_i - A_{i-1} + A_{i-2} - \ldots + (-1)^{i+1} \cdot A_1 \le A_{i+1}

must hold for every 1 \le i \lt N.

For the very last index, since we must end up with all zeros, the criterion is instead

A_N - A_{N-1} + A_{N-2} - \ldots + (-1)^{i+1} A_1= 0

Note that all our conditions are dealing with alternating prefix sums here.
Specifically, let’s define Q_i to be the alternating prefix sum ending at index i, so that

Q_i = A_i - A_{i-1} + A_{i-2} - \ldots + (-1)^{i+1} A_1

Then, the conditions derived above tell us that we need:

  • Q_i \ge 0 for all 1 \le i \le N, and
  • Q_N = 0.

It’s easy to verify that these conditions are not just necessary, but also sufficient - that is, if they hold, then the array A can be brought to [0, 0, \ldots, 0] by performing the operation repeatedly.
The proof is simple, just perform operations greedily from left to right and see that the conditions are maintained.

Now that we can recognize “good” arrays, let’s try to solve the problem at hand.
Let’s first build the alternating prefix sum array Q of the input array.

Suppose we fix an index i, and we want to see if we can place some value X at this index to make the array “good”.

Observe that there’s only one possible candidate for the value of X.
This is because we must have Q_N = 0, and each element of the array contributes exactly one term to this alternating sum.
So,

  • If (N-i) is even, replacing A_i with X will add (X - A_i) to the value of Q_N.
    • Thus, we should choose X = A_i-Q_N, which will make Q_N + (X-A_i) = 0.
      Equivalently, we subtract Q_N from A_i.
  • If (N-i) is odd, replacing A_i with X will subtract (X - A_i) from the value of Q_N.
    • By similar reasoning, we instead need to choose X = A_i+Q_N here, or add Q_N to A_i.

After figuring out the value that must be placed at A_i, we need to then figure out if the resulting array is “good”.
The condition Q_N = 0 is already satisfied by our choice, so we only need to verify whether Q_j \ge 0 for all j.

Observe that:

  • For 1 \le j \lt i, the value of Q_j is completely unchanged.
    Thus, all of these must have been \ge 0 even initially.
    This can easily be checked by, for example, storing information of the leftmost negative element of Q.
  • For i \le j \le N, the value of Q_j changes depending on the parity of j.
    • If i and j have the same parity, Q_j increases.
    • Otherwise, Q_j decreases.

For now, suppose i is even.
Since for j \ge i the parity of j matters, we treat even/odd j separately.
Let D denote the value being added to A_i (which is either Q_N or -Q_N, depending on the parity of i compared to N.)

  • For all even j \ge i, we want to check if Q_j + D \ge 0.
    • Note that as long as the smallest Q_j satisfies this, all of them will.
    • So, we only need to know the smallest value of Q_j among all even j \ge i.
  • For all odd j \ge i, we want to check if Q_j - D \ge 0.
    • Again, it’s sufficient to check whether the smallest Q_j satisfies this.
    • So, we again only need to know the smallest value of Q_j among all odd j \ge i.

Thus, by simply storing information about the smallest even/odd Q_j for each suffix, the check at any given index can be performed in constant time - so we’re done.

One thing to note is that we need A_i \ge 0 for all i, since if some A_i \lt 0 then it surely can’t reach 0.
However, we don’t need to explicitly check for this when performing our replacement - because if A_i \lt 0 then either some alternating sum before i will be negative (so this index is invalid anyway), or the alternating sum at index i will become negative (which is accounted for in our suffix checks.)

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    alt = [0]*n
    alt[0] = a[0]
    for i in range(1, n):
        alt[i] = a[i] - alt[i-1]

    good = [0]*n
    good[0] = alt[0] >= 0
    for i in range(1, n):
        good[i] = good[i-1] & (alt[i] >= 0)

    ans = 0
    mne, mno = 10**18, 10**18
    for i in reversed(range(n)):
        ch = -alt[-1] if i%2 != n%2 else alt[-1]
        
        if i%2 == 0:
            mne = min(mne, alt[i])
            if mne + ch >= 0 and mno - ch >= 0 and (i == 0 or good[i-1]): ans += 1
        else:
            mno = min(mno, alt[i])
            if mno + ch >= 0 and mne - ch >= 0 and good[i-1]: ans += 1
    print(ans)