P5169 - Editorial

PROBLEM LINK:

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

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Binary search

PROBLEM:

You’re given an array A. You can rearrange it freely, as long as you ensure that the relative order of positive numbers doesn’t change and the relative order of negative numbers doesn’t change.
What’s the minimum possible value of the maximum subarray sum attainable?

EXPLANATION:

Let \text{pos} denote the list of positive elements of A in order, and \text{neg} denote the list of non-positive elements in order.
Our task is now to merge these two lists while minimizing the maximum subarray sum.

Let us try to see if making the maximum subarray sum be \leq X is possible: if we’re able to decide this quickly enough, binary searching to find the smallest valid X will give us a solution.

To get an idea of what to do, let’s look at the classical algorithm to compute the maximum subarray sum:

max_subarray_sum = 0
current_max = 0 # maximum sum of a subarray ending at the current index
for i in 1...n:
    current_max = a[i] + max(0, current_max) # take either only this element, or it along with the best subarray ending at the previous index
    max_subarray_sum = max(max_subarray_sum, current_max)

Ensuring that the maximum subarray sum is \leq X is equivalent to ensuring that the value of current_max above (i.e. the maximum subarray sum ending at each index) never exceeds X.

We must place the elements of \text{pos} and \text{neg} in order, allowing this to be done greedily.
That is,

  • Run the above maximum sum subarray only on the elements of \text{pos}.
    • This is because the maximum sum subarray will end at a positive element - if it ends at a negative element, simply discarding that element will give us a larger sum.
    • So, we only need to ensure that the value of current_max at positive elements is \leq X.
    • This allows us to use the negative elements as ‘separators’, with their only role being reducing the sum.
  • If the value of current_max ever exceeds X, use negative elements from \text{neg} to reduce it.
    • These elements must be used in order, so you can for example keep a pointer to the last used element.
    • This can be thought of as placing the corresponding negative elements just before the positive element.
    • Make sure that current_max is updated appropriately when doing this - note that it can’t reduce below the value of the current element of \text{pos} that’s being processed.
  • If current_max exceeds X at any point but we run out of negative elements, it’s not possible to make all the subarray sums \leq X. Otherwise, it is.

This can be checked easily in linear time, since all we do is a single pass over \text{pos} and a single pass over \text{neg}.
So, binary searching to find the smallest valid X will be fast enough.

As for the limits of the binary search: \max(A) and \text{sum}(\text{pos}) are safe lower/upper bounds, respectively.

TIME COMPLEXITY:

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

CODE:

Author's code (C++)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <chrono> 
#include <random>
using namespace std;
#define ll long long

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
  ll cases;
  cin>>cases;
  while(cases--){
    ll n;
    cin>>n;
    ll x;
    vector <ll> v,u;
    for(int i=0;i<n;i++){
      cin>>x;
      if(x>0){
        v.push_back(x);
      }
      if(x<0){
        u.push_back(x);
      }
    }
    ll l=0;
    ll r=1e18;
    ll ans=r;
    ll mid,best,sum,y;
    vector <ll> cntv,cntu;
    while(r>l){
      mid=(r+l)/2+1;
      best=0;
      cntv=v;cntu=u;
      sum=0;
      while(cntv.size() && best<mid){
        y=cntv.back();
        if(y>=mid){
          best=mid;
          break;
        }
        if((sum+y)>=mid){
          if(cntu.size()){
            sum=max((ll)0,sum+cntu.back());
            cntu.pop_back();
          }else{
            best=mid;
          }
          continue;
        }
        cntv.pop_back();
        best=max(best,y+sum);
        sum+=y;
      }
      if(best>=mid){
        l=mid;
      }else{
        r=mid-1;
      }
    }
    cout<<l<<"\n";
  }
	return 0;
}

Editorialist's code (PyPy3)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))

    pos, neg = [], []
    for x in a:
        if x > 0: pos.append(x)
        else: neg.append(x)
    
    def check(mid):
        i, curmx = 0, 0
        for x in pos:
            curmx += x
            while i < len(neg):
                if curmx > mid:
                    curmx = max(x, curmx + neg[i])
                    i += 1
                else: break
            if curmx > mid: return False
        return True
    
    if len(pos) == 0:
        print(0)
        continue
    
    lo, hi = max(pos), 10**15
    while lo < hi:
        mid = (lo + hi)//2
        if check(mid): hi = mid
        else: lo = mid + 1
    print(lo)
1 Like

Nice problem. A real insight and understanding of binary search is required.

1 Like

Good problem. Failed to see it was binary search but was able to upsolve it quickly. Thanks for the contest!

Awesome problem , didn;t think of binary search during the contest i though it was greedy.