**EDIT: Please help me in finding my mistake. In below link I’ve mention my problem in detail. **
SQRDSUB - Editorial - #37 by vijay72
I’ve been trying to a solve this problem and using bruteForce approach only complete the first sub Task and giving me TLE in rest of them. O(N^2)
So then I somehow able to come up with an O(N) and this algorithm is giving me AC on the On task only. And couldn’t able to find out the case on which it fails.
I’ve been trying for 3 days Not enough time but still.
Now I come up with a idea(Thanks to Discussion forum)
I have generated random test cases and pasting this to my first algorithm O(N^2) and comparing its output with this new algorithm and I find Out minor mistakes.
But now after generating millions of test cases my both of the algorithm is giving me same output.
but still I’m getting the WA.
So my question is what else I can do figure out the age cases.
btw now I’m not getting TLE but WA.
EDIT: The problem is live on the contest. That’s why could not share it here.
if there is any general solution to get out of this situation then please let me know. and I’m not gonna give up on this problem.
Can you give a description or link about your “this” problem?
I’ve edited the post. The problem is in the live contest so could not share about it here.
Keep Trying … No Point In Discussing Problem Of Running Contest Here
Should I delete this question?
Keep trying. I can’t tell you the test case for which your code might be wrong as it is from a live contest. I just suggest you to read the complete question once again and if you have any doubt you can ask that in comment section.
i think it is sqrdsub problem no ???
u really worked hard on this problem.I think now u should take a break think about corner cases code write a fresh code.All the best U deserve AC,
Yes. its SQRDSUB. I’m new to Competitive Programming that’s why I’m very slow. Btw I still couldn’t able to find out the fault in my code. I just checked the editorial and copied the tester code and put it into the test Case generator(Random numbers) checking if there is any case for which my algorithm produces different output and turns out its not. everything is working fine.
I think I’m missing some corner case.
but I know I’ll do it.
As Contest Is Over , Here Are Some More Custom Test Cases
3 2 3 5 6 3 5 2
ans - 18
3 2 3 5 6 3 5 5
ans - 18
2 6 5
ans -3
2 3 5 8
ans-7
2 3 8 5
ans 8
Dude I tried so hard in that question. I was getting AC on subtask 1 and only 1 AC in subtask 2(other were WA). Which was quite confusing and I was stuck on that for 3 days!
I end up changing every variable, even the loop variable, to long long int and got AC.
I’ve mention the link in the second line. The problem code is SQRDSUB.
Thanks for the test cases but I getting the same correct answer. Also the weird thing is after giving random test cases to my algorithm and the tester Solution I’m getting the exact same result.
I’ve been stuck on this for almost 10 days now and I have tried changing the name and even rewrite the algorithm.
I think I have tried the very simplest and minimal approach.
first loop will take care of odd
- Count the number of odd in an array and If any sub array has odd as its product.
second loop - this loop does the same thing but check for the divisibility by 4.
being the newbie I couldn’t come up with more simpler solution.
My approach was that
In the first loop, I just change all the input to array in 0,1,2. 0 means not divisible by 2 , 1 means only divisible by 2 and 2 means only divisible by 4(2*2).
See the thing is that any odd number can be a difference of square and any multiple of 4 , so any subarray which have sum 0 will satisfy and also any subarrays which have atleast sum 2 will also satisfy this condition as 2* 2* K(this is divisible by 4).
So if we count all subarrays which have sum 0 and sum greater or equal to 2 then we will have our answer!!
So in order to do that just find number of those subarrays which have sum=1(Number of subarrays having sum exactly equal to k - GeeksforGeeks) ( let it be X)
Then,
total number of subarrays - X will be ur answer.
instead of calculating odd+ div by 4, you can calculate total - div by 2… total you will get from formula in constant time and to find div by 2, you can change the array in 1 and 0 where 1 represents div by 2 only …
I’ll try this. but somewhere in back of my mind I still wanted to know the test case for which my algorithm fails.