10534  Wavio Sequence
Moderator: Board moderators

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
10534  Wavio Sequence
how to solve this probleM without getting TLE? is there algo which run linear time?
Kalo mau kaya, buat apa sekolah?

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
This question is intresting to me too ...
This problem looks like LIS, but this has O(N^2) timecomplexity and I think that is too much ...
Best regards
DM
This problem looks like LIS, but this has O(N^2) timecomplexity and I think that is too much ...
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Experienced poster
 Posts: 131
 Joined: Thu Apr 17, 2003 8:39 am
 Location: Baku, Azerbaijan

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
Hi, Board!
Whinii F. wrote:
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. wrote:
I'm very suspicious about it.Try solving it with an O(2N) approach, by performing simple dynamic programming from alternating directions.
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.
The O(n lg n) solution will do.
Hint: Think about Binary Search!!
Hint: Think about Binary Search!!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
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...
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...

 Learning poster
 Posts: 83
 Joined: Wed Feb 27, 2002 2:00 am
 Location: Taiwan