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.

## LIS in O(nlog(k))

**Moderator:** Board moderators

See page 7 of the following:

http://ai.stanford.edu/~serafim/CS262_2 ... ture16.ppt

http://ai.stanford.edu/~serafim/CS262_2 ... ture16.ppt

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

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?

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?

Last edited by serur on Sat Apr 14, 2012 3:31 pm, edited 1 time in total.

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))

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))

Last edited by serur on Sat Apr 14, 2012 3:30 pm, edited 1 time in total.

### Re: LIS in O(nlog(k))

Can we do 103 with LIS of order nlognmf wrote:Here are some problems, which can be solved with LIS, or a similar algorithm:

103 Stacking Boxes

how about 10154 with LIS of order nlogn