SPOJ.com - Problem BRIDGE

BRIDGE - Building Bridges

#tree #binary-search

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 i^th end point on one side can only end on the i^th 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 <= 10³). The second line contains x-coordinates of end points identified on the first side and similarly 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 -10³ to 10³.

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

Explanation

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

Submit solution!

hide comments

< Previous 1 2 3 4 5 Next >

	sanki_hu: 2017-05-05 12:43:30 @Shubham Garg Thanks bro ,really very nice test cases
	vengatesh15: 2017-03-24 05:52:29 easy one with sorting and dp
	kishanvadaliya: 2016-06-24 17:03:17 what should be answer for this? 3 0 1 1 1 1 1
	topke: 2016-06-04 10:45:41 @Rohit Agarwal There is solution using BIT and using SegmentTrees.
	karthik1997: 2016-06-03 09:19:55 Sorting and LIS(Longest increasing subsequence ) paves the way .. Just see the testcases and you will get the idea immediately ... And while finding LIS ,, for equal two points on second bridge , consider the first bridge coordinates too :p (I dont tell beyond this :p ) ,, and Expected complexity is O(n^2)..... Good Luck :D
	Rohit Agarwal: 2016-06-01 12:45:31 Solved this problem with LIS but however the tag is binary search for this problem. In the beginning, I was trying to solve it with Binary Indexed tree but had some tc where it was printing wrong answers. Did anyone solved it using BS or BIT? Can someone please explain how to do it by that? Thanks
	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

Submit solution!

Added by:	Troika::Bytes
Date:	2010-02-18
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	ADA95 DOC ASM32 ASM64 BASH BF C CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCALA SCM guile SCM qobi ST TCL TEXT WHITESPACE