Friday, September 4, 2009

ZigZag - 2003 TCCC Semifinals 3 - TopCoder

Dynamic Programming - Longest Increasing Subsequence( LIS )

It's something like LIS. You have to manipulate the original algorithm to obtain the answer.
I used a two dimensional array ZIGZAG[60][2] such that ZIGZAG[i][0] is the length of the longest ZigZag sequence ending at sequence[i] and ZIGZAG[i][1] is the sign of the last difference ending at sequence[i].
Suppose we have a sequence like this:
1, 8, 7, 6, 9, 10
ZIGZAG[1][0] = 1,          ZIGZAG[1][1] = 0
ZIGZAG[2][0] = 2,         ZIGZAG[2][1] = +1
ZIGZAG[3][0] = 3,         ZIGZAG[3][1] = -1
ZIGZAG[4][0] = 3,         ZIGZAG[4][1] = -1
ZIGZAG[5][0] = 4,         ZIGZAG[5][1] = +1
ZIGZAG[6][0] = 4,         ZIGZAG[6][1] = +1

I implemented the solution in O( n^2 ), since I have to check n items and for each item I will check n items to choose the appropriate subsequence.

No comments:

Post a Comment

USACO - Prime Palindromes

I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...