Evang's blog

SPOJ ZIGZAG2 help
By Evang, history, 3 years ago, In English

Hello

For the past few days, I've been trying to solve this problem, but I still cannot come up with a solution that I can prove.

My only current candidate answer is that the longest common zigzag sequence is always in the longest common subsequence, but because there can be multiple longest common subsequences, I don't know which one to choose. Also, I don't even know if the longest common zigzag sequence is part of the longest common subsequence.

Can anyone help me with this problem? I cannot find any good explanations online.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

Hi Evang

I know this is a very old question, but the answer might help others, as I couldn't find any other post or tutorial about this when I googled it.

I solved the problem in a way that is not the most efficient, but it worked. It's O(N*M*log^2(N))

I used a Fenwick Tree 2D for maximum values. For each pair of equal numbers, I check with the FT the maximum length of a subsequence ending at that index, using maximum that value. In fact, I used 2 trees, one stores the values with greater value, and the other with smaller values (for the zig zag).

I leave my solution here.

Anyway, if someone can help us with a better solution, that would be great.

→ Reply