Could anybody give me a detailed explanation of how to solve this question from DEC16 long challenge.

I know to find LIS in nlogn but due to the number of queries my solution gets 30 points and gets a TLE in larger cases.

Could anybody give me a detailed explanation of how to solve this question from DEC16 long challenge.

I know to find LIS in nlogn but due to the number of queries my solution gets 30 points and gets a TLE in larger cases.

1 Like

Let dp[i][j] denotes the maximum index k in the array (k<=i) such that there exists a sub-sequence of length j if we use the array elements in the range k to i . Also since sum of all array elements is 10^6 so the length of the largest LIS ever will be around 1500 (you can prove this easily). So we can compute this dp easily. Also note that if j>a[i] then you donâ€™t need to compute the value for the same. After computing the dp value, you can answer query of l,r using 2d range query. Just binary search over the length j such that j is the length of LIS and check if there exists any i such that l<=dp[i][j]<=i<=r. (We can do this using 2d range tree in log(n)^2). But i am not sure it would pass in 1 sec, but for 2 secs TL it will for sure. I got to learn this in my recent talk with the problem setter @sereja .

3 Likes