Can you please explain how did you estimated the size of the frequency array ?As maximum size might have to be something like 10^10 ?
You only care about subarray sums up to X (since values are non-negative)
@swapnil159 I was also approaching the problem in the same way.Looks like the map was the only reason I was getting TLE. Thanks for the information.
1 Like
SImple:
By the above given maths , Finally you will get X = sz * (sum of two subarrays of size sz)
So sz divides X. Find all the divisors of X and store them. For every S = X/sz , find the sum of two subarrays whose sum is S using sliding window method.
I am getting different results whle submitting my solution in different C++ standards. Here is my code
This is the result with C++ 14
This is the result with C++ 17
Please look into this @admins @taran_1407 . Also if anyone can point out the mistake, I’ll be grateful.
My code’s time complexity is also O( sqrt(X)+d(X)∗N) then why TLE
can somebody tell me what is wrong
my code Link
Thanks
Can someone plz explain why is time limit 3 sec in this problem??
1 Like
Its already very tight bro why do you want to reduce it even further 
?
https://www.codechef.com/viewsolution/34840483
can anyone tell the mistake in my code/logic please
i would be very thankfull
can u please tell why we are considering freq[z-s] in answer and not simple freq[z] in the editorial?
Bij= Ai+Aij
if we take take submatrix of length 3
then ,
sum = B00+B01+…+B22
see if you open up each Bij as Ai+Aj
then all Ai & Aj in the sum will be multiple of 3(which is also the side length of submatrix)
so 3 is a factor of sum
and we want those submatrix whose ,sum = X
hence 3 should also be the factor of X.
In the above e.g.
considering this cell (1,1) & (3,3) we get side length = 3
sum of subarray with these two cell at edge = (1+1+3+3) * 3 = 24
but in actual the sum is 2+3+4+3+4+5+4+5+6 =36 , hence it may contradict
please guide me if i got the above e.g. in wrong aspect(probably my misconception)!
I applied the approach mentioned in the editorial post contest ,
still getting that 3 second TLE
can anyone find any unecessary additional run in my code to reduce time
https://www.codechef.com/viewsolution/34857515
(P.S. - comment are mentioned sidewise to clarify the all steps in code)
@ankit0038 Because the equation we get is X = sz * (sum of two subarrays)
Here we calculate all possible sum of subarrays of size sz and that is stored in the freq array.
From the above equation, the we need to find a pair whose sum is X/sz. That is the reason why we store all sums and calculate the other.
To simplify, let us take an equation a = b + c
We have b’s to know c’s we do a-b right, same idea
no that would be (1+2+3+1+2+3) * 3 = 36.
https://www.codechef.com/viewsolution/34862345
some one please help on this WA and one TLE also…
i explained this code above 
Here’s the catch
what if we take array A : 2 3 5
then subarray(such that Bij=Ai+Aj) will be
4 5 7
5 6 8
7 8 10
In this e.g.,
considering the cell (1,1) & (3,3) as edge we get side length = 3
sum of subarray with these two cell at edge = (1+2+3+1+2+3) * 3 = 36 = X
but in actual the sum is 4+5+7+5+6+8+7+8+10 = 60 , hence it may contradict
as X not equal to sum of subarray
please guide me if i got the above e.g. in wrong aspect(probably my misconception)!
Yeah, Got it! Thanks buddy.