SUBMEDIA - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Setter: Jatin Khandual
Tester: Anshu Garg, Nishant Shah

DIFFICULTY:

SIMPLE

PREREQUISITES:

Greedy

PROBLEM:

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

EXPLANATION:

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.

TIME COMPLEXITY:

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)

SOLUTIONS:

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

2

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.

3

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
4

Right, thanks for pointing this out!