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