PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Testers: iceknight1093, rivalq
Editorialist: iceknight1093
DIFFICULTY:
1758
PREREQUISITES:
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];
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,' ');
}
void solve()
{
int n = readIntSp(1, 300000);
int k = readIntLn(1, n);
string s = readStringLn(1, n);
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);
int T=readInt(1,2000,'\n');
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)