Page 1 of 1
LIS in O(nlog(k))
Posted: Tue Mar 28, 2006 3:03 pm
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.
Posted: Fri Apr 14, 2006 6:44 pm
by aminallam
Posted: Fri Apr 14, 2006 8:05 pm
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
Posted: Sun Apr 16, 2006 4:32 pm
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?
Posted: Sun Apr 16, 2006 4:47 pm
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
Posted: Wed May 03, 2006 2:16 pm
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))
Posted: Mon May 08, 2006 2:15 pm
by serur
I got it, thank you.
10534- very good question, I have had pleasure solving it.
Have fun, problemhunters!
Re: LIS in O(nlog(k))
Posted: Mon Sep 08, 2008 3:30 pm
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