10534 - Wavio Sequence

titid_gede · Post by **titid_gede** » Thu Jul 31, 2003 7:26 am

how to solve this probleM without getting TLE? is there algo which run linear time?

Dominik Michniewski · Post by **Dominik Michniewski** » Thu Jul 31, 2003 8:18 am

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

Maxim · Post by **Maxim** » Thu Jul 31, 2003 11:21 am

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.

Farid Ahmadov · Post by **Farid Ahmadov** » Thu Jul 31, 2003 2:52 pm

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.

Whinii F. · Post by **Whinii F.** » Thu Jul 31, 2003 3:20 pm

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.

Dominik Michniewski · Post by **Dominik Michniewski** » Thu Jul 31, 2003 3:33 pm

Thanks Whinii .... I try to think about it ...

Best regards
DM

Andrey Mokhov · Post by **Andrey Mokhov** » Sat Aug 02, 2003 9:48 am

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.

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)

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.

Whinii F. · Post by **Whinii F.** » Sun Aug 03, 2003 12:17 pm

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.

Observer · Post by **Observer** » Sun Aug 03, 2003 3:36 pm

The O(n lg n) solution will do.

Hint: Think about Binary Search!!

Larry · Post by **Larry** » Mon Aug 04, 2003 1:23 am

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?

junjieliang · Post by **junjieliang** » Mon Aug 04, 2003 3:17 pm

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

Larry · Post by **Larry** » Mon Aug 04, 2003 3:37 pm

junjieliang: pm it to me.. thanks! =)

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

Larry · Post by **Larry** » Mon Aug 04, 2003 4:11 pm

I get TLE on a O(n^2) algo.. so.. hrmm..

LittleJohn · Post by **LittleJohn** » Mon Aug 04, 2003 5:37 pm

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.

Larry · Post by **Larry** » Mon Aug 04, 2003 8:31 pm

Okay, with some thinking, I figured out the nlogn one, thanks!

Is there a Theta( n log n ) algorithm?