# Maximum Median Matching CodeChef Solution

### We Are Discuss About CODECHEF SOLUTION

Maximum Median Matching CodeChef Solution

## Maximum Median Matching CodeChef Solution

NN boys and NN girls attend a dance class, where NN is odd. For today’s practice session, they need to form NN boy-girl pairs.

The ii-th boy has a happiness value of AiAi and the ii-th girl has a happiness value of BiBi. A pair consisting of the ii-th boy and the jj-th girl has a happiness value of Ai+BjAi+Bj.

Let the happiness values of the NN pairs be C1,C2,,CNC1,C2,…,CN. The dance instructor would like it if many of the pairs have a high happiness value, and passes the task to you — find the maximum possible value of the median of CC, if the boy-girl pairs are chosen optimally.

Note: The median of a odd-sized list of integers is the middle number when they are sorted. For example, the median of  is 11, the median of [1,5,2][1,5,2] is 22, and the median of [30,5,5,56,3][30,5,5,56,3] is 55.

### Input Format

• The first line of input will contain a single integer TT, denoting the number of test cases.
• Each test case consists of three lines of input.
• The first line of each test case contains a single integer NN.
• The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN — the happiness values of the boys.
• The third line of each test case contains NN space-separated integers B1,B2,,BNB1,B2,…,BN — the happiness values of the girls.

### Output Format

For each test case, output on a new line the maximum possible median happiness of the NN pairs.

## Maximum Median Matching CodeChef Solution

### Constraints

• 1T31041≤T≤3⋅104
• 1N<31051≤N<3⋅105
• NN is odd
• 1Ai,Bi1091≤Ai,Bi≤109 for each valid ii
• The sum of NN across all test cases won’t exceed 31053⋅105.

• Subtask 1 (10 points):
• The sum of NN across all test cases won’t exceed 1010.
• Subtask 2 (30 points):
• The sum of NN across all test cases won’t exceed 40004000.
• Subtask 3 (60 points):
• No further constraints.

### Sample Input 1

3
1
10
25
3
1 6 6
2 2 7
5
10 4 93 5 16
4 34 62 6 26


### Sample Output 1

35
8
50


## Maximum Median Matching CodeChef Solution

Test case 11: There is only one boy and one girl, so they must be paired with each other. The happiness value of the pair is 10+25=3510+25=35, and it is also the median.

Test case 22: Pair A1A1 with B3B3A2A2 with B2B2, and A3A3 with B3B3. The happiness values are then [1+7,2+6,2+6]=[8,8,8][1+7,2+6,2+6]=[8,8,8], with a median of 88. It can be shown that this is the maximum possible median.

Test case 33: One way of achieving a median of 5050 is as follows:

• Pair A1A1 with B3B3, for a happiness of 10+62=7210+62=72
• Pair A2A2 with B4B4, for a happiness of 4+6=104+6=10
• Pair A3A3 with B5B5, for a happiness of 93+26=11993+26=119
• Pair A4A4 with B1B1, for a happiness of 5+4=95+4=9
• Pair A5A5 with B2B2, for a happiness of 16+34=5016+34=50

The happiness values are [72,10,119,9,50][72,10,119,9,50], with a median of 5050. It can be shown that no other pairing obtains a strictly larger median.

## SOLUTION

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here ScishowEngineer   Then Follow US HERE and Join Telegram.

If You Want To Learn Something New Then Visit Our Official Channel YOUTUBE

## 2 thoughts on “Maximum Median Matching CodeChef Solution”

1. Best view i have ever seen !

2. Best view i have ever seen !