CODEWITHSUNDEEP
algorithmdata-structures
sasha sami
sasha sami

Reputation: 525

Approach to LIS2 on spoj

I was solving problem LIS2 on spoj http://www.spoj.com/problems/LIS2/.I came across 2D segment tree but I guess it is not suitable for this problem.I read misof solution to NICEDAY on spoj which is similar to this problem according to this post: http://apps.topcoder.com/forums/;jsessionid=F39EBDDC41BEB792536BE044ADC8BA2A?module=Thread&threadID=615154&start=0&mc=2. Neither can't I understand the link between these two questions neither can I understand the complexity of misof's solution to NICEDAY.

PS:I don't want the whole solution also I don't want any approach through 2D segment tree, as it will be too complex for this problem(I have tried)

Upvotes: 3

Views: 2003

Answers (2)

Marsupito
Marsupito

Reputation: 79

To me, I don't think we can use 2D Segment Tree for this problem because we'll need up to a 10^5 x 10^5 table for the 2D Segment Tree, which is too large.

Upvotes: 1

IVlad
IVlad

Reputation: 43477

Think of how you would solve the 1D problem:

dp[i] = longest increasing subsequence that ends at position i.

For each i, we have to append a[i] to a j such that dp[j] is maximum and a[j] < a[i]. We can find this efficiently using advanced data structures by changing the definition of our dp array:

dp[i] = longest increasing subsequence that ends with the VALUE i

Now, initially dp[ a[i] ] = 1 for each position i. Then for each element a[i], you need the maximum of dp[0], dp[1], ..., dp[ a[i] - 1 ]. Then you have dp[ a[i] ] = mx + 1.

You can find this maximum by normalizing your array values (make sure they are all in the interval [1, n]). You can do this with a sort. For example, if your array is 42 562 13, the n = 3 and your new array will be 2 3 1.

This can be implemented easily with a segment tree that supports queries and updates for maximums. The time complexity will be O(n log n).

This can be extended quite easily to your problem by using 2D segment trees, obtaining time complexity O(n log^2 n), which should not be too complex at all. This involves using a segment tree whose nodes are also segment trees.

Upvotes: 1

Related Questions