adplus-dvertising

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

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

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

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

Explanation

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

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

Related Posts

2 thoughts on “Maximum Median Matching CodeChef Solution

Leave a Reply

Your email address will not be published.