932. Which Class Gets Each Extra Student

A school has n classes. Class i currently has t[i] students of whom p[i] are expected to pass, so its pass ratio is p[i] / t[i]. The school is judged on the AVERAGE of the n class ratios.

k extra students arrive, one at a time, and each is certain to pass. Each one is placed in the class where adding them raises the average by the most; when several classes tie, the one with the smallest index wins.

Print the k class indices in the order they are chosen.

classes (1,2) (3,5) (2,2), k = 2 -> 0 0 classes (0,1), k = 3 -> 0 0 0 classes (1,1) (1,1), k = 1 -> 0

In the first example class 0 gains 2/3 - 1/2 = 1/6, class 1 gains 4/6 - 3/5 = 1/15, and class 2 already passes everybody so it gains 0. Class 0 wins. After the student joins, class 0 is (2,3) and gains 3/4 - 2/3 = 1/12, which still beats 1/15, so class 0 wins again.

## What most people try first

Putting every student in the class with the lowest ratio is wrong, and two classes show why. A class of (0, 1) has ratio 0 and adding a student takes it to 1/2, a gain of 1/2. A class of (0, 100000) also has ratio 0, and adding a student takes it to 1/100001, a gain of about one part in 100000. Same ratio, gains five orders of magnitude apart. The ratio and the gain are different quantities, and ordering by the wrong one picks the wrong class.

Recomputing all n gains before each of the k placements is O(nk), which at n = 10^5 and k = 10^3 is 10^8 and is the thing to beat.

## The derived key

The gain of adding one guaranteed pass to a class (p, t) is

p + 1 p t - p ----- - - = --------- t + 1 t t (t + 1)

Divided by n to become the change in the average, but n is the same for every class so it does not affect the ordering and can be dropped.

That expression is the key the heap is ordered by. It is not the ratio, not the class size and not the number failing; it is the specific combination above, and finding it is the problem.

## The method

h = max-heap of (gain, index), gain compared exactly, ties by smaller index push every class with its current gain repeat k times: pop the best; output its index p = p + 1; t = t + 1 for that class recompute its gain and push it back

The key CHANGES when a class receives a student, which is why the entry is popped, updated and pushed rather than modified in place. Problem #922 makes the same move and explains why almost no library lets you edit a heap entry directly.

## Comparing gains without floating point

Never compare these as doubles. Two classes can have gains differing in the fifteenth decimal place, and at t = 10^5 the gains themselves are around one part in 10^10, where double rounding decides the tie rather than the arithmetic.

Compare a1 / b1 against a2 / b2 by cross-multiplying, with both denominators positive:

a1 / b1 > a2 / b2 is a1 * b2 > a2 * b1

## Why the greedy is correct

Each placement is independent of the others in this sense: adding a student to class i changes only class i's ratio, and the gain available from any OTHER class is unaffected. So the problem is to pick k items from n sequences of gains, one sequence per class, taking each sequence's gains in order.

Within one class the gains strictly decrease, because

t - p t - p (t+1) - (p+1) --------- versus ------------------ and ----------------- t (t + 1) (t+1) (t+2) (t+1) (t+2)

the numerator is unchanged by adding one to both p and t, while the denominator grows, so each successive gain is smaller. A class therefore cannot offer a later gain before an earlier one, so the k largest gains overall are obtained by repeatedly taking the largest currently available, which is exactly the heap.

## The boundary that breaks a careless implementation

A class with p == t has gain 0 and stays at 0 forever. It must still take part in the tie-break, because when every class is full the smallest index wins, and a heap that drops zero-gain classes cannot answer that.

The tie-break is on the class INDEX, and it must survive the update: a class pushed back keeps its own index rather than being re-inserted at the end.

## Overflow

The denominator t (t + 1) reaches 10^5 * (10^5 + 1), about 10^10, which already exceeds 32 bits. The cross-multiplied comparison is a numerator up to 10^5 times a denominator up to 10^10, so about 10^15. That fits in a signed 64-bit integer, which holds about 9.2 * 10^18, and it also fits exactly in a double, whose integers are exact to 2^53 = 9007199254740992.

The declared test with classes (0, 100000) and (99999, 100000) computes that product and a 32-bit build picks the wrong class on the very first placement.

## Related problems

Problem #807 also optimises a ratio of sums and does it by binary searching the answer, because there the choice changes the denominator of a single combined ratio. Here each choice touches one class only, so the gains are separable and a greedy over a heap is exact.

## Cost

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

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ k ≤ 1000` - `1 ≤ t[i] ≤ 100000` - `0 ≤ p[i] ≤ t[i]`