PIBRO Editorial

editorial
, , ,
3

your time complexity is O(n^2)

4

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

5

please inform me what’s wrong in this code:

link: CodeChef: Practical coding for everyone

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
7

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?

8

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

9

No,I think it is O(n) only

10

Why only one test case passes in this CodeChef: Practical coding for everyone
I used different approach.

11

No. It’s Linear.

12

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 ;
}
1 Like
13

Fails on the same testcase as this guy: Problem with code (PIBRO) - #2 by ssjgz

2 Likes
14

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 ;
}
15

Your code gives a different answer for

1
10 4
1111111111

every time I run it :slight_smile:

2 Likes
16

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 ;
}
17

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
18

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
20

plz explain me the logic @kmaaszraa

22

:rofl: :joy: :joy: :joy: :joy: :joy:

23

Can any one please see why my code is not working
#include<bits/stdc++.h>

using namespace std;

int main(){

int t ;

cin >> t ; 

for(int testcase = 0 ; testcase < t ; testcase++){

    int n , k ;

    cin >> n >> k ;

    if(n<=k){

        cout << n << endl ; 

        continue ; 

    }

    string PizzaBroccoli = "0" ;

    string temp ;

    cin >> temp ; 

    PizzaBroccoli = PizzaBroccoli + temp ;

    PizzaBroccoli = PizzaBroccoli + "0" ;

    //cout << PizzaBroccoli.size() << endl ;

    int LeftToRight[n+2] = {0}; 

    int RightToLeft[n+2] = {0};

    for(int i = 1 ; i <= n ; i++){

        if(PizzaBroccoli[i] == '1' ){

            LeftToRight[i] = LeftToRight[i-1] + 1 ;

        }

    }

    for(int i = n ; i >=1 ; i--){

        if(PizzaBroccoli[i] == '1' ){

            RightToLeft[i] = RightToLeft[i+1] + 1 ;

        }

    }

    /*

    for(int i = 1 ; i <= n ; i++)

    cout << LeftToRight[i] << " " ;

    cout << endl ;

    for(int i = 1 ; i <= n ; i++)

    cout << RightToLeft[i] <<" " ; 

    cout << endl ;

    */

    int maxPizza = INT_MIN ;

    for(int i = 1 ; i+k <= n ; i++){

        int total = RightToLeft[i+k] + LeftToRight[i-1] + k;

        maxPizza = max(maxPizza , total) ;

    }

    cout << maxPizza << endl ;

}

}

24

Here is your AC code, with a single change .you should iterate from i =0 upto i=n-k.
https://www.codechef.com/viewsolution/48832337

25

Try this
1
5 1
11011