Page 1 of 3

10534 - Wavio Sequence

Posted: Thu Jul 31, 2003 7:26 am
by titid_gede
how to solve this probleM without getting TLE? is there algo which run linear time?

Posted: Thu Jul 31, 2003 8:18 am
by Dominik Michniewski
This question is intresting to me too ...
This problem looks like LIS, but this has O(N^2) time-complexity and I think that is too much ...

Best regards
DM

Posted: Thu Jul 31, 2003 11:21 am
by Maxim
There is a way to find LIS in O(n log n).
If you have found LIS for first i-1 elements, calculating LIS for i-th element should be done in O(log n). Think of such structure.

Posted: Thu Jul 31, 2003 2:52 pm
by Farid Ahmadov
I know O(n*log(n)) solution for this problem. But I also get TLE on Pascal.
Can you tell me why? What problems can there be?
I have tested it many times. My program works allright.

Posted: Thu Jul 31, 2003 3:20 pm
by Whinii F.
I didn't manage to solve this problem in the contest, but my teammate did. Try solving it with an O(2N) approach, by performing simple dynamic programming from alternating directions.

Posted: Thu Jul 31, 2003 3:33 pm
by Dominik Michniewski
Thanks Whinii .... I try to think about it ...

Best regards
DM

Posted: Sat Aug 02, 2003 9:48 am
by Andrey Mokhov
Hi, Board!

Whinii F. wrote:
Try solving it with an O(2N) approach, by performing simple dynamic programming from alternating directions.
I'm very suspicious about it. :wink:

It is well known that to find the length of LIS in a sequence you need O(nlog(n)) operations. But if you can find the length of the longest Wavio Sequence in O(n) than using this algorithm you will be able to find LIS as well in O(n). Assume you have a sequence a1..an and you want to find its LIS. Than you may find its maximum value M in O(n) and make another sequence b1..b(2n+1) in following manner - b1..bn = a1..an, b(n+1)=M+1, and b(n+2)..b(2n+1) = an..a1 (reversed!). Now find the length of the longest Wavio Sequence in O(n) (as you say you can!) and it will obviosly include LIS of a1..an. So we found length of LIS in O(n) :roll: :o :-?

May be I wrote it in bad way but I guess you will understand that this proves that the problem cannot be solved in O(n).

Am I wrong here?

Waitnig for your reply,
Best regards,
Andrey.

Posted: Sun Aug 03, 2003 12:17 pm
by Whinii F.
Andrey,

Umm yes I think you're totally right about it. Examining my teammate's source code I found out he actually used an O(n^2) algorithm..

I'm gonna think about it more. :wink:

Posted: Sun Aug 03, 2003 3:36 pm
by Observer
The O(n lg n) solution will do.

Hint: Think about Binary Search!! :P

Posted: Mon Aug 04, 2003 1:23 am
by Larry
how does a O(n^2) algorithm pass?

I used a balanced binary tree to do it in O( n log n ).. is there a easier way to do O( n log n ) for LIS?

Posted: Mon Aug 04, 2003 3:17 pm
by junjieliang
I solved this problem with an O(N^2) algo, but I believe that only happens in the worst case (or maybe not, if I did a better analysis of the complexity).

Another way would be to use the O(n log n) algo for LIS, which is just modifying a loop in the original algorithm to use binary search. Does anybody need the code? It can be obtained from the USACO training gateway, or I can post it here...

Posted: Mon Aug 04, 2003 3:37 pm
by Larry
junjieliang: pm it to me.. thanks! =)

(Or someone can just tell me what you binary search on?)

Posted: Mon Aug 04, 2003 4:11 pm
by Larry
I get TLE on a O(n^2) algo.. so.. hrmm..

Posted: Mon Aug 04, 2003 5:37 pm
by LittleJohn
Larry wrote:I get TLE on a O(n^2) algo.. so.. hrmm..
I guess junjieliang's complexity is O(n*m).
Although its worst case is O(n^2), but it seems not no bad.
However, Θ(n^2) will get TLE.

Posted: Mon Aug 04, 2003 8:31 pm
by Larry
Okay, with some thinking, I figured out the nlogn one, thanks!

Is there a Theta( n log n ) algorithm?