CHEFCK - Editorial

editorial
, , , , ,
21

Why my code become accepted instead of TLE/WA ? I just change the portion

A[x]=(a*pm(A[x-1],m) + b*(A[x-1]%m)+c)%m;

/// where pm is a function which make the operation : { b=A[x-1]%m; return (b*b)%m; }

TO

A[x]=(a*A[x-1]*A[x-1] + b*A[x-1]+c)%m;

I think the second one should get WA instead of ACC .
Because (10^9*10^9 *10^9 +10^9*10^9+10^9)% 10^9 will overflow the long long integer’s range.
Am I wrong?
http://www.codechef.com/viewsolution/6980480

22

Please someone help me…

23

The last two comments in the code
// Remove the first element of the window,
// and from the list P as well, if it belongs there.
Somebody Please explain that part to me?

24

How am I supposed to solve the problem if I cannot even generate array A and Q queries in the given time for python? http://www.codechef.com/viewsolution/6989977

25

Here is an accepted version of your code -

http://www.codechef.com/viewsolution/6995617

  1. Changed lli to int wherever possible. lli is 64 bits and int is 32 bits - makes a lot of difference in such problems with strict time limits. In the arr[] array, you only need arr[x-1] in cases where overflow might occur so you can create a temporary variable which stores the previous arr[x-1] as a lli. Check the code.

  2. Removed extra % m. I personally only use %m when I am certain that there will be an overflow if I dont use it at that stage.

26

Time Limit was too strict. My solution with correct approach gave TLE in just 1 Task because of using too many mod operations. Wasted 4 days and lost 70 pts :frowning:

27

This means that for a particular k length segment/window say 1 to k then when this window will slide to 2 to k+1 then you need to exclude the 1st element out of window and also from the P list which means that this first element wont be used as a minimum ever because it does not exist in the segment so pop it out of your double ended queue structure

28

Another possible way to solve this problem is by using queue with O(1) min. query for sliding window - implementing it with two stacks is a well-known trick: https://www.codechef.com/viewsolution/7645078.

29

I did not understand the question as to how is range min query applicable in this.

Could someone please explain