Xenny and Matching Pairs

4

1 votes
Dynamic Programming
Problem

Xenny is studying hard for exam and he came across a the trivial question "Match the pairs". The question is given two columns of numbers, he has to match the numbers and draw lines connecting them. Xenny was very happy to see such a simple question, but then he saw the condition. The condition was while matching the pairs, lines connecting each pair should not cross each other. Xenny went to teacher with this problem; but instead of solving, teacher made the problem little easier. Teacher fixed the first column as numbers from 1 to n. Now Xenny needs to match those numbers to numbers in second column satisfying the condition.

Now Xenny is in big trouble. He wants to maximize the no. of pairs he can match and he now want your help.

Input: The First line will have an integer t denoting number of test-cases. The format for each test-case is as follows: The First line will have an integer n denoting no. of integers in each column. Next n lines will have an integer each denoting the integers in second column from top to bottom. (As said earlier, first column will have integers 1 to n, from top to bottom). (Each integer will surely have a matching pair in other column.)

Output:

For each case, print the maximum number of pairs of integers you can match, on new line.

Constraints:

SMALL:

0 < t <= 200

0 < n <= 100 i.e. 10^2

MEDIUM:

0 < t <= 50

0 < n <= 1000 i.e. 10^3

LARGE:

0 < t <= 15

0 < n <= 100000 i.e. 10^5

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

There are 2 test-cases. In first case, There are 2 numbers in second column and their order is 2 -- 1. And as we know, first column is 1 -- 2. First Second 1 2 2 1

Now if we match pair of 1, then we cant match pair of 2s because then line 2-2 will cross 1-1. Similarly, if we match 2-2 first, then we can't match 1-1. So maximum pairs those can be matched are 1.

In second case, There are 2 numbers in second column and their order is 1 -- 2. And as we know, first column is 1 -- 2. First Second 1 1 2 2

Now if we match pair of 1, then we can match pair of 2 as well because then line 2-2 will not cross 1-1. So maximum pairs those can be matched are 2.

Editor Image

?