Register Now
Member Count: 626,145 - April 17, 2014  [Get Time]
Login
forums   
Round Tables
News Discussions
Algorithm Matches
Marathon Matches
NASA Tournament Lab
Software Forums
TopCoder Cookbook
High School Matches
Sponsor Discussions
Search Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Forums Round Tables Educational Discussion 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=575041
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.
Forums Round Tables Educational Discussion SPOJ LIS2
Previous Thread  |  Next Thread
RSS