Nope because that is completely logical. Compiler won’t be able to interpret that when c0==c1*c1 => c1==x
1 Like
thankyou ! will remeber this next time 
1 Like
Understood. Thanks for the response. 
1 Like
can you please explain the condition a[i]!=a[i-1] and cnt1==j
i am counting the number of 1s in the range from i to i+p-1 (both inclusive) using prefix sum…
so when i=0–>no of 1s=a[i+p-1]-a[i]+1------(if a[i]=1)
---------------------------------=a[i+p-1]-a[i]---------(if a[i]!=1)
and when i!=0–>no of 1s=a[i+p-1]-a[i]+1— (if a[i]!=a[i-1])
------------------------------------=a[i+p-1]-a[i] ------(if a[i]==a[i-1])
try taking some examples and dry run my code on it you will understand everything…
happy coding !! 
1 Like
Getting TLE using Python. Is really time limit that strict ?
from math import sqrt
def Calc(s, size):
'''
The normal sliding window counter function
Counts how many sliding window of length=size have sum=ReqSum
'''
left,right = 0,size
CurSum,CurCount = sum(s[:size]),0
n,m = size,len(s)
ReqSum = (int(sqrt(1+4*n)-1)/2)
if CurSum==ReqSum:
CurCount += 1
while right < m:
CurSum -= s[left]
CurSum += s[right]
left += 1
right += 1
CurCount += 1 if CurSum == ReqSum else 0
return CurCount
def isSquare(n):
'''
Returns True if 4n+1 is a perfect square and sqrt(4n+1)-1 is even
'''
n = 4*n+1
m = int(sqrt(n))
return True if m*m==n and (int(sqrt(n))+1)%2==0 else False
def solve():
'''
function to solve each testcase
'''
s = list(map(int,input()))
ans,n = 0,len(s)
for i in range(1,n+1):
if isSquare(i):
ans += Calc(s,i)
print(ans)
if __name__=='__main__':
test = int(input().strip())
for testcase in range(test):
solve()
Edit : While the same implementation passes easily in c++
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
vector<int> s;
int n;
bool isSquare(int len){
// Returns True if 4n+1 is a perfect square and sqrt(4n+1)-1 is even
len = 4*len+1;
int n=sqrt(len);
if(n*n != len)
return false;
else if((n-1)%2 != 0)
return false;
return true;
}
int calc(int len){
/*
The normal sliding window counter function
Counts how many sliding window of length=size have sum=ReqSum
*/
int CurSum=0,ReqSum=((int)sqrt(4*len+1)-1)/2;
int left=0,right=0;
while(right < len){
CurSum += s[right];
right += 1;
}
int ans=0;
if(CurSum == ReqSum)
ans += 1;
while(right < s.size()){
CurSum -= s[left];
CurSum += s[right];
left += 1;
right += 1;
if(CurSum == ReqSum)
ans += 1;
}
return ans;
}
void solve(){
string ss; cin >> ss;
n = ss.size();
s.resize(n);
for(int i=0;i<n;i++){
s[i] = ss[i]-'0';
}
int ans=0;
for(int len=1;len<=n;len++){
if(isSquare(len)){
ans += calc(len);
}
}
cout << ans << '\n';
}
int main(){
int test;
cin >> test;
while(test--)
solve();
return 0;
}
basically suppose you already know the answer for string s for length n and a new character is added so n new substrings will now added. Now you have to check how many new substrings will satisfy the given criteria and add it to the previous answer and it will be your new ans. complexity of it will o(n sq) but if you notice any substring that satisfy the given condition will always be of length ixi+i i.e. 1,6,12,20 etc so instead of checking every new substring you can check only substring having length of type ixi+i complexity will be optimized to o(n root n) using this method.Hope you understand and sorry for my bad english this is the link of the approach i used.
my simple java solution, using sliding windows,
uses O(1) extra space, time complexity same as editorial
Was stuck for 2 hr because of this, i was thinking of O(n) solution, finally had to give up and see tutorial to find this! so disappointing
1 Like
Those who are not able to understand this problem you must dry run this question on paper and then think how prefix-sum+ sliding window + O(n*sqrt(n)) can work here . This is enough hint to solve this problem .
I am telling my solution hope this will help some beginner
- First observation of this is that length of string is always (zero==x ) x*x+x , because *one one =zero so no of one are x*x so total length is x*x+x .
- then we got size of your window which is always of length x*x+x then next step is to calculate no of zeros and ones for each index which we done using prefix as it is O(n) approach .
- then for each widow check whether one*one ==zero then count++ .
then print count .
Sorry for my poor english !
I did’t get this statement , could you eleborate more on this if(cnt1==i)
aye, your solution is O(n*n)
as mentioned in the editorial, maximum length of window can be, (x*x +x) where x is count1.
so you iterate ,
for(int i=1; i*i + i <= s.length(); i++)
now,
as @l_returns said in above comments,
don’t use multiplication(since it can be costly) i.e rather than using one*one == zero,
use (one == 1)
thats it!
Hi, this is my code in C++ using the same approach as the editorialist’s. I am getting TLE. Can anyone figure out the problem in it?
Here’s the link to my solution : CodeChef: Practical coding for everyone
Thanks for the optimization. I took the same approach but faced TLE. This one solved it!
Still, didn’t know that multiplication could be this costly.
i am unable to get the solution can anyone explain me the working of this source code