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) time-complexity and I think that is too much ...
Best regards
DM
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)
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