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.
- First, S_2 can contain only ones. It can then take every one that isn’t in S_1, which equals
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))