Maximum Median Matching Codechef Solution CoderCEO

Maximum Median Matching Codechef Solution | MEDMAXMATCH | (100/100) FULL | Codechef July Lunchtime | AC Code

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

The $i$ -th boy has a happiness value of $A_{i}$ and the $i$ -th girl has a happiness value of $B_{i}$ . A pair consisting of the $i$ -th boy and the $j$ -th girl has a happiness value of $A_{i} + B_{j}$ .

Let the happiness values of the $N$ pairs be $C_{1}, C_{2}, \dots, C_{N}$ . 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 $C$ , 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]$ is $1$ , the median of $[1, 5, 2]$ is $2$ , and the median of $[30, 5, 5, 56, 3]$ is $5$ .

Input Format

The first line of input will contain a single integer $T$ , 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 $N$ .
The second line of each test case contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ — the happiness values of the boys.
The third line of each test case contains $N$ space-separated integers $B_{1}, B_{2}, \dots, B_{N}$ — the happiness values of the girls.

Output Format

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

Constraints

$1 \leq T \leq 3 \cdot 10^{4}$
$1 \leq N < 3 \cdot 10^{5}$
$N$ is odd
$1 \leq A_{i}, B_{i} \leq 10^{9}$ for each valid $i$
The sum of $N$ across all test cases won’t exceed $3 \cdot 10^{5}$ .

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

Test case $1$

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 = 35$ , and it is also the median.

Test case $2$

Pair $A_{1}$ with $B_{3}$ , $A_{2}$ with $B_{2}$ , and $A_{3}$ with $B_{3}$ . The happiness values are then $[1 + 7, 2 + 6, 2 + 6] = [8, 8, 8]$ , with a median of $8$ . It can be shown that this is the maximum possible median.

Test case $3$

One way of achieving a median of $50$ is as follows:

Pair $A_{1}$ with $B_{3}$ , for a happiness of $10 + 62 = 72$
Pair $A_{2}$ with $B_{4}$ , for a happiness of $4 + 6 = 10$
Pair $A_{3}$ with $B_{5}$ , for a happiness of $93 + 26 = 119$
Pair $A_{4}$ with $B_{1}$ , for a happiness of $5 + 4 = 9$
Pair $A_{5}$ with $B_{2}$ , for a happiness of $16 + 34 = 50$

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

				
					void solve()
{
    ll oo = 1, n;
    if (oo != 1)
    {
        ll ji = -1;
    }
    else
    {
        cin >> n;
    }

    vector<ll> y(n);
    vector<ll> x(n);

    for (ll i = 0; i < n; i++)
        cin >> x[i];
    sort(x.begin(), x.end());
    for (ll i = 0; i < n; i++)
        cin >> y[i];

    sort(y.begin(), y.end());

    vector<ll> we;

    for (ll i = n / 2; i < n; i++)
        we.push_back(y[i]);
    b = we;
    we.clear();
    for (ll i = n / 2; i < n; i++)
        we.push_back(x[i]);
    a = we;

    n = a.size();
    vector<ll> cty;
    for (ll i = 0; i < n; i++)
    {
        cty.push_back(x[i] + y[n - 1 - i]);
    }
    sort(cty.begin(), cty.end());
    cout << cty[0] << endl;
}

Maximum Median Matching Codechef Solution

Published by Govind Deshmukh on July 17, 2022July 17, 2022