PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: S. Manuj Nanthan
Preparer: Tejas Pandey
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh
DIFFICULTY:
2056
PREREQUISITES:
Observation, prefix sums
PROBLEM:
You have a binary string S. You can swap any two of its elements for a cost of 1. At most once, you can also reverse one prefix of S for no cost. Find the minimum cost of obtaining the lexicographically smallest string from S.
EXPLANATION
Suppose S has x zeros and y ones. Obviously, the smallest string we can obtain is \underbrace{000\ldots000}_{x \text{ zeros}}\underbrace{111\ldots111}_{y\text{ ones}}, so we want to calculate the cost of reaching this.
Note that the operations can always be reordered so that the prefix reverse operation is performed first - if any swaps are made before the reverse operation, we could have just as well performed these swaps (on maybe different positions) after reversing the prefix.
So, suppose we fix the length of the prefix we are going to reverse, say i (0 \leq i \leq N). We would like to calculate the minimum number of swaps required to sort the string now.
This can be done as follows:
- Look at the first x characters. We want all of them to be 0-s, since doing this automatically ensures the last y characters are 1-s.
- If any of the first x characters is already a zero, it is in place and nothing needs to be done.
- If any of the first x characters is a one, it needs to be swapped out with a zero. This can be done in exactly one move, since each one among the first x characters will correspond to a one among the last y characters.
- So, the number of swaps required is exactly the number of ones among the first x characters! All that remains is to be able to calculate this quickly.
This leads us to the following:
- If 0 \leq i \leq x, the number of ones in the prefix of length x doesn’t change (only their positions may change, the number remains the same).
- If x \lt i \leq N, the length x prefix of the string after reversing upto i consists of the characters i, i-1, i-2, \ldots, i-x+1.
So, if we compute the prefix sum of the number of ones in the string, each case can be computed in \mathcal{O}(1), after which we can take the minimum over them all. This gives us an \mathcal{O}(N) solution to the problem.
TIME COMPLEXITY:
\mathcal{O}(N) per test case.
CODE:
Preparer's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
//freopen("inp1.in", "r", stdin);
//freopen("inp1.out", "w", stdout);
int t;
cin >> t;
while(t--) {
string s;
cin >> s;
int cnt = 0, ncnt = 0;
for(int i = 0; i < s.size(); i++) cnt += (s[i] == '0');
if(!cnt) {
cout << "0\n";
continue;
}
for(int i = 0; i < cnt; i++) ncnt += (s[i] == '0');
int ans = cnt - ncnt;
for(int i = cnt; i < s.size(); i++) {
ncnt -= (s[i - cnt] == '0');
ncnt += (s[i] == '0');
ans = min(ans, cnt - ncnt);
}
cout << ans << "\n";
}
}
Tester's code (C++, utkarsh_25dec)
//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,' ');
}
int sumN=0;
void solve()
{
string s=readString(1,100000,'\n');
int n=s.length();
sumN+=n;
assert(sumN<=500000);
for(auto ch:s)
assert(ch=='0' || ch=='1');
s='%'+s;
int cnt[n+1]={0};
int zeros=0;
for(int i=1;i<=n;i++)
{
cnt[i]=cnt[i-1];
if(s[i]=='1')
cnt[i]++;
else
zeros++;
}
int ans=1e9;
for(int i=1;i<=n;i++)
{
int j=i+zeros-1;
if(j>n)
break;
int req=cnt[j]-cnt[i-1];
ans=min(ans,req);
}
cout<<ans<<'\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,50000,'\n');
while(T--)
solve();
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's code (C++, tabr)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int n = (int) s.size();
vector<int> pref(n + 1);
for (int i = 0; i < n; i++) {
pref[i + 1] = pref[i] + (s[i] == '0');
}
int ans = n;
int ones = n - pref[n];
for (int i = 0; i <= ones; i++) {
ans = min(ans, pref[n] - pref[n - ones + i] + pref[i]);
}
cout << ans << endl;
}
return 0;
}
Editorialist's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
string s; cin >> s;
int n = s.size();
int ans = n;
vector<int> pref(n+2);
for (int i = 1; i <= n; ++i) {
pref[i] = s[i-1] == '1';
pref[i] += pref[i-1];
}
int z = count(begin(s), end(s), '0');
auto get = [&] (int i, int j) {if (j < i) return 0; return pref[j] - pref[i-1];};
for (int i = 0; i <= n; ++i) {
// flip upto i
if (i <= z) ans = min(ans, pref[z]);
else ans = min(ans, get(i-z+1, i));
}
cout << ans << '\n';
}
}
