[Solution] Maximum Median Matching solution codechef

Maximum Median Matching solution codechef – 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.

[Solution] Maximum Median Matching solution codechef

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 [1][1] 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.

[Solution] Maximum Median Matching solution codechef

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

Constraints

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

Subtasks

• 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.

[Solution] Maximum Median Matching solution codechef

 

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

[Solution] Maximum Median Matching solution codechef Explanation

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 B3B3, A2A2 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.

For Solution

“Click Here“