Coding Blocks 1 count problem

problem link
https://hack.codingblocks.com/practice/p/346/916

WHY I am getting runtime error in 2 cases only
code is
#include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
long long int i,j,k,l,m,n,o,p,q,r,s,t,a[1000000],prefix[1000000],e,mid;
cin>>n>>k;
prefix[0]=0;
for(i=1;i<=n;i++)
{
cin>>a[i];
prefix[i]=prefix[i-1];
if(a[i]==0)
prefix[i]+=1;
}
m=-10000000;
l=0;
r=0;
for(i=1;i<=n;i++)
{
s=i;
e=n+1;
while(s<=e)
{
mid=(s+e)/2;
if(prefix[mid]-prefix[i-1]<=k)
{
j=mid;
s=mid+1;
}
else
{
e=mid-1;
}
}
if(j-i+1>m)
{
l=i;
r=j;
m=j-i+1;
}
}
for(i=l;i<=r;i++)
{
a[i]=1;
}
cout<<m<<endl;
for(i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}

Anyone please tell me about my runtime error.

It looks like for each i, you’re trying to find a j >= i such that the range [i,j] contains at most k 0’s - is that correct?

If so, it’s computing incorrect values for the sample testcase:

10 2
1 0 0 1 0 1 0 1 0 1

In particular, for i = 6, it’s giving j = 11 leading to m = 6 when it should be 5. I think :slight_smile: So it might be as simple as clamping j to not exceed n - my randomised tests, with this change, seem to be giving results that agree with a naive, brute force approach.

Add a bit of diagnostic output (like I did ;)) to help you debug :slight_smile:

Also, the question is ambiguous - for the sample input, there appear to be multiple ways of flipping k 0’s that give the same maximum run of 1s (5) - which are you supposed to output?

Edit:

TL;DR - add

if (j > n)
   j = n;

before the if(j-i+1>m).