PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: sushil2006
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Binary search (optional)
PROBLEM:
You’re given an array A of length N. Find the minimum number of the following operation needed to make all its elements equal 0:
- Let S = \text{sum}(A).
- Choose an index i such that 1 \leq i \leq \min(N, |S|).
- Then, either increase or decrease A_i by 1.
EXPLANATION:
Let S = \text{sum}(A).
First, observe that if S = 0 initially, it’s impossible to perform an operation on A at all since a valid index i doesn’t exist.
So, if all the elements are already zeros the answer is 0, otherwise it’s impossible to make everything 0.
Now, suppose S \gt 0.
We need to perform several additions and several subtractions on the array to make all its elements 0.
It’s not hard to see that it’s always optimal to perform all additions before any subtractions: making the sum larger allows us to reach further indices with our operations, and performing a subtraction first doesn’t allow us to make any new moves.
Next, let’s look at where the additions and subtractions go.
Clearly, every negative element must receive additions to make it 0, and every positive element must receive subtractions to make it 0.
This gives us a lower bound of \sum_{i=1}^N |A_i| operations necessary.
As noted above, additions will happen before subtractions, so let’s focus on the negative elements first.
It’s clearly optimal to take care of negative elements from left to right: adding to one of them will increase S, allowing us to go further for the next one, and so on.
However, it’s possible that at some point, the sum isn’t large enough to reach the next negative element.
In this case, we need to increase our sum even further - but no negative elements remain in our range, so some non-negative element must be increased.
The best element to perform these ‘extra’ moves on is the first, since the first element is also the only one we’re sure can always be reduced later on.
Once all negative elements have been taken care of, we need to take care of positive elements.
These must be handled right to left instead: each operation we make decreases the sum, so carelessly reducing an earlier element might make later ones unreachable.
Again, it’s possible that we might need some extra additions to A_1 to reach some indices, which can be made as necessary.
With the above observations, there are now several ways to solve the problem.
One way is to binary search on the minimum number of extra additions to A_1, say x.
With x fixed, attempt to simulate the process - if you’re successful, x is an upper bound; otherwise x+1 is a lower bound.
Once the optimal x is found, the answer is 2x + \sum_{i=1}^N|A_i|.
Alternately, the binary search can be skipped entirely: simply try to simulate the process, and just add extras to A_1 whenever it’s absolutely necessary.
TIME COMPLEXITY:
\mathcal{O}(N\log N) or \mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll n; cin >> n;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
bool all_zero = true;
rep1(i,n) if(a[i]) all_zero = false;
ll s = 0;
rep1(i,n) s += a[i];
if(all_zero){
cout << 0 << endl;
return;
}
if(!s){
cout << -1 << endl;
return;
}
if(s < 0){
rep1(i,n) a[i] *= -1;
s *= -1;
}
ll sum = s;
ll to_add = 0;
if(a[1] < 0){
to_add = abs(a[1]);
sum += abs(a[1]);
a[1] = 0;
}
ll ans = 0;
// operate on -ves from 1 to n
rep1(i,n){
if(a[i] >= 0) conts;
amax(ans,i-sum);
sum -= a[i];
}
// operate on +ves from n to 1
rev(i,n,1){
if(a[i] <= 0) conts;
sum -= a[i];
amax(ans,i-sum-1);
}
ans *= 2;
rep1(i,n) ans += abs(a[i]);
ans += to_add;
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if min(a) == 0 and max(a) == 0:
print(0)
continue
if sum(a) == 0:
print(-1)
continue
sm = sum(a)
if sm < 0:
for i in range(n): a[i] *= -1
sm *= -1
lo, hi = 0, n
while lo < hi:
mid = (lo + hi) // 2
possible = 1
have = mid + sm
for i in range(1, n+1):
if a[i-1] < 0:
if have < i: possible = 0
have -= a[i-1]
for i in reversed(range(1, n+1)):
if a[i-1] > 0:
if have - (a[i-1] - 1) < i: possible = 0
have -= a[i-1]
if possible: hi = mid
else: lo = mid + 1
print(2*lo + sum(abs(x) for x in a))