LCS3 - Long Common Subsequence
Given a main sequence of N (1 <= N <= 1000000) numbers range from 0 to 10000 and several other sequence of M (0 <= M <= 5) numbers, you have to compute the Longest Common Subsequence of this sequence with the main sequence.
Input
First line of the input will be N the number of elements of the main sequence. After that line there will be N numbers in one or more lines. Each of this number will be between 0 to 10000 (inclusive). Then there will be Q (1 <= Q <= 5000) the number of query. Then following Q lines will be queries. In each query, start with a number M (0 <= M <= 5), followed by M numbers also between 0 to 10000 (inclusive).
Output
For each query first print the number of elements in the longest common subsequence of the main and query sequences. Then print the subsequence. If there is more then one then print the lexicographically smallest.
Example
Input: 10 5 1 4 3 2 6 5 5 0 7 5 1 5 1 10 4 5 0 4 7 5 4 1 2 3 5 5 2 6 5 0 7 Output: 1 5 0 3 5 0 7 3 1 2 5 5 2 6 5 0 7Huge Test Case (almost 5MB)
Added by: | Muhammad Ridowan |
Date: | 2011-07-02 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Own. Thanks msh_shiplu and zobayer for alternate |