SUBMEDIA - Editorial


Contest - Division 3
Contest - Division 2
Contest - Division 1

Setter: Jatin Khandual
Tester: Anshu Garg, Nishant Shah






Given an array A of size N. Determine a subsequence of A of length K, with the largest possible median.


Observation: A subsequence of A of length K with median X exists if and only if there are at least \lfloor\frac K 2\rfloor elements in A greater than X (and \lfloor \frac{K-1}{2}\rfloor elements lesser than X.)
(Proof left to the reader as an exercise!)

Therefore, the largest possible median attainable will be the (\lfloor\frac K 2\rfloor-1)^{th} largest element of A. It can be trivially shown that, one subsequence with this median, would be the set of the K greatest elements of A.

How do I find the $K$ greatest elements of $A$ while maintaining the relative order of the elements?

Create an array of pairs whose elements are \{A_i, i\}, for all valid i.

Sort the array in ascending order, by the first term. Create a new array with the last K elements of the sorted array. Then, sort this new array by the second term (the indices of the elements) to restore the relative order of the elements.


Since we sort the array twice (once to find the K greatest elements, once to restore the relative order of the selected elements), the total time complexity is:

O(2*N\log N) \approx O(N\log N)


Editorialist’s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

MY Approach
First, find out the n-k minimum elements from the array and remove them then find the median of the remaining elements which would be our maximum median.

int n, k;
    cin >> n >> k;
    vector<int> org(n);
    vector<pair<int, int>> dup(n);
    // duplicate array for storing the numbers with their indexes
    for (int i = 0; i < n; i++)
        cin >> org[i];
        dup[i].first = org[i];
        dup[i].second = i;
    // sorting the duplicate array
    sort(dup.begin(), dup.end());
    // finding the first n-k elements of the duplicate array in the original array and making them as -1,as they do not contribute to our required sequence
    for (int i = 0; i < (n - k); i++)
        org[dup[i].second] = -1;
    // printing the middle element in the duplicate vector,excluding the n-k elements
    cout << dup[(n - k) + k / 2].first << endl;
    // printing the elements of the orginal array whose value is not set -1
    for (int i = 0; i < n; i++)
        if (org[i] != -1)
            cout << org[i] << " ";
    cout << endl;

Is this approach correct, it is similar to your approach but somehow i am getting wrong answer,
when submitted, will you please say why i am getting wrong answer. Is my approach wrong.

a subsequence of {4,5,6,7,8} of length 3 with median 4 exists if and only if there are at least [3/2] elements in {4,5,6,7,8} greater than X-------> the condition holds but there is no such subsequence.
I guess the write statement should be "A subsequence of A of length K with median X exists if and only if there are at least [K/2] elements in A greater than X and atleast [K/2] elements lesser than X.

1 Like

Right, thanks for pointing this out!