I am new in DP, in fact this is my first program on DP, my code shows TLE, although I think I am using it correctly(which obviously I’m not). I am using the same logic as in the editorial for this problem, http://discuss.codechef.com/problems/FROGV.
Please look at my code, and tell me why its showing TLE(works fine for small inputs), most probably the error will be in my DP function, but I cant figure it out. Help appreciated, thanks.
http://www.codechef.com/viewsolution/5484068
Your code answers each query in O(n). I can think of O(1) implementation. So think! 
2 Likes
@p00r Just help me out with this, where is the ‘n’ in O(n) coming from? Is it due to my DP function? Or the way I search at the end(the for loop that runs from 1 to n)? Or both of them. Also, as I am new in DP, can you also tell me if my DP function is the correct way to implement it or does it need improvements? Thanks.
Also, the method in the editorial solves the question in O(n*log(n)) time.
The ‘n’ comes from the loop where you search for the new index after sorting. You can make it efficient and find it in O(1) time. My solution link : http://www.codechef.com/viewsolution/4410253 but think on your own before checking mine!
@p00r I cant figure it out, please tell me how I can do this, I do not understand your code, so tell me with reference to my code, thanks.
@p00r I got the time complexity out of the way, and now its giving me wrong answer. I am really frustrated, stuck on the same problem for 2 days. Please help me, give me some test cases for which this code fails.
http://www.codechef.com/viewsolution/5487570