BINSUBS - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Ashish Gupta
Tester: Rahul Dugar
Editorialist: Mohammed Ehab

DIFFICULTY:

SIMPLE

PREREQUISITES:

None

PROBLEM:

Given a binary string, what’s the minimum number of characters you need to remove to make it non-decreasing?

QUICK EXPLANATION:

For every index i, try erasing all the 1's up to i and all the 0's after it. The answer is the minimum across all i.

EXPLANATION:

For a binary string to be non-decreasing, it has to start with a bunch of 0's and then end with a bunch of 1's. So how can you make your string non-decreasing? Start with fixing the “split index,” the index where you’ll change from 0's to 1's; let’s call it i. You need to erase all the 1's that come before i and all the 0's that come after it. You can pre-compute these quantities using prefix-sum arrays. Now, to get the answer, just try every i to be the split index and take the minimum across them.

Bonus task: what if it’s a ternary string? Can you still solve in linear time?

SOLUTIONS:

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int pre[100005],suf[100005];
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n;
        string s;
        cin >> n >> s;
        for (int i=1;i<=n;i++)
        pre[i]=pre[i-1]+(s[i-1]=='1');
        suf[n]=0;
        for (int i=n-1;i>=0;i--)
        suf[i]=suf[i+1]+(s[i]=='0');
        int ans=n;
        for (int i=0;i<=n;i++)
        ans=min(ans,pre[i]+suf[i]);
        printf("%d\n",ans);
    }
}

VIDEO EDITORIAL:

3 Likes

Below is my code for the bonus question. I first calculate the cost of making s[0,…,i] into a 0-1 string for each i. Then the answer would be minimum of cost of making s[0,…,i] into a 0-1 string + number of zeroes and ones in s[i+1,…,n-1] over all i.

Note : This code works for the original problem as well. :blush:

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n;
    cin>>n;
    
    char s[n+1];
    s[0]='0'; //doesn't alter the answer. Just makes writing the code easier.
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
    }
    
    int count_0[n+1]={0};
    int count_1[n+1]={0};
    int count_2[n+1]={0};
    
    count_0[0]=1;
    
    for(int i=1;i<=n;i++)
    {
        count_0[i]=count_0[i-1];
        count_1[i]=count_1[i-1];
        count_2[i]=count_2[i-1];
        
        if(s[i]=='0')   count_0[i]++;
        if(s[i]=='1')   count_1[i]++;
        if(s[i]=='2')   count_2[i]++;
    }
    
    int cost_to_make_a_0_1_string_till_here[n+1]={0};
    int minimum_1_minus_0=1e9;
    for(int i=1;i<=n;i++)
    {
        cost_to_make_a_0_1_string_till_here[i]=min(count_0[i]+count_2[i],count_1[i]+count_2[i]);
        if(s[i]=='1')       minimum_1_minus_0=min(minimum_1_minus_0,count_1[i-1]-count_0[i-1]);
        cost_to_make_a_0_1_string_till_here[i]=min(cost_to_make_a_0_1_string_till_here[i],minimum_1_minus_0+count_0[i]+count_2[i]);
    }
    
    int ans=1e9;
    for(int i=0;i<=n;i++)
    {
        ans=min(ans,cost_to_make_a_0_1_string_till_here[i]+count_1[n]-count_1[i]+count_0[n]-count_0[i]);
    }
    
    cout<<ans<<endl;
}

int main() {
    
    int t;
    cin>>t;
    
    while(t--)
    {
        solve();
    }
}
1 Like

Actually, even if there are no restrictions on the characters at all, the problem is still solvable. Instead of thinking about it as “minimize the number of characters you’ll erase,” think about it as “maximize the number of characters you’ll keep.” So the answer is just N minus (longest non-decreasing subsequence.)

1 Like

Thanks for this idea. I didn’t think about generalizing the approach. This approach for any number of unique characters would be O(nlogn) from what I remember. If we know what the possible characters are, can this be solved in linear time?

Yes, there exists an O(n) solution if there’s an upper bound M on the number of unique characters.

Thanks Alot. You healped greatly. Can you please suggest some ways to approach DP problems. I know nothing about DP. From where should i learn it?

@richeshgupta I’d recommend this contest.

Can you tell which approach you are refering to.

I am referring to the third method here where we can use a fenwick tree, which is quite useful when only some fixed known characters are present. The complexity will be more like O(string_size*log2(number_of_distinct_characters)). But if we know beforehand that the number_of_distinct_characters<=M, then the time is only dependent upon n and it can be considered as O(n) by definition.

But in practice, saying O(n) can be a little misleading.

Okayyyy

Here are two more approaches to solve this problem:

  1. Using the concept of LIS (Longest Increasing Subsequence), a basic DP approach But the approach will fail in subtask 2 as it is O(n^2): Link
  2. Using Binary Search + DP it is O(n): Link

Hey, beginner here!
What exactly does it mean to make a string non-decreasing?
The actual decimal value of subsequence is larger than or equal to the decimal value of original string
Or
The no of ‘1’ > no ‘0’?

#include
using namespace std;

int main() {
int t,n;
cin>>t;
for(int i=0;i<t;i++){
cin>>n;
char arr[n];
cin>>arr;
int sum[3];
sum[0]=0;

    for(int j=0;j<n;j++){
        if(arr[j]=='0')
        sum[0]++;
        if(arr[j]=='1')
        sum[1]++;
        if(arr[j]==arr[j-1] && arr[j]=='0')
        sum[3]=min(sum[0],sum[1]);
        if(arr[j]=='0' && arr[j-1]=='1')
        sum[3]++;
    }
    cout<<sum[3]<<endl;
}
return 0;

}
the above code was my solution for the above question but codchef’s compiler is telling that the answer is wrong can anyone tell me where I am going wrong

Codechef did a live class on unacademy named ’ Master Dynamic Programming - I/II ’ in case you haven’t already attended it. Provides a great intro to the concept.

Here is my Solution. It is in O(n). Have a look.

int countone=0,count=0,countzero=0;

for(int i=0;i<n;i++){
if(A[i]==‘1’){
countone++;
}
if(A[i]==‘0’){
if(countone!=0){
countone–;
count++;
}
}
}
cout<<count<<"\n";