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 :-- CodeChef: Practical coding for everyone
Thnx for ur helpā¦
Finally got ACā¦
Got to learn about some modular airthmeticā¦
Thnx for ur helpā¦
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
updated. What a silly mistake by me, sorry for inconvenience caused. Thank you for informing !!
@bazzzinga : log and % take lot of time. Check the setterās solution 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.
I feel the point of algorithm contest is not just to teach you algorithms but to code efficiently.
This is one of the questions where we need to consider of the constant factor in time complexity.
The difference between something taking 10 sec and something taking 1 sec could be a matter of considering the constant
actually, dp[i] is itself an array, where dp[i][100+d] refers to all those APs ending at the ith place, with d as their common difference.
In the editorial, the dp array is 1d, because they have used it in a loop from 1 to 200(or from -100 to 100 for that matter).
hence, in the first loop, dp[i] represents all the APs ending at ith place, with common difference -100.
so, add dp[i] from 1 to n to get all APs
Hope this makes it clear!
@wiseboy How dp[i] is a 2d array? In the O(n^2) solution, dp[i] denotes number of APās ending at i and they will use the loop 200 times to check all the possible values,so following the above rules my first comment should be correct.can you please elaborate with an example.
Oh, I am really sorry for the misunderstanding on my part!!
I thought you were talking about the O(n) solution.
yes, you are absolutely correct. and even your comment as well as calculation is.
The only problem is, to find all the APs, you have to do
total APs= summation(i=1 to n)dp[i].
Itās because you have to take in account all the APs, i.e., the APs ending at position 1, then at position 2 and so on.
hence, total=dp[1]+dp[2]+dp[3]=1+2+4=7.
Hope it helped!
Thanks for your help,I got it
yes, just for the sake of simplicity
1 Like