MEDMAXMATCH- EDITORIAL

PROBLEM LINK:

Contest
Practice

Setter: iceknight1093
Testers: gamegame
Editorialist: aryanag_adm

DIFFICULTY:

1647

PREREQUISITES:

Sorting

PROBLEM:

You are given two length N arrays A and B of positive integers, where N is odd. You need to pair up each element of A with an element of B such that the median of the sums of these pairs is maximised.

That is, if A_i is paired with B_{\sigma_i}, then we want to maximise median of the set C = \{A_i + B_{\sigma_i} | 1 \leq i \leq N\}.

Output the maximum possible median.

EXPLANATION:

Let M = \lceil \frac{N}{2} \rceil. The median is the M^{th} smallest element of C.

Therefore, the problem can be rephrased as maximising the M^{th} smallest element (which is also the M^{th} largest element). This implies that the smallest M-1 elements can be arbitrarily small, making them bigger does not help our objective.

Therefore, I claim the following:

  • Step 1: We first sort both A and B
  • Step 2: For the first M-1 elements of A, we can pair A_i with B_i. These elements can be very small, they won’t affect our result.
  • Step 3: For the final M elements, we pair A_M with B_N, A_{M+1} with B_{N-1}, A_{M+2} with B_{N-2}, \cdots, A_N with B_M.

I claim that this is the optimal construction, and the maximum possible median is the minimum sum from the pairs created in step 3.

Proof:
We see that in our construction, the median is the minimum sum from amongst the Step 3 pairs. This is because all of the Step 2 pairs have sum lesser than all of the Step 3 pairs, and there are exactly M-1 Step 2 pairs, implying that the M^{th} smallest sum is from the smallest pair in Step 3.

To see that this construction is optimal, note the following:

  • Since we want to maximise the M^{th} largest element, the largest M pairs should consist of only the largest M elements from A and the largest M elements from B.
  • Therefore, we can ignore the pairs formed in Step 2, and we only have to show that the pairs formed in Step 3 are optimal.
  • This is simple: if M=1 then this is the only possible construction. If M>1, just note that it is always optimal to pair A_M with B_N. After that, by induction. we see that our process in Step 3 is optimal.
  • To see that A_M with B_N is optimal, just note that if, instead, we pair some A_{M+i} with B_N and pair A_M with some B_{N-j}, we can get a solution at least as good by swapping A_{M+i} and A_M in their pairs.
  • This completes the proof.

Therefore, we can simply make the pairs as in Step 3, and then calculate their minimum.

TIME COMPLEXITY:

Time complexity is O(N \cdot {log}(N)).

SOLUTION:

Editorialist's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <sys/resource.h>
//#define int long long
#define double long double
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
#define mp(a, b) make_pair(a, b)
#define lz lazup(l, u, i);
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int a[n], b[n];
        for(int i = 0;i<n;i++) cin>>a[i];
        for(int i = 0;i<n;i++) cin>>b[i];
        sort(a, a+n);
        sort(b, b+n);
        int ans = 2e9;
        int k = n-1;
        for(int i = (n - ((n/2) + 1));i<n;i++){
                ans = min(ans, a[i] + b[k--]);
        }
        cout<<ans<<endl;
    }
}
3 Likes

AGGGGHHHHHHH I couldn’t prove this, and it costed me a rating drop :frowning:

2 Likes

To me the proof is still not clear as why we should join Am and Bn

1 Like

here
BINARY SEARCH ON ANSWER
& EASY TO PROVE

bro can you please elobrate you approach i can not figure it with how to do with bineary search on answer

hey can u explain the check function?

suppose we want to check for the x to be valid answer

A[]={a1,a2,a3,a4,a5}
B[]={b1,b2,b3,b4,b5}
both the array are sorted
final[] = {c1,c2,c3,c4,c5}

we know that we want to maximize the middle (c3)

we minimize c1 and c2 in order to maximize the c3
c1->(a1+b1)
c2->(a2+b2)

now array
A[]={a3,a4,a5}
B[]={b3,b4,b5}

we traverse one array
store the second array in the multiset

while traversing the array making sure that every Ci is atleast x.

example:

x=5
ai = 3
we require bi to be atleast 2
using multiset it will be sufficient to find and erase

The important observation for the proof to work is the following line towards the end of the editorial:

To see that A_M with B_N is optimal, just note that if, instead, we pair some A_{M+i} with B_N and pair A_M with some B_{N-j}, we can get a solution at least as good by swapping A_{M+i} and A_M in their pairs.

If you write out what happens when you swap, the result should become obvious pretty quickly.

Detailed explanation

Suppose A_M isn’t paired with B_N. It has to be paired with something, let that something be B_{N-j} (where j \geq 1, of course). Similarly, B_N must now be paired with some A_{M+i} where i \geq 1.

The first pair here has sum A_M + B_{N-j}, and the second has sum B_N + A_{M+i}.

As the editorial says, consider what happens when we swap A_M and A_{M+i} in their pairs. Now A_M is paired with B_N and A_{M+i} is paired with B_{N-j}. The sums are now A_M + B_N and A_{M+i} + B_{N-j}. Note that:

  • A_M + B_N \geq A_M + B_{N-j} (since B_N \geq B_{N-j})
  • A_{M+i} + B_{N-j} \geq A_M + B_{N-j} (since A_{M+i} \geq A_M)
  • A_{M+i} + B_N \geq A_M + B_{N-j}

So, A_M + B_{N-j} has the smallest sum among all 4 pairs we have. It’s obviously better to make pairs such that it is not one of them, since all we care about is maximizing the minimum sum. Thus, making this swap (and as a result pairing A_M with B_N) is optimal, and you can go on to do the same thing with the rest of the elements.

As an aside, the argument used in this proof is a rather common way to prove the optimality of some ordering of elements. It’s called an exchange argument, you can see more use cases in this Codeforces blog.

Thanks it was awesome:). Exchange argument is really cool way that can be used to proof so many greedy problems
Thanks again