Hello, The May Long contest just concluded. I need some help regarding the problem CHEFCK. Unfortunately I couldn't solve it , even though I tried it for 4-5 days :( .

(http://www.codechef.com/MAY15/problems/CHEFCK).

I would describe my approach(es) to this problem and would appreciate it if someone could tell me where my thought process was slow/wrong. All of my codes are correct, I couldn't clear the 3rd subtask of the problem.

1st Approach

I initially , tried solving it by using A segment tree. The time was O(n + Q*log(2*k)), it timed out.

the link — http://www.codechef.com/viewsolution/6912313.

2nd Approach

I then got to know about Range Minimum Query from Topcoder. I read the article and then built the sparse table as described. Even that timed out. I divide the table into blocks of size log(n) and create a ST on the block minimums and then create ST for each and every block. Even this timed out.

The Link -; http://www.codechef.com/viewsolution/6928522

3rd Approach

Further optimization, I banged my head a little bit more and got to know about Cartesian Trees from Stanford CS166. I learn that there are only a limited number of block types for RMQ for a size b, there are 4^b rmq structures possible and that can be calculated using Cartesian Trees. I did that too. I calculate Cartesian tree number for each block and if it hasn't been calculated before, I calculate and memoize it in a table otherwise I reuse the already calculated RMQ structure. Unfortunately Even this timed out. I coded the approach given here and it was O(n*log(log(n) + (n/log(n))*(log(n/log(n)) + (4^b)*b*b)

(http://web.stanford.edu/class/archive/cs/cs166/cs166.1146/lectures/01/Slides01.pdf)

[submission link] — (http://www.codechef.com/viewsolution/6960288)http://www.codechef.com/viewsolution/6960288

4th and Final Approach

I then realized that the pseudo random generator was periodic (duh!) and the same block was repeating in the array A. I also got to know about Sliding Range Minimum Query , I implemented a solution but cleared just one testcase of the 3rd subtask. [Submission] — (http://www.codechef.com/viewsolution/6971896).

Could someone tell me What I failed to observe to solve this problem. Also, could someone brief me on how and when I should be using the Sliding RMQ method, The WCIPeg website is very brief about it. Would appreciate if someone could also tell me how they implemented the approach given on Topcoder using Euler Tour of the Cartesian Tree and so forth. I am reading the codes and the editorial and trying to understand now and would appreciate some help.

Sorry for the long post and not using latex for posting complexities. Thanks :)