## 10534 - Wavio Sequence

Moderator: Board moderators

titid_gede
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?

Dominik Michniewski
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) time-complexity 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)

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:
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.

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
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.
_____________
NO sigNature

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
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.
JongMan @ Yonsei

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Thanks Whinii .... I try to think about it ...

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)

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
Hi, Board!

Whinii F. wrote:
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?

Best regards,
Andrey.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
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.
JongMan @ Yonsei

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
The O(n lg n) solution will do.

7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
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...

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
junjieliang: pm it to me.. thanks! =)

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I get TLE on a O(n^2) algo.. so.. hrmm..

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Okay, with some thinking, I figured out the nlogn one, thanks!

Is there a Theta( n log n ) algorithm?