JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Discussions Skill-building and Educational Discussion for Algorithm SPOJ LIS2
 SPOJ LIS2 | Reply Hello,This is a problem from SPOJ: http://www.spoj.pl/problems/LIS2/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?Thanks!
 Re: SPOJ LIS2 (response to post by Duc) | Reply I can draw a connection between this problem and NICEDAY (http://www.spoj.pl/problems/NICEDAY). See misof's comments here:http://forums.topcoder.com/?module=Thread&threadID=575041This 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.
 Forums Algorithm Discussions Skill-building and Educational Discussion for Algorithm SPOJ LIS2 Previous Thread  |  Next Thread