PROBLEM LINK:
Author: Jeevan Jyot Singh
Tester: Aryan Choudhary
DIFFICULTY:
SIMPLE
PREREQUISITES:
Sorting, Observation
PROBLEM:
JJ loves playing with medians. He has an array A of length N (N is odd). He wants to partition the array A into two non-empty subsets P and Q such that the value of |median(P) - median(Q)| is as small as possible. (Note that each A_i must belong to either subset P or subset Q).
Help him find this minimum value of |median(P) - median(Q)|.
As a reminder, the median of a subset X of size N is the element which occupies the \lfloor\frac{N+1}{2}\rfloor^{th} position after we sort the elements in non-decreasing order. For example, median([3, 1, 4]) = 3, median([3, 1, 4, 2]) = 2. (Here \lfloor x \rfloor denotes the largest integer which does not exceed x).
QUICK EXPLANATION:
The answer is just the difference A_{\frac{N+1}{2}} - A_{\frac{N-1}{2}} after sorting the array.
EXPLANATION:
Let us sort the initial array, since that does not affect the answer. This is because, once we choose the subsequence, the median is considered after sorting those subsequences independently. This is as good as sorting the initial array, and choosing 2 disjoint subsequences from this array.
Let us assume that we divide the array into disjoint spanning subsets P, Q. Let’s call all the indices \le \frac{N-1}{2} the left half of the array and all the indices \gt \frac{N-1}{2} the right half of the array
Claim: One of the medians will be in the left half, the other one will be in the right half.
Proof (by contradiction): Let us assume that the medians of the sets P and Q correspond to A_x and A_y where x and y are both \le \frac{N-1}{2} (WLOG, other case is symmetric). Let’s say that the size of set P is K, ie, |P| = K, and thus |Q| = N - K.
Again, WLOG, let K be odd, since one of the sets has to be odd sized.
Then this set has \frac{K-1}{2} elements > A_x. Other set has \frac{N-K}{2} elements > A_y.
Therefore we can take atmost \frac{K - 1}{2} + \frac{N - K}{2} = \frac{N-1}{2} elements from the right half. But we have \frac{N-1}{2} + 1 elements in the right half which we need to take. This is a contradiction.
So now that we have established that the medians A_x and A_y are such that x \le \frac{N-1}{2}, and y > \frac{N-1}{2}, it follows that x = \frac{N-1}{2} and y = \frac{N-1}{2} + 1 is the best case.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n; cin >> n;
vector<int> a(n);
for(int &x: a)
cin >> x;
sort(a.begin(), a.end());
cout << a[n/2] - a[n/2 - 1] << "\n";
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T;
while(T--)
{
solve();
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, i;
cin >> n;
vector<int> a(n);
for (i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
cout << a[n / 2] - a[n / 2 - 1] << "\n";
}
return 0;
}