Extreme Subtraction -- CF 1443D

Difficulty: 1800 * Techniques: difference array, decomposition into monotone parts, invariant Problem Link

Quick Revisit

• PROBLEM: Can we reduce an array to all zeros using prefix-subtract and suffix-subtract operations?
• KEY INSIGHT: Equivalent to decomposing a = f + g where f is non-increasing and g is non-decreasing. Check: positive diffs sum <= a[0], negative diffs sum <= a[n-1].
• TECHNIQUES: difference array analysis, decomposition into monotone parts
• TRANSFER: "Subtract from prefix/suffix" -- think difference array. Simulation impossible at 10^9 => find algebraic invariant.

First Read

Array of $n$ non-negative integers. Two operations:

• Choose $k$ ($1\le k\le n$), subtract 1 from the first $k$ elements.
• Choose $k$ ($1\le k\le n$), subtract 1 from the last $k$ elements.

Can we make all elements zero? No constraint on number of operations.

The Simulation Trap

My first instinct: simulate. Maybe greedily subtract from the left or right to equalize? But the order and choice of $k$ interact in complex ways. Simulation would be $O(n\cdot max(a_i))$ at best, and $max(a_i)\le {10}^9$. Dead.

OK, I need to think about what operations do structurally, not simulate them.

Reframing as a Decomposition

Stop thinking about the order of operations and look at the totals. Let $P_k$ be the number of prefix operations of length $k$ used, and $S_k$ the number of suffix operations of length $k$. The total amount subtracted from position $j$ (0-indexed) is

$$a[j]=\underset{f[j]}{\underbrace{\sum _{k>j}{P}_k}}+\underset{g[j]}{\underbrace{\sum _{k\ge n-j}{S}_k}}.$$

Two structural observations:

• $f[j]=\sum _{k>j}{P}_k$ is non-increasing in $j$: as $j$ grows, the set $\{k:k>j\}$ shrinks.
• $g[j]=\sum _{k\ge n-j}{S}_k$ is non-decreasing in $j$: as $j$ grows, $n-j$ shrinks, so the set $\{k:k\ge n-j\}$ grows.

So the question becomes purely combinatorial: can we write

$$a[j]=f[j]+g[j],f\text{ non-increasing}\ge 0,g\text{ non-decreasing}\ge 0?$$

If yes, the corresponding $P_k$ and $S_k$ exist (recover them by differencing $f$ and $g$). If no, the array can't be zeroed.

Why the Difference Array Settles It

Take $d[i]=a[i]-a[i-1]$ for $i\ge 1$. Decompose $d=d_f+d_g$ where $d_f[i]=f[i]-f[i-1]\le 0$ (non-increasing $f$) and $d_g[i]=g[i]-g[i-1]\ge 0$ (non-decreasing $g$).

To match $a$'s differences, we must assign each negative chunk of $d[i]$ to $d_f$ and each positive chunk to $d_g$ (any other allocation would force one of $d_f,d_g$ to violate its sign constraint at some $i$). With that forced assignment, $f[0]=a[0]-g[0]$, and feasibility reduces to two non-negativity checks at the boundaries:

• $f[n-1]\ge 0$: equivalently, $f[0]-(\text{sum of }|d_f[i]|)\ge 0$, i.e., $\sum _{d[i]<0}|d[i]|\le a[n-1]$ after using $g[n-1]=a[n-1]$.
• $g[0]\ge 0$: equivalently, $a[0]-f[0]\ge 0$, i.e., $\sum _{d[i]>0}d[i]\le a[0]$.

The Clean Condition

The array is reducible to zero if and only if

$$\sum _{i\ge 1,d[i]>0}d[i]\le a[0]\text{and}\sum _{i\ge 1,d[i]<0}|d[i]|\le a[n-1].$$

Intuitively: positive jumps in $a$ must be "paid for" by available prefix capacity at $a[0]$, and negative jumps must be paid for by suffix capacity at $a[n-1]$. That's the entire problem.

The Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long pos = 0, neg = 0;
    for (int i = 1; i < n; i++) {
        long long d = a[i] - a[i - 1];
        if (d > 0) pos += d;
        else neg += -d;
    }

    cout << (pos <= a[0] && neg <= a[n - 1] ? "YES" : "NO") << "\n";
}

int main() {
    int t; cin >> t;
    while (t--) solve();
}

Transfer Lesson

• "Subtract 1 from a prefix/suffix" -- think difference array. These operations have very clean effects on differences.
• Decomposition into monotone parts -- if an array must be expressible as $f+g$ (non-increasing + non-decreasing), the difference array splits neatly into positive and negative parts.
• When simulation is impossible (${10}^9$ values), find an algebraic invariant. The difference array often reveals the right one.

---

See also: Difference Arrays | Greedy | Invariant Technique | Pattern Recognition Guide | Practice Ladder 1700-2100