CHEFCK - Editorial

@Sabari You can optimise your solution by using just using the following things::

  1. 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.
  2. 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

@madhur123Thanks a lot!!! cleared all sub-tasks. I never knew load posed by mod operation.

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

I am applying second method still getting TLE for one test case out of 6 solution link rkAgT2 - Online C++ Compiler & Debugging Tool - Ideone.com please help

http://www.codechef.com/viewsolution/6980436
could you explain, why isn’t my solution right?

@nil96 remove modulo while you are generating array use only once when number exceeds m.i was doing same mistake after 4 days i got this…:stuck_out_tongue:

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?

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

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:

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.

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

Could someone please explain

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

Title spelling wrong :slight_smile:

I am applying second method still getting TLE for one test case out of 6 solution link rkAgT2 - Online C++ Compiler & Debugging Tool - Ideone.com please help

Please someone help me…

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.

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