We will discuss the solution to Prime Minister from AIO 2026.
We have no money to distribute, so the answer is just the initial median.
Since the wealth values are already given in sorted order, the median is the middle value, A(N+1)/2.
Be careful with this in your code: in a list starting from 0, the median is A[N//2] in Python or A[N/2] in C++.
For example, in sample input 2 the median of [4, 6, 6, 9, 10] is A[2] = 6.
Let's call H = (N+1)/2, which is the number of citizens in the middle and above
of the sorted list.
For the median to be at least x, at least H citizens must each have at least x dollars.
(Think about why: if fewer than H citizens had x or more, then the middle citizen in the sorted list would have less than x.)
Since everyone starts with 0 dollars, a median of x costs at least H × x dollars. We can achieve this by giving x dollars to each of any H citizens. The largest x we can afford is ⌊K/H⌋, which is our answer. Any leftover money can be given to one of these citizens without reducing the median.
For example, in sample input 3 we have N = 3, so H = 2. With K = 5 dollars we can give 2 dollars each to two citizens, so the answer is ⌊5/2⌋ = 2. The 1 leftover dollar can go to anyone.
For the remaining subtasks, we use the same idea: to get a median of at least x, we need at least H citizens to have at least x dollars. Which H citizens should we choose? Raising citizen i's wealth to x costs max(0, x-Ai) dollars, so a citizen who starts with more is always at least as cheap to raise as a citizen who starts with less. Therefore the cheapest choice is always the last H citizens in the sorted list: the citizen at the initial median and everyone to their right.
This means it never helps to give money to the citizens before the median in the sorted list, so we only need to decide how to share the money among these H citizens. The median after our distribution is then the smallest wealth among our chosen H citizens. So our problem becomes: distribute K dollars among these H citizens to make the smallest wealth as large as possible.
We can distribute the money one dollar at a time. Each time, we find a citizen with the smallest wealth among our chosen H citizens and give them 1 dollar. This makes sense: giving money to anyone other than a citizen with the smallest wealth wouldn't help raise the smallest wealth. If several citizens are tied for the smallest wealth, it doesn't matter which one we choose.
Let's look at sample input 1, where the wealth values are [1, 2, 5, 6, 9] and K = 4. Our chosen citizens have wealth 5, 6, and 9.
Let's analyse the time complexity of this solution. Finding the smallest wealth takes O(N) time for each of the K dollars, giving a time complexity of O(NK + N) (the extra N is for reading the input). This is fast enough to solve subtask 3 but not the later subtasks.
The slow part of the previous solution is finding the smallest wealth each time.
We can speed this up using a priority queue (also called a heap), which is a data structure designed for exactly this job.
It lets us remove the smallest wealth, increase it by 1, and put it back, all in O(log N) time per dollar.
In Python we can use the heapq module, and in C++ we can use a std::priority_queue that is set up to return its smallest element.
The resulting time complexity is O((N+K) log N), which is fast enough for this subtask.
Now K can be up to a billion, so we can't afford to hand out one dollar at a time. Instead, let's look at the subtask 3 example again and notice what is happening. Once two citizens are tied at 6, we end up raising them together: first both to 7, and then (if we had enough money) both to 8, and so on. So rather than giving out single dollars, we can raise a whole group of tied citizens at once.
Suppose we have a group of g citizens who are all tied for the smallest wealth, which we'll call level. The next citizen in the sorted list, just outside the group, has wealth next. Raising our whole group up to next costs (next - level) × g dollars.
We start with a group containing just the citizen at the initial median, and consider each citizen after them in the sorted list in order. If the next citizen already has the same wealth as our group, the cost is 0 and they join immediately. If all H citizens end up in the group, we can raise everyone by ⌊K/H⌋ using the remaining money.
Here is this method on sample input 1, where our chosen citizens have wealth 5, 6, and 9, and K = 4:
| level | g | Money left | next | Cost to reach next | What happens |
|---|---|---|---|---|---|
| 5 | 1 | 4 | 6 | (6-5) × 1 = 1 | We can afford it |
| 6 | 2 | 3 | 9 | (9-6) × 2 = 6 | We can't afford it, so the answer is 6 + ⌊3/2⌋ = 7 |
This matches what we found by handing out one dollar at a time, but with far fewer steps!
The video below shows the same steps, raising the whole group at once.
Each citizen joins the group at most once, so this solution has a time complexity of O(N) which is fast enough to score 100.
If you are using C++, be careful: the cost (next - level) × g can be much larger than the range of an int, so we use long long.
There is also a different full solution using binary search. For a proposed median x, we can compute the cost of reaching it by adding max(0, x-Ai) over the last H citizens in the sorted list, and check whether this is at most K. If we can afford a median of x, we can also afford any smaller median, so we can binary search for the largest affordable value. The answer is always between the initial median and the initial median plus K, which gives a time complexity of O(N log(K+1) + N). As an exercise, try coding this solution yourself!
Below you can see the O(N) full solution written in Python and C++. I suggest trying to code the solution yourself and only look at our code after you finish or if you get stuck.
# N is the number of citizens.
N = 0
# K is the amount of money to distribute.
K = 0
# A contains the initial wealth of each citizen in sorted order. Note that the
# list starts from 0, and so the values are A[0] to A[N-1].
A = []
# Read the values of N, K, and the initial wealth values.
N, K = map(int, input().strip().split())
A = list(map(int, input().strip().split()))
# Compute the answer
# Our group starts with just the citizen at the initial median
middle = N // 2
level = A[middle] # level stores the wealth of every citizen in the group
group = 1 # group stores the number of citizens in the group
# Try to raise the group to the wealth of each later citizen in turn
# From now on, K stores the amount of money we have left
for i in range(middle+1, N):
cost = (A[i] - level) * group
if cost > K:
# We can't afford to reach A[i]
break
K -= cost
level = A[i]
group += 1 # Citizen i has joined the group
# Share the remaining money evenly among the group
answer = level + K // group
print(answer)
#include <cstdio>
/* N is the number of citizens. */
int N;
/* K is the amount of money to distribute. */
long long K;
/*
* A contains the initial wealth of each citizen in sorted order. Note that the
* array starts from 0, and so the values are A[0] to A[N-1].
*/
long long A[200005];
int main(void) {
/* Read the values of N, K, and the initial wealth values. */
scanf("%d%lld", &N, &K);
for (int i = 0; i < N; i++) {
scanf("%lld", &A[i]);
}
/* Compute the answer */
// Our group starts with just the citizen at the initial median
int middle = N / 2;
long long level = A[middle]; // level stores the wealth of every citizen in the group
int group = 1; // group stores the number of citizens in the group
// Try to raise the group to the wealth of each later citizen in turn
// From now on, K stores the amount of money we have left
for (int i = middle+1; i < N; i++) {
long long cost = (A[i] - level) * group;
if (cost > K) {
// We can't afford to reach A[i]
break;
}
K -= cost;
level = A[i];
group++; // Citizen i has joined the group
}
/* Share the remaining money evenly among the group */
long long answer = level + K / group;
printf("%lld\n", answer);
}