LIS in O(nlog(k))

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

LIS in O(nlog(k))

Post by serur »

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
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.

Post by aminallam »


Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur »

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?
Last edited by serur on Sat Apr 14, 2012 3:31 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur »

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)) :roll:
Last edited by serur on Sat Apr 14, 2012 3:30 pm, edited 1 time in total.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur »

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

Have fun, problemhunters!

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: LIS in O(nlog(k))

Post by tryit1 »

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

Post Reply

Return to “Algorithms”