Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
SPOJ LIS2 | Reply
This is a problem from SPOJ:
My algorithm is O(nlog^2n) used 2d segment tree , but it get time limit exceeded. I think it's because the constant factor is large.
Could anyone help me about how to optimize it, or is there a faster algorithm?
Re: SPOJ LIS2 (response to post by Duc) | Reply
I can draw a connection between this problem and NICEDAY ( See misof's comments here:
This still gives O(N log^2 N), but it is very fast - I got 1.90 seconds on the judge.
Re: SPOJ LIS2 (response to post by bbi5291) | Reply
Can you please explain what the relation is ?
Re: SPOJ LIS2 (response to post by Duc) | Reply
Some people got accepted with O(N log^2 N), using 2D segment tree/BIT. However I didn't, so I believe they did heavy constant optimization in it.

I finally got accepted using O(N log N log M) algorithm, where N is the number of items and M is the actual LIS. You may recall O(N log M) algorithm to solve LIS (M = length of LIS), and extend it into 2D version.