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.

can anyone please explain what is the problem in my code -
my code is understandable easily.
my code is -

#include <bits/stdc++.h>
using namespace std ;
int main()
{
    int t ;
    cin>>t ;
    while(t--)
    {
        int n,k ;
        cin>>n>>k ;
        string str ;
        cin>>str ;
        if(n==k)
        {
            cout<<n<<"\n" ;
            continue ;
        }
        vector<pair<int,int> > val ;
        int kmax=0 ;
        for(int i=0;i<n;i++)
        {
            if(str[i] == '1')
            {
                int j=i;
                for(j=i;j<n;j++)
                {
                    if(str[j] =='1')
                        kmax++ ;
                    else
                        { break ;}
                }
                val.push_back(make_pair(kmax,i) ) ;
                i=j-1 ;
                kmax=0 ;
            }
        }
        if(val.size()==0)
        {
            cout<<k<<"\n" ;
            continue ;
        }
        sort(val.begin(),val.end()) ;
        //cout<<"val is \n" ;       
        int ans=0,temp ;
        //vector<int> ans ;
        for(int i=val.size()-1;i>=0;i--)
        {
            if( val[i].second+1 > k )
            {
               temp = k + val[i].first ;
               if(temp>ans)
               {ans=temp;}
               //break ;
            }
            else
            {
                if( val[i].first + val[i].second + k - 1 < n )
                {
                    temp = val[i].first + k ;                
                    if(temp>ans)
                        ans = temp ;
                }
                else
                {
                  if(val[i].second + k < n)
                  {                     
                      temp = n - val[i].second ;
                      if(temp>ans)
                        ans=temp ;
                  }
                }
            }
        }
        cout<<ans<<"\n" ;
    }
    return 0 ;
}

Fails on the same testcase as this guy: Problem with code (PIBRO)

2 Likes

so I changed the code a little bit , having the data of the consecutive occurrences of 1’s in forward and backward direction, and then using it .
and here is my code but still I am getting W.A any guess why? please …

 #include <bits/stdc++.h>
using namespace std ;
int main()
{
    int t ;
    cin>>t ;
    while(t--)
    {
        int n,k ;
        cin>>n>>k ;
        string str ;
        cin>>str ;
        if(n<=k)
        {
            cout<<n<<"\n" ;
            continue ;
        }
        vector<pair<int,int> > val ;
        int forward[n] = {0},back[n]={0} ;
        int kmax=0 ;
        for(int i=0;i<n;i++)
        {
            if(str[i] == '1')
            {
                int j=i;
                for(j=i;j<n;j++)
                {
                    if(str[j] =='1')
                        {kmax++ ;forward[j]=kmax ;}
                    else
                        { break ;}
                }
                val.push_back(make_pair(kmax,i) ) ;
                i=j-1 ;
                kmax=0 ;
            }
        }
        kmax = 0 ;
        for(int i=n-1;i>=0;i--)
        {
            if(str[i]=='1')
            {
                int j=i ;
                for(j=i;j>=0;j--)
                {
                    if(str[j]=='1')
                    {
                        kmax++ ;
                        back[j] = kmax ;
                    }
                    else
                     break ;
                }
                i=j+1 ;
                kmax = 0 ;
            }
        }
        if(val.size()==0)
       {
            cout<<k<<"\n" ;
            continue ;
       }
        sort(val.begin(),val.end()) ;
        //cout<<"val is \n" ;       
        int ans=0,temp ;
        //vector<int> ans ;
        for(int i=val.size()-1;i>=0;i--)
        {
            if( val[i].second+1 > k )
            {
               temp = k + val[i].first + forward[ val[i].second - k - 1 ] ;
               if(temp>ans)
               {ans=temp;}
               //break ;
            }
            else
            {
                if( val[i].first + val[i].second + k - 1 < n )
                {                  
                    temp = val[i].first + k + back[ val[i].second + k + 1 ] ;                    
                    if(temp>ans)
                        ans = temp ;
                }
                else
                {
                  if(val[i].second + k < n)
                  {                      
                      temp = n - val[i].second  ;
                      if(temp>ans)
                        ans=temp ;
                  }
                  if( val[i].second + val[i].first  >= k )
                  {
                    temp = val[i].second + val[i].first + back[ val[i].second + val[i].first + 1 ] ;
                    if(temp>ans)
                      ans = temp ;  
                  }
                }
            }
        }
        cout<<ans<<"\n" ;
    }
    return 0 ;
}

Your code gives a different answer for

1
10 4
1111111111

every time I run it :slight_smile:

2 Likes

thanks a lot , i figured out that trying to do it using only the consecutive occurrences of 1’s isn’t correct, as their can be cases of selecting the substring that may contain the consecutive 1’s in between , so have to traverse the entire array and check for the answer.
So , basically the answer to this question lies in the maximum length we can have between (i to i+k) + the forward 1’s till (i-1) + the backward 1’s till (i+k)
but still I am getting W.A :confused: why??
my code -

#include <bits/stdc++.h>
using namespace std ;
int main()
{
    int t ;
    cin>>t ;
    while(t--)
    {
        int n,k ;
        cin>>n>>k ;
        string str ;
        cin>>str ;       
        vector<pair<int,int> > val ;
        int forward[n] = {0},back[n+2]={0} ;
        int kmax=0 ;
        if(n<=k)
        {
            cout<<n<<"\n" ;
            break ;
        }
        for(int i=0;i<n;i++)
        {
            if(str[i] == '1')
            {
                int j=i;
                for(j=i;j<n;j++)
                {
                    if(str[j] =='1')
                        {kmax++ ;forward[j]=kmax ;}
                    else
                        { break ;}
                }
                //val.push_back(make_pair(kmax,i) ) ;
                i=j-1 ;
                kmax=0 ;
            }
        }
        kmax = 0 ;
        for(int i=n-1;i>=0;i--)
        {
            if(str[i]=='1')
            {
                int j=i ;
                for(j=i;j>=0;j--)
                {
                    if(str[j]=='1')
                    {
                        kmax++ ;
                        back[j] = kmax ;
                    }
                    else
                     break ;
                }
                i=j+1 ;
                kmax = 0 ;
            }
        }     
       /*cout<<"______the forward array is________\n" ;
       for(auto f: forward)
          cout<<f<<" " ;
        cout<<"\n_____the backward array is_______\n" ;
        for(auto f: back)
          cout<<f<<" " ;
        cout<<"\n" ;*/
        int ans=0,temp ;      
        //vector<int> ans ;
        ans = max(ans,k+back[k]) ;
        for(int i=1;i+k<n;i++)
        {
            ans = max(ans, forward[i-1] + k + back[i+k] ) ;
        }
        //ans = max(ans,forward[n-1-k]+k) ;=        
        cout<<ans<<"\n" ;
    }
    return 0 ;
}

This solution fails for the following testcase:

1
5 4
10000

The answer should be 5:

Longest consecutive run of 1's = 5 obtained by changing the following marked range (of size 4) to all 1's: 
10000
 ^  ^
Giving: 
11111

just figured out how I used my last four hours :joy::joy::joy::joy: but didn’t find out a bug that was in front of my eyes, all the time:rofl::rofl::rofl::rofl:

if(n<=k)
        {
            cout<<n<<"\n" ;
            break ;
        }

that break statement instead of continue . :rofl::rofl::rofl:

1 Like