PROBLEM LINK:
Tester: Kasra Mazaheri
Editorialist: Hussain Kara Fallah
PROBLEM EXPLANATION
Given an array A[1 \ldots N] consisting of N binary digits (0,1) and a single integer K. You can select only one segment (subarray) of length K and change all zeroes inside this segment to 1.
Find the maximum number of consecutive ones inside the array you can achieve after applying the mentioned operation once.
DIFFICULTY:
Easy
CONSTRAINTS
1 \leq N \leq 10^5
EXPLANATION:
Let’s define 2 arrays head,tail such that:
head_i denotes the number of consecutive 1 (ones) to the left of i_{th} element (the element itself not included).
tail_i denotes the number of consecutive 1 (ones) to the right of i_{th} element (the element itself not included).
How to calculate each?
If A_{i-1}=0 then head_i=0
If A_{i-1}=1 then head_i=head_{i-1}+1
If A_{i+1}=0 then tail_i=0
If A_{i+1}=1 then tail_i=tail_{i+1}+1
Now how to pick the best segment?
Easy, let’s try all possible choices. Assume we pick the element with index st as the starting element then we will change all elements with indices in the range [st,st+K-1] into ones. So we would result in a segment made of ones of length head_{st}+K+tail_{st+K-1}
Try all possible st and pick the best result. Check implementation for details.
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
int T , n , K , head[1<<17] , tail[1<<17];
string str;
int main(){
cin>>T;
while(T--){
cin>>n>>K>>str;
for(int j = 1 ; j < n ; j++) {
if (str[j - 1] == '1')
head[j] = head[j - 1] + 1;
else head[j] = 0;
}
for(int j = n - 2 ; j >= 0 ; j--) {
if (str[j + 1] == '1')
tail[j] = tail[j + 1] + 1;
else tail[j] = 0;
}
int ans = 0;
for(int j = 0 ; j + K <= n ; j++)
ans = max(ans , K + head[j] + tail[j + K - 1]);
cout<<ans<<endl;
}
}
Tester Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int q, n, k, L[N], R[N];
char S[N];
int main()
{
scanf("%d", &q);
for (; q; q --)
{
scanf("%d%d%s", &n, &k, &S[1]);
for (int i = 0; i <= n + 1; i ++)
L[i] = R[i] = 0;
for (int i = 1; i <= n; i ++)
if (S[i] == '1')
L[i] = L[i - 1] + 1;
for (int i = n; i; i --)
if (S[i] == '1')
R[i] = R[i + 1] + 1;
int Mx = 0;
for (int i = 1; i + k - 1 <= n; i ++)
Mx = max(Mx, L[i - 1] + k + R[i + k]);
printf("%d\n", Mx);
}
return 0;
}