 # PREFIXFLIP - Editorial

Author: notsoloud
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

1758

None

# PROBLEM:

Given a binary string S, in one move you can flip (i.e, convert 0\to 1 and 1\to 0) some prefix of S.

Find the minimum number of flips to make S contain a substring of K ones.

# EXPLANATION:

Let’s fix a substring of length K and see how many moves we need to make it contain only ones.

Suppose the substring is A = A_LA_{L+1}\ldots A_R. Then,

• If A_i = 0, we need to flip a prefix that includes i an odd number of times.
• If A_i = 1, we need to flip a prefix that includes i an even number of times.

This should give you a greedy solution:

• If A_R = 1, then ignore it. Otherwise, flip the prefix [1, R].
• Then, repeat this with A_{R-1}, A_{R-2}, \ldots, A_L in order.

Analyzing this process, you’ll note that the number of flips is in fact determined exactly by the number of positions L \leq i \lt R such that A_i \neq A_{i+1}; in particular, if there are x such positions, then:

• If A_R = 0 then we need x+1 flips.
• If A_R = 1 then we need x flips.

Intuitively, we’re breaking the substring into contiguous ‘blocks’ of zeros and ones; after which each flip turns exactly one block into a block of ones.

This allows us to solve a single substring in \mathcal{O}(K). Repeating this for every substring will take \mathcal{O}(NK), which is too slow.

To improve this solution, notice that the answer for a substring is determined by exactly two things: the value of x (i.e, the number of adjacent pairs of unequal characters), and what the last character is.

So, suppose we know x for the substring starting at L. We can easily obtain it for the substring starting at L+1, since the only pairs that need to be looked at are (L, L+1) and (R, R+1) (here, R = L+K-1).

This allows us to move from one substring to the next in \mathcal{O}(1), giving us a solution in \mathcal{O}(N) overall.

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

Setter's code (C++)
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <math.h>
#include <ctime>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <cassert>
#define int 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;

const int N=500023;
bool vis[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 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){
}
}
}

void solve()
{
int ans = n;
int cnt = 0;
for(int i = 0; i<k-1; i++){
if(s[i] != s[i+1]){
cnt++;
}
}
if(s[k-1] == '0'){
ans = min(ans, cnt + 1);
}
else{
ans = min(ans, cnt);
}
for(int i = k-1; i<n-1; i++){
if(s[i] != s[i+1]){
cnt++;
}
if(s[i-k+1] != s[i-k+2]){
cnt--;
}
if(s[i+1] == '0'){
ans = min(ans, cnt + 1);
}
else{
ans = min(ans, cnt);
}
}
if(s[n-1] == '0'){
ans = min(ans, cnt + 1);
}
else{
ans = min(ans, cnt);
}
cout << ans;
}
int32_t 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);
while(T--){
solve();
cout<<'\n';
}
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
s = input()
ans = n
blocks = 1
for i in range(1, k):
blocks += s[i] != s[i-1]
if s[k-1] == '1': ans = blocks-1
else: ans = blocks
for i in range(k, n):
blocks += s[i] != s[i-1]
blocks -= s[i-k] != s[i-k+1]
if s[i] == '1': ans = min(ans, blocks-1)
else: ans = min(ans, blocks)
print(ans)

2 Likes

Prefix Sum + Sliding Window approach
https://www.codechef.com/viewsolution/83722805

2 Likes

Thanks for the solution.