Just tried it practice section and it works!
Thanks Ayush… I could not have guessed it.
For large common differences d, I do things a bit differently.
Let MAX be the maximum and MIN be the minimum. If |d| > (MAX-MIN)/2, then the length of the arithmetic subsequence is at most 2—any more than that and you’ll get a number larger than MAX or smaller than MIN. Therefore, the number of arithmetic subsequences with absolute common difference d is equal to ∑ C(x)C(x+d) for MIN ≤ x ≤ MAX-d, and C(x) is the number of indices in the array with value x.
The values C(x) can be precalculated in the beginning of a test case in O(N), and for a particular d with |d| > (MAX-MIN)/2, the sum can be calculated in MAX-MIN ≤ 100 operations.
If |d| ≤ (MAX-MIN)/2, we do the same DP approach as in the editorial. But now we’ve cut the runtime in half!
1 Like
Can you tell me why code is getting WA…
I used the same algorithm as you have told in ur editorial but still WA…
Soln link :-- http://www.codechef.com/viewsolution/4107416
Thnx in advance…
You are using pow(2,n) to calculate the value of total no of sub-sequences possible. Since
1<=n<=200000, 2^n will be a very huge number. You need to calculate it using fast exponentiation and keep a check when its value becomes more than 10^9+7. The no. of arithmetic progressions possible can also be greater than 10^9+7, so while calculating it keep a check on it also. Your program requires a lot of mod operations. Also long long int might give you TLE, change variables within range to int data type.
1 Like
^ it should be set to 0.
Now I am using fast exponentiation and proper modulus operation as u suggested…
But still getting WA…
soln link :-- http://www.codechef.com/viewsolution/4107666
Thnx for ur help…
DP always cripples my mind…
4 Likes
Finally got AC…
Got to learn about some modular airthmetic…
Thnx for ur help…
I am getting WA again n again. Can someone please point out why my solution is wrong ?
http://www.codechef.com/viewsolution/4108001
Thanks
Can somebody please into my solution.Used the exact same algorithm. Pairs to store the difference and the index. http://www.codechef.com/viewsolution/4101901. Thanks in advance
for cases where n=100 and all the 100 elements are same answer is 0 because then all the 2^n subsequences possible are in AP, but your program doesn’t give answer as 0 because the value in sum array overflows, you need to apply mod operation on sum array. Also take care to use mod operation only when required and not after each operation. Using mod without if condition might give you TLE. Also there are chances long long data type might give TLE, so use int data type for variables with small range.
Keep coding, you will learn many new things. 
thanks a lot. AC
from now on i will take care of adding MOD only where necessary and check bounds after WA.
that’s nice
Even after implementing the above idea and keeping the number of mod equations and variables of type LongLongInt at minimum, still getting TLE.
Please suggest corrections.
[http://www.codechef.com/viewsolution/4109359][1]
[1]: http://www.codechef.com/viewsolution/4109359
updated. What a silly mistake by me, sorry for inconvenience caused. Thank you for informing !!
@bazzzinga : log and take lot of time. Check the <a href="https://codechef_shared.s3.amazonaws.com/download/Solutions/2014/June/Setter/MAXPR.cpp">setter's solution</a> for modular expo. That may be the best replacement in your solution. Since every time you are checking whether a number lies in [0,1000000007], i think operator can be replaced with - operator if the condition is satisfied. Also since all numbers in your solution are always in [-2000000014,2000000014] because there’ll be no * operations after including the above suggestion, all datatypes can be changed to int.
1 Like
no prob! Very nice editorial, btw.