Maximum Average Pass Ratio

medium heap greedy

Problem

Each class is given as [pass, total]: of its total exam takers, pass will pass. You also have extraStudents brilliant students who are guaranteed to pass whatever class you place them in — assigning one to a class turns its ratio from pass/total into (pass+1)/(total+1).

Place every extra student so that the average pass ratio (the mean of pass/total over all classes) is as large as possible. Answers within 10⁻⁵ of the optimum are accepted.

Inputclasses = [[1,2],[3,5],[2,2]], extraStudents = 2

Output0.78333

Both extras go to the first class (1/2 → 3/4): (3/4 + 3/5 + 2/2) / 3 ≈ 0.78333.

classes (pass/total, comma-separated)

extraStudents

import heapq

def max_average_ratio(classes, extra_students):
    def gain(p, t):
        return (p + 1) / (t + 1) - p / t

    heap = [(-gain(p, t), p, t) for p, t in classes]
    heapq.heapify(heap)
    for _ in range(extra_students):
        g, p, t = heapq.heappop(heap)
        p, t = p + 1, t + 1
        heapq.heappush(heap, (-gain(p, t), p, t))
    return sum(p / t for _, p, t in heap) / len(classes)

function maxAverageRatio(classes, extraStudents) {
  const gain = (p, t) => (p + 1) / (t + 1) - p / t;
  // max-heap of [gain, pass, total] (array kept sorted)
  const heap = classes.map(([p, t]) => [gain(p, t), p, t]);
  heap.sort((a, b) => b[0] - a[0]);
  for (let i = 0; i < extraStudents; i++) {
    const [, p, t] = heap.shift();   // class with best gain
    heap.push([gain(p + 1, t + 1), p + 1, t + 1]);
    heap.sort((a, b) => b[0] - a[0]);
  }
  return heap.reduce((s, [, p, t]) => s + p / t, 0) / classes.length;
}

double maxAverageRatio(int[][] classes, int extraStudents) {
    PriorityQueue<double[]> heap =
        new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));
    for (int[] c : classes) {
        double p = c[0], t = c[1];
        heap.offer(new double[]{(p + 1) / (t + 1) - p / t, p, t});
    }
    for (int i = 0; i < extraStudents; i++) {
        double[] top = heap.poll();
        double p = top[1] + 1, t = top[2] + 1;
        heap.offer(new double[]{(p + 1) / (t + 1) - p / t, p, t});
    }
    double sum = 0;
    for (double[] c : heap) sum += c[1] / c[2];
    return sum / classes.length;
}

double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
    auto gain = [](double p, double t) {
        return (p + 1) / (t + 1) - p / t;
    };
    priority_queue<tuple<double, double, double>> heap;
    for (auto& c : classes)
        heap.push({gain(c[0], c[1]), c[0], c[1]});
    for (int i = 0; i < extraStudents; i++) {
        auto [g, p, t] = heap.top(); heap.pop();
        heap.push({gain(p + 1, t + 1), p + 1, t + 1});
    }
    double sum = 0;
    while (!heap.empty()) {
        auto [g, p, t] = heap.top(); heap.pop();
        sum += p / t;
    }
    return sum / classes.size();
}

Explanation

The key observation is that an extra student changes only the class that receives them, and by a fixed, computable amount: the class's ratio moves from p/t to (p+1)/(t+1), a gain of (p+1)/(t+1) − p/t. Since the average is just the sum of ratios divided by a constant n, maximizing the average means maximizing the total gain we collect.

That makes a greedy strategy natural: hand each extra student, one at a time, to the class with the largest current gain. A max-heap keyed by gain makes this fast — push every class with its gain, then for each student pop the top, add the student, recompute the (now smaller) gain, and push the class back.

Why is greedy safe? Gains are independent across classes and within one class they are strictly decreasing: each added student shrinks the next student's gain. So the final total is just a sum of per-student gains drawn from these decreasing sequences, and picking the largest available gain every time is exactly how you maximize such a sum — swapping any chosen gain for a skipped larger one can only help, so an optimal solution may be rearranged into the greedy one.

Walking through the default example [[1,2],[3,5],[2,2]] with 2 extras: the gains are 0.167, 0.067 and 0 (the full 2/2 class can never improve). Student 1 goes to class 1, which becomes 2/3 with a new gain of 0.083 — still the best, so student 2 also goes there, making it 3/4. The average is (0.75 + 0.6 + 1.0) / 3 ≈ 0.78333.

Note the diminishing returns at work: a nearly-full class like 2/2 gains nothing, while a half-empty class gains a lot, which matches the intuition that brilliant students help most where the pass ratio has room to grow.

Building the heap costs O(n) (or O(n log n) with pushes), and each of the k students triggers one pop and one push at O(log n) each, for O((n + k) log n) time and O(n) extra space.

Time: O((n + k) log n) Space: O(n)