# S100 - Editorial

Author & Tester: tabr
Editorialist: iceknight1093

1631

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

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

1111

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?

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.

3 Likes

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());

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;


indeed it helped me a lot
thank you

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;
}


:')

{
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”;
}

What’s wrong with my code??

#include <iostream>
using namespace std;

int main() {
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;
}