PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: wuhudsm
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
2976
PREREQUISITES:
Prefix sums, Longest increasing subsequence in \mathcal{O}(N\log N) time.
PROBLEM:
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.
EXPLANATION:
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.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Tester's code (C++)
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...) "11-111"
#endif
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();
dp.push_back(pf.back());
if(dp.size() == 1) {
cout << -1 << '\n';
return;
}
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++)
__solve_testcase(test_no);
return 0;
}
Editorialist's code (Python)
# https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/SegmentTree.py
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()
self.data = [default] * (2 * _size)
self.data[_size:_size + self._len] = data
for i in reversed(range(_size)):
self.data[i] = func(self.data[i + i], self.data[i + i + 1])
def __delitem__(self, idx):
self[idx] = self._default
def __getitem__(self, idx):
return self.data[idx + self._size]
def __setitem__(self, idx, value):
idx += self._size
self.data[idx] = value
idx >>= 1
while idx:
self.data[idx] = self._func(self.data[2 * idx], self.data[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, self.data[start])
start += 1
if stop & 1:
stop -= 1
res_right = self._func(self.data[stop], res_right)
start >>= 1
stop >>= 1
return self._func(res_left, res_right)
def __repr__(self):
return "SegmentTree({0})".format(self.data)
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:
print(-1)
continue
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)