An interesting subsequence

Problem code: C5

All submissions for this problem are available.

For two given sequences of integers, find the longest possible integer sequence which is a subsequence of both these sequences, and whose elements are integers in a (strictly) increasing order.

Input

The first number is n (1 ≤ n ≤ 5000), the length of the first sequence.

The next n integers are elements of the first sequence.

The next is m (1 ≤ m ≤ 5000), the length of the second sequence.

The next m integers are elements of the second sequence.

Output

One number k, the length of the longest possible common subsequence that is increasing, followed by exactly k space-separated integers containing any exemplary sequence of this length.

Example

For the input:

5
2 3 1 4 0
6
10 3 4 1 0 0

the unique correct answer is:

2
3 4
Date: 2009-04-20
Time limit: 3s
Source limit: 50000
Languages: C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp HASK CAML CLPS PRLG WSPC BF ICK TEXT


Comments

totobogy @ 3 May 2009 02:58 AM

How is '3 4' a 'subsequence' of the first sequence? So the 'subsequence' doesn't have to be continous?

devanshu17 @ 4 May 2009 02:54 AM

The valid(in increasing order) subsequences for the first sample input as per the above written example are and
whereas for the second sequence the valid subsequences are and . So, how is a common subsequence for the two sequences given as input?
In the first sample input, 1 lies between 3 and 4, thus cannot be considred as its subsequence.

Kindly explain.

devanshu17 @ 4 May 2009 02:58 AM

The valid(in increasing order) subsequences for the first sample input as per the above written example are 2,3 and 1,4 whereas for the second sequence the valid subsequences are 3,4 and 1,0. So, how 3,4 is a common subsequence for the two sequences given as input? In the first sample input, 1 lies between 3 and 4, thus cannot be considred as its subsequence. Kindly explain.

chiku @ 6 May 2009 02:23 AM

Hi All,
I have got the solution for this problem. Its giving correct output for the sample input and any other inputs that i can think of. But i really am not able to comprehend why its giving wrong answer for codechef test cases... :( :(
somebody please help me

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions