Can someone tell me why am i getting a runtime error for this solution.
Thanks in advance
https://www.codechef.com/viewsolution/25407101
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.
1 Like
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
1 Like
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. 
2 Likes
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.
1 Like
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