BRIDGE - Building Bridges


The tribe soon discovers that just communication is not enough and wants to meet each other to form a joint force against the terminator. But there is a deep canyon that needs to crossed. Points have been identified on both sides on which bridge ends can be made. But before the construction could be started, a witch Chudael predicted that a bridge can only be built between corresponding end points, i.e. a bridge starting from the ith end point on one side can only end on the ith end point on the other side, where the position of end points is seen in the order in which the points were identified. If not, it would lead to the end of the tribe. The tribe just wants to make as many non-cutting bridges as possible, with the constraint in mind. Bridges "cut" if and only if they have exactly one common point that is not an end point.

Input

The first line of the input contains test cases t (1<=t<=50). It is followed by 3*t lines, 3 for each test case. The first line of input for each test case contains the number of end points identified on each side, n (1<=n<=103). The second line contains x-coordinates of end points identified on the first side and similiarly the third line contains the x-coordinates of corresponding end points identified on the other side. The end points are inputted in the order in which they were identified. The x-coordinates can range between -103 to 103.

Output

You are required to output a single line for each test case. The line contains a single integer – the maximum number of bridges possible with the constraints explained above.

Example

Input:
3

4

2 5 8 10

6 4 1 2

3

5 3 10

6 4 1

6

1 2 3 4 5 6

3 4 5 6 1 2

Output:

2

2

4

 

Expalanation: For the first test case, two non-overlapping bridges can be formed between the 3rd and 4th end points on each side.


hide comments
Akshay Damle: 2016-04-21 20:09:17

The knapsack-type DP solution I thought of initially gave TLE :( n^2 LIS solution passed though

try2catch: 2016-03-22 07:09:04

I'm getting WA why?
passing all test cases though :(

Mateusz Lamecki: 2016-01-14 14:23:04

@Shashank Tiwari: your post is very helpful, but actually answer of @Shubham Garg's test case is correct.

Shashank Tiwari: 2015-12-13 11:32:58

Let me explain the problem more clearly ....

We have some equal number of points on two sides of a deep canyon . Now we need to form a bridges as many as possible to cross the canyon. A bridge is formed by connecting any 2 points each on different side of canyon. But , No two bridges can cut each other. Things are little more weird . We have been given x-coordinates of those points. If X1, X2, X3 ,...,Xn be those coordinates , then Point1 is on X1, ; point 2 is on X2 ; .... and so on. Also ,

1) It is not necessary that Point 1 will have least X coordinate or to be more formal , it is not necessary that
Point i will have lesser X coordinate than Point (i+1).
2) Two points can have same X coordinates. (Ya , I know this is weird but then that's how the question is ...)
3) Two bridges that meet on other side of river at same x-coordinate are acceptable i.e. They should not be considered intersecting.

The question is how many maximum bridges can we construct satisfying above conditions.

Lets take an example . Let the coordinate list be as mentioned below.

12 5 8 1
6 4 1 2

This means Point 1 has x coordinate 12 and 6 on respective side of canyon.
This means Point 2 has x coordinate 5 and 4 on respective side of canyon.
This means Point 3 has x coordinate 8 and 1 on respective side of canyon.
This means Point 4 has coordinate 1 and 2 on respective side of canyon.

Note that on either side of Canyon the order in which points occur are :

4 2 3 1
3 4 2 1

It is not necessary that Point 1 will occur at first , then Point 2 and so on ... I hope you get it.

Lets take another example . Thanks to @e_coder for this.

1 2 2
1 1 1

Here we see on lower side of canyon , Points 1, 2,3 have same x - coordinate =1 and on upper side x- coordinate of Point 2 , 3 is same i.e. =2 . We can draw at max 3 non intersecting bridges.

Note that @Shubham Garg test case answer is wrong . I post the same test case with right answer.
2
3
0 1 1
1 2 -1
3
0 1 1
1 3 2


3
3

Hope this helps.

Last edit: 2015-12-13 11:35:01
e_coder: 2015-06-23 13:37:41

try this one:
3
1 2 2
1 1 1
ans: 3

Sudarshan K: 2015-05-31 14:03:06

No need to bang your head - O(n^2) passes :)

Madhav: 2015-04-19 12:53:32

Thankyou Shubham and Aparajita for the test cases!!

anando_du: 2015-03-04 19:11:55

same as BRDGHRD :v :v submitted same code . got AC . ^_^

aparajita choudhary: 2015-02-01 14:03:29

Test case for those who are getting WA-
1
4
0 2 1 1
1 4 4 3
Output-4

Last edit: 2015-02-01 14:07:35
Kishlay Raj: 2014-12-30 04:12:39

thanks @shubham garg , really nice test case


Added by:Troika::Bytes
Date:2010-02-18
Time limit:0.193s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASMGCC AWK clang_c clang_cpp C++14 CLOJ COB dmd clang_d elixir F# fantom GO GROOVY nim NODEJS clang_objc objc PERL 6 pico PYPY PYTH 3.4 PYTH 3.2.3 n rust SCM chicken SED VB.net