SUBSBIN - Editorial

PROBLEM LINK:

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

Author: Tejas Pandey
Testers: Utkarsh Gupta, Jatin Garg
Editorialist: Nishank Suresh

DIFFICULTY:

1950

PREREQUISITES:

None

PROBLEM:

Given a binary string S, in one move you can choose any substring of S that has an equal number of zeros and ones, and replace it with a single 0 or 1.
Find the minimum length of the final string, and a sequence of moves that achieves this.

EXPLANATION

First, let’s get one edge case out of the way: if S consists of only a single character, no moves can be made on it so the minimum length is just N.

In any other case, you can bring the length down to 1.
A proof of this also gives us a construction.

Let d denote the difference between the number of ones and the number of zeros in the string.

  • If d = 0, the string has an equal number of zeros and ones, so just replace the entire string with a single character.
  • Otherwise, suppose d \gt 0 (the d \lt 0 case can be handled similarly). This means there are d more ones then zeros.
    • S has at least one 1 and one 0 (since the case when it doesn’t was taken care of right at the start).
    • In particular, it has at least one substring that is either \texttt{10} or \texttt{01}.
    • Replace this substring with a \texttt{0} (if d \lt 0, replace it with \texttt{1} instead).

Notice that doing this operation reduces d by 1 (since we effectively just deleted a \texttt{1} from the string and did nothing else), while also ensuring that the string still has both 1's and 0's. So, this can be repeated till we reach d = 0, at which point the entire string is replaced.

The small limit on N allows for each operation to be done in \mathcal{O}(N), giving us a \mathcal{O}(N^2) solution. However, it also possible (and not very hard) to implement this in \mathcal{O}(N).

TIME COMPLEXITY

\mathcal{O}(N^2) or \mathcal{O}(N) per test case, depending on implementation.

CODE:

Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;

int main() {
    //freopen("inp3.in", "r", stdin);
    //freopen("out3.txt", "w", stdout);
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        int c[2] = {0, 0};
        for(int i = 0; i < s.size(); i++) c[s[i] - '0']++;
        if(c[0] && c[1]) {
            cout << "1 " << max(c[0], c[1]) - min(c[0], c[1]) + 1 << "\n";
            while(c[0] != c[1]) {
                string now = "";
                int flag = 1;
                for(int i = 0; i < s.size(); i++) {
                    if(s[i] != s[i + 1] && flag) {
                        flag = 0;
                        cout << i + 1 << " " << i + 2 << " ";
                        if(c[0] > c[1]) cout << "1\n", c[1]++, now += '1';
                        else cout << "0\n", c[0]++, now += '0';
                        i++;
                    } else now += s[i];
                }
                s = now;
            }
            cout << "1 " << s.size() << " 0\n";
        } else cout << s.size() << " 0\n";
    }
}
Tester (utkarsh_25dec)'s code (C++)
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
void solve()
{
    int n=readInt(1,1000,'\n');
    string s=readString(n,n,'\n');
    for(int i=0;i<n;i++)
        assert(s[i]=='0' || s[i]=='1');
    int cnt0=0,cnt1=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='0')
            cnt0++;
        else
            cnt1++;
    }
    if(min(cnt0,cnt1)==0)
    {
        cout<<n<<' '<<0<<'\n';
        return;
    }
    cout<<1<<' '<<(abs(cnt0-cnt1)+1)<<'\n';
    int substitute=0;
    if(cnt1<cnt0)
        substitute=1;
    for(int x=1;x<=abs(cnt0-cnt1);x++)
    {
        int l=0;
        string tmp="";
        for(int i=0;i<n;i++)
        {
            if(s[i]!=s[i+1])
            {
                l=i;
                break;
            }
        }
        cout<<l+1<<' '<<l+2<<' '<<substitute<<'\n';
        for(int i=0;i<l;i++)
            tmp+=s[i];
        tmp+=('0'+substitute);
        for(int i=l+2;i<s.length();i++)
            tmp+=s[i];
        s=tmp;
    }
    cout<<1<<' '<<s.length()<<' '<<substitute<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T=readInt(1,100,'\n');
    while(T--)
        solve();
    assert(getchar()==-1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester (rivalq)'s code (C++)
// Jai Shree Ram  
  
#include<bits/stdc++.h>
using namespace std;


#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC



template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}

// -------------------- Input Checker Start --------------------
 
long long readInt(long long l, long long r, char endd)
{
    long long x = 0;
    int cnt = 0, fi = -1;
    bool is_neg = false;
    while(true)
    {
        char g = getchar();
        if(g == '-')
        {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if('0' <= g && g <= '9')
        {
            x *= 10;
            x += g - '0';
            if(cnt == 0)
                fi = g - '0';
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if(g == endd)
        {
            if(is_neg)
                x = -x;
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(false);
            }
            return x;
        }
        else
        {
            assert(false);
        }
    }
}
 
string readString(int l, int r, char endd)
{
    string ret = "";
    int cnt = 0;
    while(true)
    {
        char g = getchar();
        assert(g != -1);
        if(g == endd)
            break;
        cnt++;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}
 
long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF() { assert(getchar() == EOF); }
 
vector<int> readVectorInt(int n, long long l, long long r)
{
    vector<int> a(n);
    for(int i = 0; i < n - 1; i++)
        a[i] = readIntSp(l, r);
    a[n - 1] = readIntLn(l, r);
    return a;
}
 
// -------------------- Input Checker End --------------------

const int maxn=2000005;
int p[maxn];
int sz[maxn];
void clear(int n=maxn){
    rep(i,0,maxn)p[i]=i,sz[i]=1;
}
int root(int x){
   while(x!=p[x]){
       p[x]=p[p[x]];
       x=p[x];
   }
   return x;  
}
void merge(int x,int y){
    int p1=root(x);
    int p2=root(y);
    if(p1==p2)return;
    if(sz[p1]>=sz[p2]){
        p[p2]=p1;
        sz[p1]+=sz[p2];
    }
    else{
        p[p1]=p2;
        sz[p2]+=sz[p1];
    }
}

int solve(){
		int n = readIntLn(1,1000);

                string s = readStringLn(n,n);
                for(auto i:s)assert(i >= '0' and i <= '1');
                int c0 = count(all(s),'0');
                int c1 = n - c0;
                if(c0 == n or c1 == n){
                        cout << n << " " << 0 << endl;
                        return 0;
                }
                int op = abs(c0 - c1) + 1;
                vector<array<int,3>> ops;
                for(int i = 1; i < op; i++){
                        int j = 1;
                        while(s[j] == s[j - 1])j++;
                        char c = (c0 < c1)?'0':'1';
                        ops.push_back({j,j + 1,c});
                        string t = s.substr(0,j - 1) + c + s.substr(j + 1);
                        s = t;
                }
                ops.push_back({1,(int)s.length(),'0'});
                cout << 1 << " " << ops.size() << endl;
                for(auto i:ops){
                        cout << i[0] << " " << i[1] << " " << char(i[2]) << endl;
                }

 return 0;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout)`;
    #ifdef SIEVE
    sieve();
    #endif
    #ifdef NCR
    init();
    #endif
    int t = readIntLn(1,100);
    while(t--){
        solve();
    }
    return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    s = input()
    if s.count('0') == n or s.count('1') == n:
        print(n, 0)
        continue
    
    dif = s.count('0') - s.count('1')
    print(1, abs(dif) + 1)
    while dif != 0:
        n = len(s)
        for i in range(n):
            if s[i] != s[i+1]:
                which = '0'
                if dif > 0:
                    which = '1'
                s = s[0:i] + which + s[i+2:]
                print(i+1, i+2, which)
                break
        dif = s.count('0') - s.count('1')
    n = len(s)
    print(1, n, 1)
1 Like

So we don’t need to make the operations minimum??

2 Likes

A single operation can change the difference between zeros and ones by either +1 or -1.

If d \gt 0, it’s best to perform an operation that does -1, which you need to do d times.
If d \lt 0, similarly it’s best to perform an operation that achieves +1.

As long as you do this in each operation, it doesn’t actually matter which substring is replaced. The minimum number of operations is always going to be |d| + 1, which you achieve as long as you don’t sabotage yourself.

2 Likes

Can someone explain the O(N) implementation pls?

1 Like

Got it.

Can someone tell why am i getting TLE on this solution : CodeChef

Thanks you so much !!

https://www.codechef.com/viewsolution/74185018
Can anyone point out the TC on which y
This gives WA

What does your readInt() function do?What are advantages of using it like this?

Can someone please point out why I am getting TLE in this implementation ?
The approach I implemented above - Link

https://www.codechef.com/viewsolution/74250273

what is error in this?

So why we are not doing it in minimum number of operations

It is specified in the question.

Has anybody tried the O(n) approach. Could someone explain how one might implement that?

my O(n) implementation. it turns out to be something like matching parentheses