Maximum Average Pass Ratio

Problem Statement

In a given scenario within a school system, we have several classes, each scheduled to take a final exam. The dataset representing these classes is structured as a 2D integer array named classes. Each subarray, classes[i], is composed of two integers [passi, totali] indicating the number of students (passi) expected to pass the exam out of the total students (totali) enrolled in the ith class.

Additionally, you are provided with an integer extraStudents. This integer represents a number of exemplary students who are certain to pass the exam in whatever class they are placed in. The challenge is to distribute these extraStudents among the classes in such a manner that the average pass ratio across all classes is maximized.

The pass ratio for a class is defined as the ratio of students passing to total students in the class. The objective is to return the maximum possible average pass ratio after the optimal distribution of extra students. The solution should be precise up to a tolerance of 10^-5.

Examples

Example 1

Input:

classes = [[1,2],[3,5],[2,2]], `extraStudents` = 2

Output:

0.78333

Explanation:

You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.

Example 2

Input:

classes = [[2,4],[3,9],[4,5],[2,10]], `extraStudents` = 4

Output:

0.53485

Constraints

• 1 <= classes.length <= 105
• classes[i].length == 2
• 1 <= passi <= totali <= 105
• 1 <= extraStudents <= 105

Approach and Intuition

To tackle this problem, one needs to understand that the benefit (increase in the pass ratio) of adding an extra student to a class varies based on the current number of students passing and the total students in that class. Here is how one can strategically think about placing the extra students:

1. The impact of adding an extra student to any class on the overall average pass ratio should be evaluated. Specifically, the incremental pass ratio gain from adding an extra student to a class can be determined by comparing the new pass ratio after adding a student versus the original pass ratio.
2. To efficiently manage this, using a priority data structure like a max-heap is beneficial. The heap will prioritize classes based on the maximum potential increase in pass ratio per extra student added.
3. Initialize the heap with all classes, each class's priority based on the potential pass ratio increase from adding one extra student.
4. Iteratively assign one extra student at a time to the class which currently has the maximum potential increase in pass ratio (i.e., the class at the top of the heap). After assigning a student, recalculate the potential increase for that class and adjust its position in the heap.
5. Continue this process until all extra students are assigned.
6. The goal is iteratively to maximize the smallest improvements first, leading to an overall maximal average pass ratio across all classes.

This strategy, while computational, ensures each extra student is placed in the class where they make the most significant impact on the average pass ratio. By focusing on quantifying the benefit of each assignment, one can iteratively converge on the optimal solution.

Solutions

class Solution {
public:
    double findMaximumAverageRatio(vector<vector<int>>& classList, int additionalStudents) {
        // Function to compute the incremental ratio after adding a student
        auto computeIncrement = [](int passed, int total) {
            return (double)(passed + 1) / (total + 1) - (double)passed / total;
        };
    
        // Priority queue to manage the maximum ratio gain first
        priority_queue<pair<double, pair<int, int>>> gainQueue;
        for (const auto& cl : classList) {
            gainQueue.push({computeIncrement(cl[0], cl[1]), {cl[0], cl[1]}});
        }
    
        // Applying extra students to the classes
        while (additionalStudents--) {
            auto [gain, classStat] = gainQueue.top();
            gainQueue.pop();
            int passed = classStat.first;
            int total = classStat.second;
            gainQueue.push({computeIncrement(passed + 1, total + 1), {passed + 1, total + 1}});
        }
    
        // Calculate the overall average pass ratio of all classes
        double totalRatio = 0;
        while (!gainQueue.empty()) {
            auto [_, stats] = gainQueue.top();
            gainQueue.pop();
            totalRatio += (double)stats.first / stats.second;
        }
    
        return totalRatio / classList.size();
    }
};