PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Practice
Setter: Shivansh Agarwal
Testers: Nishank Suresh and Abhinav Sharma
Editorialist: Anish Ashish Kasegaonkar
DIFFICULTY
1112
PREREQUISITES
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 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,' ');
}
/*
------------------------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(){
int n = readIntLn(1,2e5);
sum_n+=n;
string s = readStringLn(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;
t = readIntLn(1,2e5);
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. 