Original Problem

Full Problem

Uh Oh! Ms. Strict’s class just had an exam, and all $N$ students failed, each with score $a_i$. Even more unfortunately, Ms. Strict’s class has been chosen by the Massachusetts Department of Education to assess LHS’ academic readiness!

In order to save the school’s reputation, Principles Snehpets has hired you, a PRO HACKER, to hack into the system and change the students’ scores. However, it would be very suspicious if the scores’ total sum changes, or if any score is negative. In addition, increasing or decreasing a score by $1$ costs $1$ dollar, and since LHS is so broke, you can only spend at most $K$ dollars. Help Principles Snehpets find the maximum possible median score after the changes.

Formally, given an array $a_1, a_2, \cdots, a_N$, find the maximum number $x$ such that there exists another sequence $b_1, b_2, \cdots, b_N$ with median $x$, such that $b_i \geq 0$, $\left(\sum{a_i}\right) = \left(\sum{b_i}\right)$, and $\left(\sum{|a_i - b_i|}\right) \leq K$. Also note that since $N$ is guarenteed to be odd, the median is always the $\frac{N + 1}{2}$-th largest element.

Constriants:

$N \leq 2 \cdot 10^5$, $0 \leq K \leq 10^18$, and $0 \leq a_i \leq 10^9$. And N must be odd so $N \equiv 1 \pmod{2}$.

Input Format

The first line has two integers $N$, and $K$ ― the number of elements and the maximum cost The next line contains $N$ integers, where the $i$th number is the score of the $i$th student $a_i$,

Output Format

Output the maximum achievable median after the changes.

Sample Input

5 8
1 3 5 7 9

Sample Output

8

Definitions

Median

Given multiple numbers, sort them from least to greatest and find the value of the middle element. In cases where there are an even amount of items, we take the arthmetic mean of both numbers (add them and divide by 2).

Solution

This reminded me of a certain math problems from mathcounts.

A set of six distinct positive integers has a mean of 8, a median of 8 and no term greater than 13. What is the least possible value of any term in the set?

– 2015 Chapter

A set of six distinct positive integers has a mean of 8, a median of 8 and no term greater than 13. What is the least possible value of any term in the set?

– 2016 Chapter

A set of seven distinct positive integers has its mean and its median both equal to 30. What is the largest possible integer this set can contain?

– 2010 Sprint

In all of those problems, the optimization strategy is as follows. Say you have the following

1 2 3 4 5 6 7 8 9 1011
1 2 2 3 3 4 4 5 5 5 6

Observe that changing anything above the median does not help us. Changing the lowest number does not help us at first instantly either, because it’ll either stay the same or move up when sorted. Thus we start by increasing the center numbers because they contribute the most to the median. We can’t affect the median in one step due to the sorting so we have to change both 6 and 7.

1 2 3 4 5 6 7 8 9 1011
1 2 2 3 3 5 5 5 5 5 6

We use this greedy strategy until we run out of money.

Impl

#include <bits/stdc++.h>
#define MAXN 200002
// for reference 10e18
#define MAXK 1000000000000000001

#define DEBUG 0

using namespace std;

int arr[MAXN];

priority_queue<int, vector<int>, greater<int>> pq;

void solve(){
    int N;
    long long K;
    cin >> N >> K;
    K = K/2;
    for(int i = 0; i < N; i ++){
        cin >> arr[i];
    }

    sort(arr, arr + N); // DO I NEED THIS???

    int med = (N - 1)/2; // for 0 indexed
    long long usable = 0;
    for(int i = 0; i < med; i ++){
        usable += arr[i]; // until 0
    }
    usable = min(usable, K); // K is limit

    for(int i = med + 1; i < N; i ++){
        pq.push(arr[i]);
    }

    long long ans;

    long long raising = 1LL;
    int currentMedian = arr[med];

    while(!pq.empty() && usable > 0){
        int target = pq.top();
        long long costToReachTarget = ((long long)target - (long long) currentMedian) * raising;
        if(costToReachTarget <= usable){
            usable -= costToReachTarget;
            currentMedian = target;
            if(DEBUG) cout << "Raised to " << target << endl;
            pq.pop();
            raising ++;
        }else{
            // How much more can we go partially
            long long inc = floor(usable / raising);
            usable -= inc * raising; // nearest decrease
            if(DEBUG) cout << "Partial increase from " << currentMedian << " to " << currentMedian + inc << endl;
            currentMedian += inc;
            break; // bye
        }
    }

    if(usable > 0){
        long long raisable = floor(usable / raising); // this shall floor
        if(DEBUG) cout << "Extra raising " << raisable << " usable " << usable << " raising " << raising << endl;
        currentMedian += raisable;
        usable -= raisable * raising;
    }
    
    cout << currentMedian << endl;
}

int main(int argc, char const *argv[])
{
    solve();   
    return 0;
}