Maximum Average Pass Ratio

Updated on 12 June, 2025
Maximum Average Pass Ratio header image

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

  • C++
  • Java
  • Python
cpp
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();
    }
};

The solution deals with calculating the maximum possible average pass ratio after distributing additional students among a number of classes. Implemented in C++, it incorporates a priority queue for efficiency in selecting the class that will most improve the average pass ratio with an additional student.

Follow this implementation outline:

  1. Define the function findMaximumAverageRatio that accepts a 2D vector classList representing pairs of currently passed students and total students per class, and an integer additionalStudents.

  2. Create a lambda function computeIncrement to calculate the incremental ratio gain if one more student were to pass in a given class.

  3. Use a max priority queue gainQueue to keep track of the class gains with the higher gain classes getting priority. Each item in the queue holds the potential gain and current class statistics (pass and total students).

  4. Process the addition of all extra students by repeatedly taking the top element from gainQueue (class with max gain), updating its pass count, recalculating its gain, and pushing it back into the queue.

  5. After distributing all students, calculate the total average pass ratio of all classes by iterating through gainQueue and summing up the ratios of passes to total students in each class.

  6. Divide the aggregated pass ratios by the number of classes to obtain the final average and return it.

This solution uses the priority queue for tracking and updating the class with maximum incremental gain effectively, making the process of maximizing the average pass ratio much more efficient than a linear scan approach.

java
class Solution {
    
    public double findMaxAverage(int[][] classes, int extra) {
        PriorityQueue<double[]> priorityQueue = new PriorityQueue<>((x, y) ->
            Double.compare(y[0], x[0])
        );
    
        for (int[] cla : classes) {
            int pass = cla[0];
            int total = cla[1];
            double improvement = computeImprovement(pass, total);
            priorityQueue.add(new double[] { improvement, pass, total });
        }
    
        while (extra-- > 0) {
            double[] top = priorityQueue.poll();
            double topGain = top[0];
            int pass = (int) top[1];
            int total = (int) top[2];
            priorityQueue.add(
                new double[] {
                    computeImprovement(pass + 1, total + 1),
                    pass + 1,
                    total + 1,
                }
            );
        }
    
        double aggregatePassRatio = 0;
        while (!priorityQueue.isEmpty()) {
            double[] top = priorityQueue.poll();
            int pass = (int) top[1];
            int total = (int) top[2];
            aggregatePassRatio += (double) pass / total;
        }
    
        return aggregatePassRatio / classes.length;
    }
    
    private double computeImprovement(int pass, int total) {
        return (
            (double) (pass + 1) / (total + 1) -
            (double) pass / total
        );
    }
}

In the Maximum Average Pass Ratio Java program, the solution focuses on boosting the pass ratio of a set of classes using extra slots while taking into account the largest potential gains first. The following actions occur in the program:

  • Define a PriorityQueue to manage classes in descending order of their potential improvement in pass ratio.
  • Iterate over each class, calculate its possible improvement in pass ratio if an extra student is passed, and add it to the PriorityQueue.
  • For each extra slot available, the class with the highest potential for improvement is updated—one student is added to both the passed and total students count, recalculating the improvement and re-adding it to the queue.
  • Sum the pass ratio for all classes in the queue and calculate the average by the number of classes.

The auxiliary function computeImprovement calculates the difference in ratio of passing students if one more student passes. This function is crucial for assessing which class could benefit most from the addition of one student in terms of pass ratio.

By managing class data with a priority queue, prioritizing those with maximum potential gain, and updating counts dynamically, this solution efficiently finds the maximum average pass ratio after distributing all extra slots.

python
class Solution:
    def calculate_max_average_ratio(
        self, class_list: List[List[int]], additional_students: int
    ) -> float:
        # Calculate improvement after adding one student
        def _improve_ratio(passed, total):
            return (passed + 1) / (total + 1) - passed / total
    
        # Priority queue to store classes with least beneficial gain
        priority_queue = []
        for passed, total in class_list:
            improvement = _improve_ratio(passed, total)
            priority_queue.append((-improvement, passed, total))
    
        # Transform list into a heap
        heapq.heapify(priority_queue)
    
        # Distribute additional students to classes
        for _ in range(additional_students):
            min_improvement, passed, total = heapq.heappop(priority_queue)
            heapq.heappush(
                priority_queue,
                (
                    -_improve_ratio(passed + 1, total + 1),
                    passed + 1,
                    total + 1,
                ),
            )
    
        # Compute the average pass ratio
        total_ratio = sum(
            passed / total for _, passed, total in priority_queue
        )
        return total_ratio / len(class_list)

This Python 3 solution optimizes the average pass ratio across a list of classes, each represented by a pair of integers (students who passed, total students). It uses a priority queue to ensure that additional students are allocated in a way that maximizes this average pass ratio after all students have been assigned.

  • First, define a helper function _improve_ratio within the class to calculate the impact of adding an additional student to a class.
  • Initialize an empty list, priority_queue, to store the impact of adding a student to each class along with the current count of passed and total students.
  • Convert priority_queue into a heap structure which allows for efficient retrieval of the class with the minimal improvement ratio.
  • For each additional student available, allocate them to the class where they cause the greatest increase in the pass ratio by repeatedly popping the class with the smallest improvement off the heap, updating it with the new student, then pushing it back onto the heap.
  • After all additional students have been allocated, calculate the total average pass ratio by summing the ratios of all classes and dividing by the number of classes.

This approach ensures that the additional students are distributed in a manner that maximally increases the overall pass ratio. The use of a heap-based priority queue is integral for efficient performance, particularly under constraints demanding frequent adjustments to the priority of elements.

Comments

No comments yet.