10534 - Wavio Sequence

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

10534 - Wavio Sequence

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?
Kalo mau kaya, buat apa sekolah?

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

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

User avatar
Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

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

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.
_____________
NO sigNature

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

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.
JongMan @ Yonsei

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

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

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

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

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

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. :wink:
JongMan @ Yonsei

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

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

The O(n lg n) solution will do.

Hint: Think about Binary Search!! :P
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:

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

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

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

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

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

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

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?

Post Reply

Return to “Volume 105 (10500-10599)”