Pair Increment Ranges - Repovive Career Starter Round 2 | Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/10/problems/f

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/10/problems/f

Pair Increment Ranges - Repovive Career Starter Round 2 | Repovive | Repovive

Page 1) Feasibility on a fixed interval [l, r]

We can apply operations: choose $i$ $(l < i ≤ r)$ , do a[i-1]-- and a[i]++. Equivalently, we move $1$ unit of value one step to the right, inside $[l, r]$ .

Define $d[i] = a[i] - b[i]$ . We want to make $d[i] = 0$ for all $i$ in $[l, r]$ .

Key invariant $1$ (total sum): The operation preserves $\sum_{i=l..r} a[i]$ , so it preserves $\sum_{i=l..r} d[i]$ .

To end with all zeros we must have: $\sum_{i=l..r} d[i] = 0$ .

Key invariant $2$ (interval prefix sums can only go down): For $j$ in $[l, r]$ , define interval-prefix: $S(j) = sum_{i=l..j} d[i]$ .

If we apply the operation at index $i$ , only $d[i-1]$ decreases and $d[i]$ increases. So among all $S(j)$ , the only one that changes is $S(i-1)$ , and it decreases by $1$ . No $S(j)$ can ever increase.

In the target state (all $d = 0$ ), every $S(j)$ equals $0$ . Since $S(j)$ never increases during operations, we must start with:

$S(j) ≥ 0$ for all $j = l..r-1$ ,

and also (from total sum): $S(r) = 0$ .

So a necessary condition is:

for all $j$ in $[l, r-1]$ : $sum_{i=l..j} (a[i]-b[i]) ≥ 0$
$sum_{i=l..r} (a[i]-b[i]) = 0$

This condition is also sufficient: Process positions from left to right. At position $x$ , if $d[x] > 0$ , we can move this surplus right (using operations at $x+1$ repeatedly) to reduce $d[x]$ to $0$ . The constraints $S(j) ≥ 0$ guarantee we never need to “pull” from the right (which is impossible), so we can finish and reach all zeros.

Conclusion: $[l, r]$ is beautiful ⇔ all interval prefix sums of $(a-b)$ are nonnegative and the total is zero.