Can someone tell me why am i getting a runtime error for this solution.

Thanks in advance

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

# BDGFT - Editorial

just dry run the code and you will understand it by yourself…

@l_returns

Thanks a lot for pointing out the teeny tiny liitle optimisation. I was also doing the unnecessary multiplication and getting a TLE. Your hack is sleek and elegant.

yeah , i was copying that full dictionary, now i have changed my code a bit, but it is still timing out, please have a look.

Welcome \hspace{0mm}

I am getting Wrong answer with my code but most of the test cases gave correct answer.Someone help pls !

#include <bits/stdc++.h>

using namespace std;

int main() {

```
int t; cin>>t;
while(t--)
{
string s; cin>>s;
int n = s.length() , cnt1=0 ;
for(int i=0;i<n;++i)
{
if(s[i]=='1')
cnt1++;
s[i]=cnt1 + '0';
}
int ss=0,times=0;
for(int i=1; i<=cnt1 && (i*i + i)<=n ; ++i)
{
int k= i + (i*i) ;
ss= s[k-1] - '0';
if(ss==i)
times++;
for(int z=1; z<= n-k ;++z)
{
ss = s[z+k-1] - s[z-1] ;
if(ss==i)
times++;
}
}
cout<<times<<endl;
}
return 0;
```

}

I have a similar approach as the editorial,can anyone tell me why it’s TLE?

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

try writing "System.out.println(e); " in the catch block

I tried implementing the approach mentioned but i get time limit exceeded.

Can u suggest any improvements???

//MY CODE:

#include

#include<math.h>

using namespace std;

int main() {

long T;

cin>>T;

while(T–)

{

string s;

cin>>s;

```
long size=s.size(),x=1,ans=0;
for(x;x<=pow(size,0.5);x++)
{
long req_size=x*x+x,cnt1=0,i=0,j=i+req_size-1;
if(req_size>size){break;}
for(i=0;i<req_size;i++,j++)
{
if(s[i]=='1'){ cnt1++;}
}
i--;j--;
if(cnt1==x){ans++;}
while(i<=s.size()-req_size)
{
if(s[i-1]=='1'){cnt1--;}
if(j<size && s[j]=='1'){cnt1++;}
if(cnt1==x){ans++;}
i++;j++;
}
}
cout<<ans<<endl;
}
return 0;
```

}

Why he(@taran_1407 ) did **len = i*i+i**,

As expained **x** is count of 1’s, he is using **i** (index/position)??

I’m confused here, there should be count of 1’s???

I used the sliding window method, but still I’m getting a TLE. Here’s my code. Can someone please help?

@raisinten

Refer this solution

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

Replace the multiplication operator inside for loop with the comparison operator as multiplication is an expensive operation in terms of the time consumed and you will be able to get rid of the TLE

Thank you so much! Solved it here.

I knew that multiplication is really slow, but I didn’t know that it would slow my code down so much. Is compiler optimization not at play here? Thank you.

I am having a doubt in the first given sample test case…

If special ones are those whose cnt0=cnt1*cnt1… then apart from the given pairs (1,2) ; (1,6) ; (2,3) ; (5,6) ,what I think is (2,4) ; (2,5) ; (3,6) ; (4,6) should also be the answers ???

May be I am not getting the concept of special strings. Please help me out…

```
(2,4) ; (2,5) ; (3,6) ; (4,6)
010001 cnt1 cnt0 cnt1 * cnt1
(2, 4) - 100 1 2 1
(2, 5) - 1000 1 3 1
(3, 6) - 0001 1 3 1
(4, 6) - 001 1 2 1
Since in the above columns, it can be seen that cnt0 != cnt1 * cnt1, hence it doesn't work out.
```

Yes, In my code, i had used i.

can anybody help me with tle using this approach how to reduce it

#include

#include<string.h>

#include<math.h>

using namespace std;

int main() {

// your code goes here

```
int t,i,j,l,x,k,cnt1=0,cnt0=0,ans=0;
string s;
cin>>t;
while(t--)
{
cin>>s;
k=sqrt(s.length());
for(i=1;i<=k;i++)
{
x=i*i+i;
cnt1=0;cnt0=0;
for(j=0;j<x;j++)
{
if(s[j]=='0')
cnt0++;
else
cnt1++;
}
if(cnt0==cnt1*cnt1)
{
// cout<<" pair is [0 , "<<x-1<<" ]\n";
ans++;
}
l=0;
for(j=x;j<s.length();j++)
{
if(s[l]=='0')
{ if(cnt0>0)
cnt0--;
// cout<<"works0- and cnt0 is "<<cnt0<<"\n";
}
else
{ if(cnt1>0)
cnt1--;
// cout<<"works1- and cnt1 is "<<cnt1<<"\n";
}
if(s[j]=='0')
{cnt0++;
// cout<<"works0+ \n";
}
else
{cnt1++;
// cout<<"works1+ \n";
}
if(cnt0==cnt1*cnt1)
{
// cout<<"cnt0 is "<<cnt0<<" cnt1 is "<<cnt1<<" ans is "<<ans<<"\n";
// cout<<"indxes are [ "<<l+1<<" , "<<j<<" ] \n";
ans++;}
//cout<<"indxes are [ "<<l+1<<" , "<<j<<" ] \n";
l++;
}
}
cout<<ans<<"\n";
cnt1=0;cnt0=0;ans=0;
}
return 0;
```

}

Replace “`if(cnt0==cnt1*cnt1)`

” with “`if(cnt1==i)`

” and let me know if its still TLE

still it is tle

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

Two more edits and its AC

Your code is taking more time because of extra “if” conditions.

Even one “if” statement makes difference when number of operations are huge.

This is intended approach which removes many comparisons and hence it takes 0.15 secs only.

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