MOVE_STONES - Editorial


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

Author: wuhudsm
Tester: apoorv_me
Editorialist: iceknight1093




Prefix sums, Longest increasing subsequence in \mathcal{O}(N\log N) time.


You have an array A. You can pick an index 1 \leq i \lt N and an integer X, and simultaneously perform A_i \to A_i - X and A_{i+1} \to A_{i+1} + X.

Find the minimum number of operations required to make A_i \geq 0 for all i, or claim it’s impossible to do so.


Often, when dealing with operations that affect adjacent elements like this (or more generally, subarrays), it’s helpful to look at how the prefix sum array changes.

Let P denote the prefix sum array of A, where P_i = A_1 + A_2 + \ldots + A_i.
Then, operation (i, X) does the following:

  • For all j \lt i, P_j is unchanged.
  • P_i changes to P_i - X.
  • For all j \gt i, P_j is unchanged.
    This is because all of them receive both the +X change and the -X change, which cancel out — A_i + A_{i+1} = (A_i - X) + (A_{i+1} + X).

In other words, all we’re doing is changing some element of P_i by X.
However, observe that we can’t change P_N, since we can only pick 1 \leq i \lt N.

Now, note that our aim is to have A_i \geq 0 for all i.
This is equivalent to the prefix sum array P being non-decreasing — after all, P_i = P_{i-1} + A_i, so A_i \geq 0 if and only if P_i \geq P_{i-1}.
Note that if P_N \lt 0, then this is impossible to achieve since we can’t change P_N.
In all other cases, it’s possible to achieve what we want.

Our task has now turned into making P non-decreasing, where we can modify any element of P other than the last.
Clearly, each index will be operated on at most once, since a single operation allows us to change the value to anything we want.

So, we only need to find the minimum number of values that need to be changed — equivalently, we can find the maximum number of values that don’t need to be changed.
Notice that any set of unchanged values must form a non-decreasing subsequence; since they’ll remain the same in the final array as well (which is non-decreasing).

The maximum number of values is then, by definition, just the longest non-decreasing subsequence of P.
Note that P_N will always be unchanged, so in particular we want to find the longest non-decreasing subsequence of P that ends at index N.

There are a couple of different ways to find this length in \mathcal{O}(N\log N): either binary search, or via use of some data structure like a segment tree.
Both methods are detailed here.


\mathcal{O}(N\log N) per testcase.


Tester's code (C++)
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")

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

#ifdef LOCAL
#include "../debug.h"
#define dbg(...) "11-111"

int32_t main() {
    ios_base::sync_with_stdio(0);   cin.tie(0);

    auto __solve_testcase = [&](int testcase) -> void {
        int n;  cin >> n;
        vector<long long> pf(n + 1);
        for(int i = 0 ; i < n ; i++) {
            int x;  cin >> x;
            pf[i + 1] = pf[i] + x;
        vector<long long> dp(1);
        for(int i = 1 ; i < n ; i++) if(pf[i] >= 0) {
            if(pf[i] >= dp.back())  dp.push_back(pf[i]);
            else {
                *upper_bound(dp.begin(), dp.end(), pf[i]) = pf[i];
        while(!dp.empty() && dp.back() > pf.back()) dp.pop_back();

        if(dp.size() == 1) {
            cout << -1 << '\n';
        cout << n + 1 - (int)dp.size() << '\n';
    int no_of_tests;   cin >> no_of_tests;
    for(int test_no = 1 ; test_no <= no_of_tests ; test_no++)

    return 0;
Editorialist's code (Python)
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length() = [default] * (2 * _size)[_size:_size + self._len] = data
        for i in reversed(range(_size)):
  [i] = func([i + i],[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size[idx] = value
        idx >>= 1
        while idx:
  [idx] = self._func([2 * idx],[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left,[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func([stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

    def __repr__(self):
        return "SegmentTree({0})".format(

from bisect import bisect_left

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    p = [0]
    for x in a: p.append(p[-1] + x)
    if p[-1] < 0:
    distinct = sorted(list(set(p)))
    seg = SegmentTree([0]*len(distinct))
    ans = 0
    for x in p[1:]:
        if x < 0: continue
        pos = bisect_left(distinct, x)
        till = seg.query(0, pos+1)
        till += 1
        seg[pos] = till
        ans = till
    print(n - till)