Exam Pass Boost
MediumHeap / Priority Queue
Problem
A school has several classes; classes[i] = [passed, total] means passed of the total students in class i will pass the final exam. The school also has extra brilliant transfer students, each guaranteed to pass, and can place each one in any class.
The school's score is the average of the pass ratios of its classes. Distribute all transfer students to maximise that score, and return it.
Example 1
- Input:
- classes = [[1, 2], [3, 5], [2, 2]], extra = 2
- Output:
- 0.78333
Both go to class 0: ratios 3/4, 3/5, 2/2 → (0.75 + 0.6 + 1) / 3 ≈ 0.78333.
Example 2
- Input:
- classes = [[0, 1]], extra = 3
- Output:
- 0.75
The only class becomes 3/4.
Constraints
- 1 ≤ classes.length ≤ 10^5
- 1 ≤ total ≤ 10^5, 0 ≤ passed ≤ total
- 0 ≤ extra ≤ 10^5
- Answers within 10^-5 are accepted.
Hint
Show the first hint
Think about one transfer student at a time. Where does a single student raise the average the most?
Walkthrough
How to approach it
01Clarify before coding
- Must every transfer student be placed? Yes, but placing one never lowers a ratio, so that is never harmful.
- Is the score the average of ratios, not the overall pass rate? Yes, every class weighs the same.
- Precision? 10^-5.
02Brute force
Try every way to split extra students among n classes and keep the best average.
Cost: C(extra + n - 1, n - 1) distributions: astronomically many. Even 'pick the best class per student by scanning' is O(extra · n) = 10^10.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.