# SRTARR - EDITORIAL

Setter: Shivansh Agarwal
Testers: Nishank Suresh and Abhinav Sharma
Editorialist: Anish Ashish Kasegaonkar

1112

Strings, Greedy

# PROBLEM

You are given a binary string S of length N. You can reverse any substring of S in one operation, find the minimum number of operations required to sort S.

# EXPLANATION

### Hint

The resulting string should be such that all '0's appear consecutively before a ‘1’ appears.

### Detailed Explanation

To sort S, we can iterate through the string and reverse every leftmost instance of “1,1,...,1,0,...,0,0”, i.e. a substring of S with consecutive '1's and then consecutive '0's. This is guaranteed to sort S in the minimum number of operations.

Intuition for correctness

While iterating through S, if you reverse an instance of “1,1,...,1,0,...,0,0” then you would obtain a prefix of '0's, as we are essentially pushing forward the occurrences of '1's that are present before a ‘0’. So, the resulting string would have a prefix of '0's and a suffix of '1's, and hence would be sorted in the minimum number of operations.

This simply reduces to counting the number of occurrences of “10” that appear in the string and printing it. This is because the number of "1,1,...,1,0,...,0,0"s that appear in the string are the same as the number of "10"s that appear in the string.

# TIME COMPLEXITY

The time complexity is O(|S|) per test case.

# SOLUTIONS

Setter's Solution
// author: Shivansh Agarwal
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const int mod = 1000000007;
const double EPS = 1e-7;

int32_t main()
{
fastio;
auto begin = std::chrono::high_resolution_clock::now();
int tt;
cin >> tt;
while(tt--)
{
int n;
cin >> n;
string s;
cin >> s;
int ans = 0;
for (int i = 0; i < n - 1;i++) if(s[i] == '1' && s[i+1] == '0')
ans++;
cout << ans << "\n";
}
auto end = std::chrono::high_resolution_clock::now();
cerr << setprecision(4) << fixed;
cerr << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl;
}
Tester's Solution 1
#include <bits/stdc++.h>
using namespace std;

/*
------------------------Input Checker----------------------------------
*/

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 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){
}
long long readIntLn(long long l,long long r){
}
}
}

/*
------------------------Main code starts here----------------------------------
*/

const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define pb push_back

int sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 998244353;

void solve(){
sum_n+=n;

for(auto h:s) assert(h=='0' || h=='1');

int ans=0;
rep_a(i,1,n){
if(s[i]=='0' && s[i-1]=='1') ans++;
}

cout<<ans<<'\n';

}

signed main()
{

#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;

int t = 1;

for(int i=1;i<=t;i++)
{
solve();
}

assert(getchar() == -1);
assert(sum_n<=1e6);

cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_n <<" "<<sum_m<<'\n';
// cerr<<"Maximum length : " << max_n <<'\n';
// // cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';

cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's Solution 2
for _ in range(int(input())):
n = int(input())
print(input().count('10'))

Feel free to share your approach. Suggestions are welcomed.

This Approach is failing 2 cases. Can someone find the bug, or the testcases in which it is failing

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

int main()
{
int T; cin>>T;
while(T–){
int N;
cin>>N;
string s;
cin>>s;
int a=0; // if zero or pair of 0’s at starting
int b=0; //number of pairs of continous zeroes
if (s[0]==‘0’) a=1;

bool Zero=true;
if(s[1]==0) Zero=false;
for(int i=1;i<N;i++){
if (s[i]=='0' && s[0]=='0' ) Zero = (Zero && true) ;//if s is a binary of 0;
else if(s[i]=='1'){ Zero=false;
if(s[i] != s[i-1]) b++;
}

}
if(s[N-1]=='0') b++;//if zero occur at last without( that wont be counted in b as after if no 1 occurs)
if(Zero) cout<<0<<endl;
else cout<<b-a<<endl;
}

}

Hi I think you didn’t consider the consecutive 1’s, see this input
1
5
11100

should be 1, yours is 3

Okay thanks

else{
flag = x[i]-'0'==0 ? 0 : 1;
result++;
}

Should be:-

else{
flag = x[i]=='0' ? 0 : 1;
if(flag==0)
result++;
}

Can anyone tell what is wrong with my approach?
https://www.codechef.com/viewsolution/68372883

Bro, initially b was false but as we got schar == ‘1’ && echar == ‘0’ you changed b to true, means you reversed substring from schar to echar but then next time you encounter schar == ‘0’ && echar == ‘1’ then you can’t simply move left and right pointers, because since you have reversed once, it will be actually schar == ‘1’ and echar == ‘0’ means you have to reverse again. so check before moving any pointers that if you have reversed or not.

Below is my submission :-

// Accepted
int main()
{

int t=1;
cin>>t;
while(t--){

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

ll l = 0;
ll r = n-1;

ll ans = 0;
bool flip = false;

// two pointer method
while(l < r){

//cout << l << " " << r << endl;
if(s[l] == '0' and s[r] == '0'){
if(!flip) l++;
else r--;
}

else if(s[l] == '0' and s[r] == '1'){
if(flip){
flip = false;
ans++;
}
l++;
r--;
}

else if(s[l] == '1' and s[r] == '0'){
if(!flip){
ans++;
flip = true;
}
l++;
r--;
}

else if(s[l] == '1' and s[r] == '1'){
if(!flip) r--;
else l++;
}

}

cout << ans << endl;

}

return 0;
}

// 1001