826. Raising the Median
A panel of n judges has given scores a[0] ... a[n-1], with n ODD. One appeal raises one
judge's score by exactly one point, and at most k appeals are allowed.
The published result is the MEDIAN, meaning the score at position n / 2 once the scores are
sorted into non-decreasing order. Print the largest median that can be published.
scores 1 3 5 7 9, k = 2 -> 7
scores 1 2 3, k = 0 -> 2
scores 4 4 4 4 4 4 4 4 4, k = 7 -> 5
## The cheapest way to force a given median
To publish a median of at least M, at least (n + 1) / 2 of the scores must end up at M
or above, because the median is the middle element of the sorted list and everything above it
is at least as large.
Sort the scores. The cheapest (n + 1) / 2 scores to push up to M are the LARGEST ones,
that is positions n/2 through n-1, because each of those is at least as large as any score
below it and therefore costs no more to lift. Formally, swapping any chosen score for a larger
unchosen one never increases the bill, so an optimal choice can always be rearranged into that
suffix.
So the check is
cost(M) = sum over i from n/2 to n-1 of max(0, M - a[i])
feasible(M) is cost(M) <= k
## Why the predicate is monotone
Every term max(0, M - a[i]) is non-decreasing in M, so cost is non-decreasing, so once
a median becomes unaffordable every larger one stays unaffordable. The achievable medians
therefore form a PREFIX and the answer is the largest of them.
## The bounds
lo = a[n/2], the current median, which costs nothing.
hi = a[n/2] + k, because even spending every appeal on the single middle score cannot lift it
further, and the median can never exceed the lifted middle score.
## The loop, searching for the last true
mid = hi - (hi - lo) / 2
feasible(mid) ? lo = mid : hi = mid - 1
The upward midpoint is again what keeps lo = hi - 1 from looping forever.
## Why the loop terminates
With the upward midpoint, lo < mid <= hi whenever lo < hi, so the success branch raises
lo strictly and the failure branch lowers hi strictly. The range is about 10^14 wide, so
around 47 iterations.
## What is printed when nothing can be improved
With k = 0 no appeal is available, cost(M) is positive for any M above the current
median, and the loop never leaves lo. The answer is the current median, which is what the
second example shows.
## The overflow that this problem really does hit
The honest sum can reach n / 2 terms of size 10^14, which is about 2 * 10^18 and sits
well inside the upper half of a signed 64-bit integer. Abandon the sum the moment it passes k:
for i from n/2 to n-1:
if a[i] >= mid: stop, the rest cost nothing
cost = cost + (mid - a[i])
if cost > k: fail immediately
Both early exits matter. The first is correct only because the list is sorted, so once one score
already clears mid every later one does too. The second caps the running total at just over
2 * 10^14, which is comfortably inside 64 bits and inside the exact-integer range of a
JavaScript number.
## Cost
Time O(n log n) for the sort plus O(n log k) for the search. Space O(n).
Constraints - `1 ≤ n ≤ 49999`, and `n` is odd - `0 ≤ k ≤ 100000000000000` - `1 ≤ a[i] ≤ 1000000000`
Input
The first line contains two integers n and k, the number of judges, which is odd, and the number of appeals.
The second line contains n integers a[0] ... a[n-1], the scores, in any order.
Output
Print one integer, the largest median score that can be published within the appeal budget. Print the median value itself, alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.