S100 - Editorial

editorial
,
1

PROBLEM LINK:

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

Author & Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

1631

PREREQUISITES:

None

PROBLEM:

You’re given a string binary S. In one move, you can replace a substring of length 3 by "100".
Find the lexicographically smallest string you can attain.

EXPLANATION:

Let k be the first occurrence of \texttt{1} in S, i.e, the smallest index such that S_k = \texttt{1} . If no ones exist in the string, let k = N+1 instead.
In particular, S_i = \texttt{0} for all 1 \leq i \lt k.

Note that it’s never optimal to perform an operation involving an index \lt k, because we would replace a prefix zero with a 1, and that isn’t optimal for lexicographical smallness.
So, we only perform replacement operations on substrings that start at indices \geq k.

Now, a simple analysis of this should tell you that:

  • If k \gt N-2, then it’s not possible to even perform a move; so the optimal solution is to do nothing and just print S.
  • If k \leq N-2, then we can perform replacement operations on some substrings.
    Here, we can in fact make S_i = \texttt{0} for every i \gt k via the following process:
    • Perform the replacement operation on substring S_iS_{i+1}S_{i+2} in decreasing order of i, starting from i = N-2 and going down to i = k.
      It’s easy to see that:
      • The first move sets S_N = S_{N-1} = \texttt{0}.
      • The second move sets S_{N-2} = \texttt{0} without changing anything to its right.
      • The second move sets S_{N-3} = \texttt{0} without changing anything to its right.
        \vdots

In fact, in the second case we set every character of S to zero except S_k, and it’s easy to see why this is the lexicographically smallest string possible - making S_k zero using an operation would make some character to the left of S_k change from 0 to 1, and that’s not optimal.

TIME COMPLEXITY

\mathcal{O}(N) per testcase.

CODE:

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

int main() {
	int tt;
	cin >> tt;
    while (tt--) {
		int n;
		cin >> n;
        string s;
        cin >> s;
        int i = (int) (find(s.begin(), s.end(), '1') - s.begin());
        if (i <= n - 3) {
            for (int j = i + 1; j < n; j++) {
                s[j] = '0';
            }
        }
        cout << s << " \n";
    }
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    for i in range(n-2):
        if s[i] == '1':
            s = s[:i] + '1' + '0'*(n-i-1)
            break
    print(s)
2 Likes
2

hi @tabr , thanks for the problem and the editorial
I have a quick question though,
I wrote this algorithm, which returns WRONG and I have some hard time to understand why

#define ROF(i, N, a) for (int i = (N)-1; i >= (a); --i)

  ll n; cin >> n;
  string s; cin >> s;

  ROF(i, n-2, 0){
    if( s[i] == '1' ){
        s[i+1] = '0';
        s[i+2] = '0';
    }
  }

cout << s  << endl;

if you can check this and tell me why it’s wrong, i would be great
thanks in advance

3

1111

4

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

int main() {
int t;cin>>t;
while(t–){
int n;cin>>n;
string st;cin>>st;

    for(int i=n-3;i>=0;i--){
        if(st[i]=='1'){
            st[i]='1';
            st[i+1]='0';
            st[i+2]='0';
        }
    }
    cout<<st<<endl;	    
}
return 0;

}

This is my approach, what I was missing?

5

For the input:
4
1001
This algorithm prints the output: 1001

But a lexicographically smaller string can be obtained:
Apply the operation on index 1: 1001 => 1100
Apply the operation on index 0: 1100 => 1000

1000 < 1001
Hence, this algorithm is wrong.
I hope this was helpful.

3 Likes
6

I have tried to do this in this way would be great help if someone finds what is wrong with it
String str = s.next();
char[] arr = str.toCharArray();
for(int i = 0;i<N-2;i++){
String res1 = arr[i]+“”+arr[i+1]+“”+arr[i+2]+“”;
if(res1.equals(“101”)==true || res1.equals(“111”)==true|| res1.equals(“110”)==true){
arr[i] = ‘1’;
arr[i+1] = ‘0’;
arr[i+2] = ‘0’;
}
}
StringBuilder ans = new StringBuilder();
for(int j = 0;j<N;j++){
ans.append(arr[j]+“”);
}
System.out.println(ans.toString());

7

Can someone please help me in finding the error in my code??

int n;
cin>>n;
string s;
cin>>s;
int c=0;
for(int i=0;i<n;i++){
if(s[i]==‘1’)
c++;
}

if(c==0 || is_sorted(s.begin(),s.end()) || c==n){
    cout << s << endl;
    return;
}
if(n==3 && !is_sorted(s.begin(),s.end())){
    cout << "100" << endl;
    return;
}


string ans="";
    int ind=-1;
    for(int i=0;i<n-1;i++){
        if(s[i]=='1'){
            ind=i;
            break;
        }
    }
    
    for(int i=0;i<ind;i++){
       
        ans+='0';
    }
    
    ans+='1';
    for(int i=ind+1;i<n;i++)
        ans+='0';
    
    cout << min(s,ans) << endl;
8

indeed it helped me a lot :smiling_face:
thank you

10

Where does this code fail? It seems correct to me. CodeChef: Practical coding for everyone

typedef long long ll;
#define vll vector<long long int>
#define forp(i,k,n) for(i=k;i<n;i++)
#define forn(i,k,n) for(i=n-1;i>=k;i--)
#define nm "\n"
#define sp " "
#define ss second
#define ff first
#define pb push_back
#define pf push_front
#define no "NO"
#define yes "YES"
#define nfs ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)

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

int main(){
    nfs;
    ll t,i,n;
    cin>>t;
    while(t--){
        cin>>n;
        char s[n];
        cin>>s;
        forp(i,0,n){
            if(s[i]=='1'){
                if(i<n-2){
 //                   if(s[i+1]=='1' && i+1<n-2)
 //                   continue;
                    for(ll j=i+1;j<n;j++){
                        s[j]='0';
                    }
                    break;
                }
            }
        }
        cout<<s<<nm;
    }
    return 0;
}
11

:')

{
int n; cin>>n;
string s; cin>>s;
int c = 0;
for(int i=0; i<n; i++)
{
if(c) s[i] = ‘0’;
else if(i<n-2 && s[i] == ‘1’) c++;
}
cout<<s<<“\n”;
}

12

What’s wrong with my code??

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    string s;
	    cin>>s;
	    int pos = 0;
        while(s[pos]!='1'){
            pos++;
        }
        for(int i=0; s[i]!='\0'; i++){ 
            s[i] = '0';
        }
        s[pos]='1';
	    cout<<s<<endl;
	}
	return 0;
}