Chef and the Cards
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
There are N cards placed in a row, where every card has two numbers written on it, one on the top and
one on the bottom. The numbers are between 1 and N (both inclusive). Every number is written on the top of exactly one card, and on the bottom of exactly one card as well.
Chef wants to rearrange the cards, such that the length of the longest common contiguous subsequence between the sequence formed by number written on top of the cards, and that formed by those written on the bottom is maximum. He can't modify the numbers written on any card and can't flip the cards, that is, for any card the number written on top remains at the top and the number written on bottom stays at the bottom. Find out the maximum possible length of the common contiguous subsequence.
The first line of input contains an integer T denoting the number of test cases.
- The first line of each test
case contains an integer N.
- The next line contains N space separated integers A1, A2, ... , AN, where Ai(1 ≤ i ≤ N) is the number written on the top of the i-th card.
- The next line contains N space separated integers B1, B2, ... , BN, where Bi(1 ≤ i ≤ N) is the number written at the bottom of the i-th card.
For each test case, output a single line containing the integer L: the maximum length of the longest common contiguous subsequence.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 2000
- 1 ≤ Ai, Bi ≤ N
- All the elements in both arrays A and B are distinct.
Input: 2 3 1 3 2 2 1 3 8 3 8 4 2 6 1 5 7 5 2 4 3 8 7 6 1 Output: 2 4
First Example :
One of the possible card arrangements is:
1 2 3
2 3 1
Length of the longest common contiguous subsequence between [1, 2, 3] and [2, 3, 1] is 2, [2, 3]. And that's the maximum possible, so answer is 2.
One of the possible card arrangements is :
7 3 2 8 6 5 4 1
1 5 3 2 8 6 4 7
The longest common contiguous subsequence has length 4 [3, 2, 8, 6] here. There is no way to arrange these cards such that it's more than 4.
Let L be the answer. Let Ci be the value written on the top of the card at ith position and Di be the value written on the bottom of the card at ith position after rearranging. Then, there should be a pair (x, y) (1 ≤ x,y ≤ N-L+1) such that the condition Cx+j = Dy+j is satisfied for all j, where 0 ≤ j < L.
|Tags||cook61, dynamic-programming, graphs, greedy, medium-hard, rustinpiece|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.