PROBLEM LINK:
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;
}
}
