PIBRO Editorial

PROBLEM LINK:

Practice
Contest

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;
} 
6 Likes

Got TLE one test :’(
https://www.codechef.com/viewsolution/28027923

Any way to optimize this?

your time complexity is O(n^2)

Getting WA in 2 test case

What am i missing here …??

https://www.codechef.com/viewsolution/28014565

#include<bits/stdc++.h>
#include
#define ll long long int

using namespace std;

int main(){

ll t; cin>>t;

while(t–){

ll n,k;  cin>>n>>k;
string s;  cin>>s;
int ans = INT_MIN, tmp = 0, kk = 0;

if(n <= k){
    ans = n;
    cout<<ans<<endl;
}
else{
//   ans = k;
for(int i=0;i<n-k;i++){
    int j = i+k;
    int l = i-1;
    tmp = k;
    for(;j<n;j++){
        if(s[j] == '1'){
            tmp++;
        }
        else{
            break;
        }
    }

    for(;l>=0;l--){
        if(s[l] == '1'){
            tmp++;
        }
        else{
            break;
        }
    }

ans = max(ans,tmp);
}
cout<<ans<<endl;
}

}

return 0;
}

please inform me what’s wrong in this code:

link: https://www.codechef.com/viewsolution/28033093

from itertools import groupby
t = int(input())

while t>0:
n, k = input().split()
n = int(n)
k = int(k)
st = input()

ans = [0]

for x, y in groupby(st):
    if x == '1':
        ans.append(len(list(y)))
    #print(x , )

a = min(n, max(ans)+k)
print(a)

t = t-1

What’s wrong with this approach.here i am trying to find max consecutive ones and then adding k to it taking care of boundary conditions.

https://www.codechef.com/viewsolution/28013706

can you please reveal a testcase for which my approach doesn’t work?

Can anyone please tell why tle in my code? According to me its time complexity is n*t which should be acceptable.

#include<bits/stdc++.h>
#define ll long long
#define vi vector
#define vll vector
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,n) for(int i=n-1;i>=0;i–)
#define si set
#define sll set
#define ins insert
#define vpp vector<pair<int,int>>
#define mp make_pair
#define ft first
#define sc second
using namespace std;

struct interval{
int f,s;
};
int main(){
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
string s;
cin>>s;
int i=0;
interval v[n];
int mx=INT_MIN;
while(i<n){
int j=i;
if(s[i]==‘0’){
i++;
if(mx<0)
mx=0;
continue;
}
while(j<n && s[j]==‘1’){
j++;
}
if(j-i >mx)
mx=j-i;
i=j;
}
i=0;
int p=0;
int ans=0;
while(i<n){
int j=i;
if(s[i]==‘0’){
i++;
if(mx==0){
ans=min(n,k);
break;
}
continue;
}
while(j<n && s[j]==‘1’){
j++;
}
if(j-i ==mx){
v[p].f=i;
v[p].s=j-1;
p++;
}
i=j;
}
i=0;
if(ans==0){
while(i<p){
int l=v[i].s-v[i].f+1;
if((v[i].s+k < n)||(v[i].f-k>=0)){
ans=l+k;
break;
}else{
int op1,op2;
if(v[i].s+k >= n){
op1=n-v[i].f;
}if(v[i].f-k<0){
op2=v[i].s+1;
}
if(ans<max(op1,op2)){
ans=max(op1,op2);
}
}
}
}
cout<<ans<<"\n";
}
return 0;
}

No,I think it is O(n) only

Why only one test case passes in this https://www.codechef.com/viewsolution/28054598
I used different approach.

No. It’s Linear.