LIS in O(nlog(k))

serur · Post by **serur** » Tue Mar 28, 2006 3:03 pm

Hello everyone!
I read in Halim's website the explanation of O(nlog(k)) algo for LIS,
it seems I have grasped the main idea(for I got AC 231-"Testing the Catcher"), but how to restore the LIS itself and even how to maintain the predecessor array- it is still a mystery for me...
Would you be so kind to explain what is the the crux?
Is this multiple input problem?
If you want to cast a glance on my code (which invariably gives WA, though behaves well for my own I/O

), I'll send it immediately.

Thank you.

aminallam · Post by **aminallam** » Fri Apr 14, 2006 6:44 pm

See page 7 of the following:
http://ai.stanford.edu/~serafim/CS262_2 ... ture16.ppt

Darko · Post by **Darko** » Fri Apr 14, 2006 8:05 pm

For O(nlogk) I actually liked this one (just recently learned it):
http://en.wikipedia.org/wiki/Patience_sorting

I tried for some time to figure out what the explanation on Algorithmist meant, and then I ran into the link above. It basically says the same, but is easily understandable and (at least it was for me) easy to implement.

Darko

serur · Post by **serur** » Sun Apr 16, 2006 4:32 pm

Thank you so much Darko for your reply- it was of considerable use, for Algorithmist explains this stuff really good and after peruzing their implementation I did get it work for me too.
481-What goes up
497-Strategic defence
these are two that I got accepted using this algo, would you be so kind as to point out another problems from uva which are amenable do this elegant LIS algo?

mf · Post by mf » Sun Apr 16, 2006 4:47 pm

Here are some problems, which can be solved with LIS, or a similar algorithm:
10635 Prince and Princess
10534 Wavio Sequence
10131 Is Bigger Smarter
10051 Tower of Cubes
103 Stacking Boxes
10154 Weights and Measures
11003 Boxes

serur · Post by **serur** » Wed May 03, 2006 2:16 pm

Thank you mf for pointing out such good problems!

Ive just solved them all except 10534- I got TLE, and I'm curious to know what's the time complexity of your algo? Mine is O(n*n*log(n))

serur · Post by **serur** » Mon May 08, 2006 2:15 pm

I got it, thank you.
10534- very good question, I have had pleasure solving it.

Have fun, problemhunters!

tryit1 · Post by **tryit1** » Mon Sep 08, 2008 3:30 pm

mf wrote:Here are some problems, which can be solved with LIS, or a similar algorithm:
103 Stacking Boxes

Can we do 103 with LIS of order nlogn

how about 10154 with LIS of order nlogn

OJ Board

LIS in O(nlog(k))

LIS in O(nlog(k))

Re: LIS in O(nlog(k))