Select the subset

3.7

7 votes
Merge Sort, Sorting, Algorithms, C++
Problem

You are given an array A and B of size N.

You must select a subset of indices from 1 to N such that for any pair of indices (x,y), xy in the subset one of the following conditions holds true:

  • A[x]<A[y] and B[x]<B[y]
  • A[x]>A[y] and B[x]>B[y]
  • A[x]=A[y] and B[x]B[y]

Your task is to determine the largest possible size of a subset that satisfies the provided conditions.

Note: Assume 1 based indexing.

Input format

  • The first line contains an integer T that denotes the number of test cases.
  • For each test case:
    • The first line contains an integer N.
    • The second line contains N space-separated integers that denotes the array A.
    • The third line contains N space-separated integers that denotes the array B.

Output format

For each test case, print the largest possible size of a subset that satisfies the provided conditions in a new line.

Constraints

1T102N1051A[i],B[i]109

Sample Input
1
5
10 21 5 1 3
3 1 4 23 56
Sample Output
2
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  • Choose index 4,5 in the subset.
    • (4,5) satisfies A[x]<A[y] and B[x]<B[y]
    • (5,4) satisfies A[x]>A[y] and B[x]>B[y].
  • Thus, largest possible size of a subset which satisfies the above conditions is 2.
Editor Image

?