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

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

The -th boy has a happiness value of and the -th girl has a happiness value of . A pair consisting of the -th boy and the -th girl has a happiness value of .

Let the happiness values of the pairs be . 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 , 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 , the median of is , and the median of is .

Input Format

  • The first line of input will contain a single integer , 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 .
  • The second line of each test case contains space-separated integers — the happiness values of the boys.
  • The third line of each test case contains space-separated integers — the happiness values of the girls.

Output Format

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

Constraints

  • is odd
  • for each valid
  • The sum of across all test cases won’t exceed .

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

There is only one boy and one girl, so they must be paired with each other. The happiness value of the pair is , and it is also the median.

Test case

Pair with , with , and with . The happiness values are then , with a median of . It can be shown that this is the maximum possible median.

Test case

One way of achieving a median of is as follows:

  • Pair with , for a happiness of
  • Pair with , for a happiness of
  • Pair with , for a happiness of
  • Pair with , for a happiness of
  • Pair with , for a happiness of

The happiness values are , with a median of . 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;
}
				
			

0 Comments

Leave a Reply

Avatar placeholder

Your email address will not be published.