question link:[link text][1]
utkarsh_lath’s answer(best answer):[link text][2]
I know this technique already,But I can’t feel why we are adding m[f4[i]-f7[i]] and incrementing
it by 1?
Any illustration would be highly appreciated…
[2]: http://www.codechef.com/viewsolution/820869 link
please help me!!
Any link would suffice!!!
[1]: http://www.codechef.com/problems/LUCKY1/ link
EDIT: if you have not read the editorial,read it first as the editorialist is definitely more able in explaining the solution.
Let me first briefly tell the initial idea and then how are we computing the ans.
So, the problem asks us to find the number of pairs (L,R) such that sum(f4[i])=sum(f7[i]) where sum is over the range [L,R]. This is same as saying find pairs (L,R) such that sum(f4[i]-f7[i]) = 0.
So , if we maintain an array of f4-f7 , the question asks us to find pair of indices (L,R) so that the sum of the sub-array so formed is 0.
Now lets us form a prefix sum array from the above array, say B. Now we see the above condition reduces to find L,R so that B[L-1] = B[R]
so we have to find number of possible pairs i,j such that (i is less than j) and B[i] = B[j].
Fortunately for us, due to the definition of f4[i] & f7[i] , f4-f7 can take only very small values, hence all elements of B are small.so we can maintain a frequency table for each possible value of B[i].
suppose i say , there are 5 elements in B, 2 have value 9 and 3 have value 1. when you find the number of pairs i,j such that B[i]= B[j]. you see the values 9 & 1 don’t matter, only their frequency does, and the answer will be 2choose2+3choose2.
So given the frequency table for any N , all you have to do is return sum of freqchoose2 over all values of frequency.
Now to your main question.I am sorry if you already knew all of the above but i could not be sure till where were you clear.
the above approach is correct and has Complexity O(N) for each test case.
but we can do better. each test case is different only in terms of N; suppose you have calculated till for some N, now in calculating for N+1,a new entry will be added to array B, i.e.
prefixsum(f4[i]-f7[i]) for 1<=i<=N+1 you have to this new entry will change frequency of only one of the values. lets say earlier frequency was S and now becomes S+1. the contribution to answer for N+1 is (S+1)choose2 . So difference between answer for N and N+1 is (S+1)choose2-Schoose2 which is S. that is why you added the current frequency to the value (its not m(f4-f7) but freq[prefixsum(f4-f7)] as is given in editorial)and then updated the frequency by 1, for susequent calculations for N+2,N+3,…
Since its inductive you can find for all values till 10^5 then answer for each test case in O(1) time.
DONE!!! Thanks a lot for your help…
Glad that I could help.