CHEFCK - Editorial

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