MAXPR - Editorial

editorial
, , , , ,
31

The complexity given is for a single test case .

32

there is also O(100*N) solution. This can be done in a much faster way.
You can make it even more faster by fast exponentiation.
So, the time limit is not strict at all

33

@dpraveen what was the benefit of choosing limit of N as 2*10^5 instead of 10^5?

34

It is due to the way compiler works…

i also asked for the same here:

http://discuss.codechef.com/questions/44751/c11-just-a-pretty-face

35

@sansid There were many more optimisation that remove tle
like summing up the ans after all operation would be 100*200 which is 10 times faster than doing it after each modification.
Also you can use int here instead of long long. Using int my time was reduced by half.

36

long long int was giving me tle…changing to int gives AC

2 Likes
37

The time complexity should not depend upon the usage of int/long long int. Ideally the questions should focus on algorithmic or logical details rather than other things.

4 Likes
38

@dpraveen i am not able to understand why “sum” array is not set to 0 for each diff in the psuedo-code. Someone please explain this because even in editorial it is not mentioned that sum should be set to 0 for each diff, but sum[x] is supposed to contain sum of dp[i]'s such that A[i]=x for a particular value of diff.

39

the recursive dp was giving me TLE. changing it to a bottom up implementation got me AC

40

Just tried it practice section and it works!
Thanks Ayush… I could not have guessed it.

41

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
42

^ it should be set to 0.

43

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…

44

Finally got AC…
Got to learn about some modular airthmetic…
Thnx for ur help…

45

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.

46

Keep coding, you will learn many new things. :slight_smile:

47

thanks a lot. AC :slight_smile:
from now on i will take care of adding MOD only where necessary and check bounds after WA.

48

that’s nice :slight_smile:

49

updated. What a silly mistake by me, sorry for inconvenience caused. Thank you for informing !!

50

@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