MAXIMISEMIN - Editorial

PROBLEM LINK:

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

Author: satyam_343
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Binary search, dynamic programming

PROBLEM:

Let f(S) denote the length of the longest non-decreasing subsequence of a binary string S.

You’re given a binary string S.
Find the maximum possible value of \min(f(S_1), f(S_2)) across all partitions of S into subsequences S_1 and S_2.

EXPLANATION:

Instead of trying to find the exact answer, let’s see if we can figure out whether the answer is at least K (for a fixed parameter K).
If we can do this quickly enough, the answer can be binary searched.

So, our task reduces to checking for a fixed K, whether S can be partitioned into two subsequences S_1 and S_2 such that \min(f(S_1), f(S_2)) \geq K.
Of course, this means we want both f(S_1) and f(S_2) to be \geq K.
In fact, we can reduce this further: it’s enough to find two disjoint non-decreasing subsequences in S that both have length at least K — the remaining elements can be added to either subsequence and it won’t worsen things.
So, from now on, S_1 and S_2 will denote non-decreasing subsequences.


The main observation to be made here is that, if a valid pair (S_1, S_2) exists, then there will always exist a pair where S_1 contains the first x zeros occurring in S (x being the number of zeros in S_1 itself).

Proof

Consider a pair of disjoint non-decreasing subsequences S_1 and S_2.
Let S_1 have x zeros.
Suppose these aren’t the first x zeros in S.

Consider the leftmost zero that is not in S_1; say at position i.
Note that in particular, S_1 contains a zero to the right of i. Let j be the index of the leftmost such 0.
Then, there are two possibilities:

  • i is not included in S_2. Then, discard j from S_1 and include i - the length doesn’t change, and the included prefix is longer.
  • i is included in S_2. Once again, there are two possibilities.
    • First, suppose S_2 doesn’t include a 1 before index j. Then, we can give index i to S_1 and index j to S_2, and both sequences don’t change in value but S_1 has a longer prefix of zeros.
    • Second, S_2 might include a 1 before index j. In this case, all of S_2's zeros occur before j, so we can just give S_2 the corresponding prefix of zeros and move the rest to S_1, then swap S_1 and S_2.

With this observation in hand, let’s formulate an algorithm to compute the answer.
Suppose S_1 is to contain x zeros.
Then,

  • Let z_x be the position of the x'th zero in S.
    S_1 then needs to contain K-x ones; observe that it’s optimal to choose the K-x closest ones after z_x.
    Let y be the position of the (K-x)'th one after z_x.
  • S_2 now has two possibilities:
    • First, S_2 can contain only ones. It can then take every one that isn’t in S_1, which equals
      O-(K-x); where O is the total number of ones in S.
    • Second, S_2 might contain a 0. It would then have to contain zeros only after z_x (since the first x zeros are in S_1.
      Further, it can only contain ones after position y, since everything till that was given to S_1.
      So, the best we can do is to give all zeros from z_x+1 to y to S_2, then choose the longest non-decreasing subsequence that begins after y.

To compute this, we’d need the following information:

  • z_x, the position of the x'th zero. This is easy to find: keep a list of positions of zeros.
  • y, the (K-x)'th one after z_x. This can be found by keeping a list of ones.
  • O, the total number of ones. This can be precomputed.
  • The length of the longest non-decreasing subsequence after y.

For the last point, note that we want the longest non-decreasing subsequence on some suffix of the string.
This can be computed using dynamic programming.
Let \text{dp}[i] denote the length of the longest non-decreasing subsequence of the suffix starting from i.
Then,

  • if S_i = 0, \text{dp}[i] = \text{dp}[i+1] + 1.
  • Otherwise, \text{dp}[i] = \max(\text{dp}[i+1], O_i) where O_i is the number of ones in the suffix starting from i.

With all this information in hand, for a fixed x the maximum possible length of S_2 can be computed in \mathcal{O}(1) time.
So, simply run a check for every x. If |S_2|\geq K for at least one of them, \min(f(S_1), f(S_2))\geq K can be achieved; otherwise it can’t.

This gives us a check in linear time, so binary search gives us a \mathcal{O}(N\log N) solution.

TIME COMPLEXITY:

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

CODE:

Author's code (C++)
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;   
using namespace std;
#define ll long long
#define pb push_back                  
#define mp make_pair          
#define nline "\n"                            
#define f first                                            
#define s second                                             
#define pll pair<ll,ll> 
#define all(x) x.begin(),x.end()     
#define vl vector<ll>           
#define vvl vector<vector<ll>>      
#define vvvl vector<vector<vector<ll>>>          
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);  
#endif     
void _print(ll x){cerr<<x;}  
void _print(char x){cerr<<x;}   
void _print(string x){cerr<<x;}    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());   
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";} 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------  
const ll MOD=1e9+7;
const ll MAX=500500;
void solve(){ 
    ll n; cin>>n;
    string s; cin>>s; s=" "+s;
    vector<ll> pref(n+5,0);
    vector<vector<ll>> position(2,vector<ll>(n+5,0));
    vector<ll> freq(2,0),track(n+5,0);
    for(ll i=1;i<=n;i++){
        ll d=s[i]-'0';
        pref[i]=pref[i-1]+d;
        freq[d]++;
        position[d][freq[d]]=i;
    }
    for(ll i=n;i>=1;i--){
        track[i]=max(track[i+1],i-1-pref[i-1]+pref[n]-pref[i]+1);
    }
    auto check=[&](ll mid){
        for(ll zero=0;zero<=mid;zero++){
            ll cur=position[0][zero];
            if(zero and cur==0){
                continue;
            }
            ll need=mid-zero+pref[cur]; 
            ll last=cur;
            if(need>n){    
                continue;
            }
            if(need!=0){
                last=position[1][need];
            }
            if(last==0){ 
                continue; 
            } 
            ll zero_left=n-pref[n]-zero;
            if(zero_left>=mid){
                return 1;
            }
            if(pref[n]-need>=mid){
                return 1;
            }
            ll left_zero=last-pref[last];
            if(track[last+1]-zero>=mid){
                return 1;
            }
        }
        return 0;
    };
    ll l=1,r=n/2,ans=1;
    while(l<=r){
        ll mid=(l+r)/2;  
        if(check(mid)){  
            ans=mid;  
            l=mid+1;    
        }
        else{
            r=mid-1; 
        }    
    }
    cout<<ans<<nline;
    return;    
}                                       
int main()                                                                               
{       
    ios_base::sync_with_stdio(false);                          
    cin.tie(NULL);                               
    #ifndef ONLINE_JUDGE                 
    freopen("input.txt", "r", stdin);                                           
    freopen("output.txt", "w", stdout);      
    freopen("error.txt", "w", stderr);                        
    #endif     
    ll test_cases=1;                 
    cin>>test_cases;
    while(test_cases--){
        solve();
    }
    cout<<fixed<<setprecision(10);
    cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
}  
Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    s = input()
    dp = [0]*(n+1) # dp[i] = LNDS of i...n
    ones = 0
    for i in reversed(range(n)):
        if s[i] == '0': dp[i] = dp[i+1] + 1
        else:
            ones += 1
            dp[i] = max(dp[i+1], ones)
    onepos = []
    pref = [0]*n
    for i in range(n):
        if s[i] == '1': onepos.append(i)
        else: pref[i] = 1
        if i > 0: pref[i] += pref[i-1]
    if not onepos or len(onepos) == n:
        print(n//2)
        continue
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi + 1)//2

        zeros = 0
        ptr = 0
        possible = False
        for i in range(n):
            if s[i] == '1': continue
            zeros += 1
            if zeros > mid: break
            req = mid - zeros

            # Take the next req ones, from i+1
            while ptr < len(onepos):
                if onepos[ptr] <= i: ptr += 1
                else: break
            where = ptr + req - 1
            if where >= len(onepos): continue
            lstone = max(i, onepos[where])

            best = dp[lstone+1] + pref[lstone] - pref[i]
            best = max(best, ones - req)
            if best >= mid:
                possible = True
                break
        if not possible: hi = mid-1
        else: lo = mid
    print(max(lo, ones//2))

Wanted to mention another method here, which surprisingly doesnt even rely on the observation of the first zeroes always going to one string.

Consider the point where S1 changes from 0 to 1, and the point where S2 changes from 0 to 1, let them be i and j respectively (in the original sequence) i <= j wlog.

All the things in range [i, j) is predecided which subsequence it will go to. The 0s before i can go to either, and same for 1s after j.

This gives you a equation like min(a, b, c) and using some data structures and sorting and other such bash, you can consider all possible pairs of (i, j) in just nlogn

1 Like

One more solution
Do binary search over ans and
There are two cases:

  1. cnt0 (count of zero)>= cnt1
  2. o.w.

Checker function for 1. case (similar for second)
//1.1 greedily take last mid zeros for 2nd-second subsequence(s2)
//1.2Then check whether you can make s1 length>= mid

We can prove 1.1 using some exchange arguments.
Here is the code:
https://www.codechef.com/viewsolution/1036114859

Checker function

bool solve(vector v, int mid)
{
int n= v.size();
int ans= 0;

int cnt0= 0, cnt1= 0;

for(int i= 0; i< n; i+= 1)
{
  if(v[i]) cnt1+= 1;
  else cnt0+= 1;
}

if(cnt0>= cnt1)
{
  // take half zeros from back greedily;
  vector<bool> taken(n, false);
  int took= 0;

  for(int i= n- 1; i>= 0; i-= 1)
  {
    if(took== mid) break;
    if(v[i]== 0) taken[i]= true, took+= 1;
  }
  
  int curr= 0;

  for(int i= 0; i< n; i+= 1)
   if(!taken[i])
  {
    if(v[i]== 0) curr+= 1;
    ans= max(ans, curr+ cnt1);
    if(v[i]== 1) cnt1-= 1;
  }
}
else
{
  vector<bool> taken(n, false);
  int took= 0;

  for(int i= 0; i< n; i+= 1)
  {
    if(took== mid) break;
    if(v[i]== 1) taken[i]= true, took+= 1;
  }
  
  int curr= 0;

  for(int i= n- 1; i>= 0; i-= 1)
   if(!taken[i])
  {
    if(v[i]== 1) curr+= 1;
    ans= max(ans, curr+ cnt0);
    if(v[i]== 0) cnt0-= 1;
  }
}
ans= min(ans, n/ 2);
return ans>= mid;

}

1 Like

In editorialist’s code, why max(ans, ones/2) is taken at the end?