ZIGZAG2 - Zig when you zag
We say that a sequence of numbers x(1), x(2) ... x(k) is zigzag if no three of its consecutive elements create a non-increasing or non-decreasing sequence. More precisely, for all i=1, 2 ... k-2 either x(i+1) < x(i), x(i+2) or x(i+1) > x(i), x(i+2).
You are given two sequences of numbers a(1), a(2) ... a(n) and b(1), b(2) ... b(m). The problem is to compute the length of their longest common zigzag subsequence. In other words, you're going to delete elements from the two sequences so that they are equal, and so that they're a zigzag sequence. If the minimum number of elements required to do this is k then your answer is m+n-2k.
Input
There is a single integer t (t ≤ 100) on the first line of input. Then t test cases follow. Each of them consists of two lines. The first line contains the length of the first sequence n (1 ≤ n ≤ 2000) and n integers a(1), a(2) ... a(n). The second line contains the length of the second sequence m (1 ≤ m ≤ 2000) and m integers b(1), b(2) ... b(m). All a(i) and b(i) are from [-109, 109]. (REPEAT: the first number on the line is not part of the sequence, it's the length of the sequence.)
Output
For each test case output one line containing the length of the longest common zigzag subsequence of a and b.
Example
Input: 2 5 1 2 5 4 3 5 4 1 2 5 3 3 1 2 1 2 1 1 Output: 3 2
hide comments
miamimagna:
2024-11-03 19:48:42
am I the only one who can't decipher this question
|
|
amangoyal097:
2020-07-14 21:40:42
Try using two states of dp and the special cases:
|
|
gauravsingh_:
2019-09-14 11:29:15
some important test cases:-
|
|
gauravsingh_:
2019-09-09 18:30:45
what's wrong in following approach?
|
|
Sushovan Sen:
2016-10-25 10:46:14
What is expected output for case:
|
Added by: | gawry |
Date: | 2013-05-10 |
Time limit: | 1s-4s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |