@Sabari You can optimise your solution by using just using the following things::
While generating the array A[] don’t use power() function. since every time t is taken to the power of x which is also equal to the iteration of loop, so simply make a variable and in every iteration of loop multiply it by t.
Use % (modulo) only if a number becomes greater or equal to modulo … ie. if(A[x] >= m ) then take modulo.
Rest is all fine…I was also doing same mistake…and i’ve done about 60 submissions
For referance you can see my submission here link text link text
I used Sparse Table Algorithm and i am not getting why it gives SIGSEGV for subtask 3 (after running for 2 secs). Please help and guide me. Here is my solution : CodeChef: Practical coding for everyone
I used Sparse Table Algorithm and i am not getting why it gives SIGSEGV for subtask 3 (after running for 2 secs). Please help and guide me. Here is my solution : CodeChef: Practical coding for everyone
I used Sparse Table to solve this problem. Can someone please tell me why I am getting TLE in last test case of third subtask.Here is my solution : CodeChef: Practical coding for everyone
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
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?
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
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.
Yes. Sparse Table Algorithm will give you 100 points, but after so many optimizations & that too will bring the runtime just inside the specified limits…
Here’s my solution if you want some reference: CodeChef: Practical coding for everyone
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.
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.
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