Solution for waifujahat | C# 119ms 100% / C++ 164ms 100% | Max Heap
C# SubmissionsC++ SubmissionsHow to SolvePersonally I think this task is hard, rather than medium. I need to maximizing the average pass ratio after distributin
# C# Submissions\n![Screenshot 2024-12-15 113825.png](https://assets.leetcode.com/users/images/d0d5c79d-6ad8-480b-9458-7bc92d923f7d_1734237523.5146198.png)\n\n---\n\n# C++ Submissions\n![Screenshot 2024-12-15 125138.png](https://assets.leetcode.com/users/images/92f3377b-7492-48bd-a5c4-cd5920457c91_1734241979.0669122.png)\n\n---\n\n# How to Solve\n\nPersonally I think this task is hard, rather than medium. I need to maximizing the average pass ratio after distributing extra students across multiple classes. Each class has a pass ratio defined as `pass i / total i`. Assigning an extra student increases both `pass i` and `total i` by 1, but the extent of this improvement varies between classes. So, after watch some other people solutions, I think I know how to maximizing the overall average pass ratio, here :\n1. Just focus on classes where an extra student results in the largest improvement to the pass ratio\n2. Repeate selecting the class with the highest potential improvement or profit from assigning an extra student\n\nThe profit of adding a student to a class is the difference between the new pass ratio `pass i + 1` / `total i + 1` and the current pass ratio `pass i` / `total i`. So I decide to use `Max Heap` for selecting the class with the largest profit and every extra student assigned, I update the selected class and re-insert it into the heap with the new profit, ensuring the heap remains sorted by maximum profit. Pop the class with the highest profit and update `pass i` and `total i`, re-compute profit and re-insert it into the heap. I repeat until all extra students are assigned or no more improvement is possible. After assigning all extra students, compute the average pass ratio by summing the pass ratios of all classes and dividing by the number of classes.\n\nI need to be careful, with `The Constraints`, the result must be accurate within `10\u207B\u2075`. So, with up to `10\u2075` classes and students, I need to code carefully, every time a student is assigned, the heap must be update heapify operations. If the heap isn\'t updated correctly after recalculating profits, I may select suboptimal classes or fail to converge on the correct result, for example, recalculating profits in a suboptimal way or using recursive heapify operations for large inputs can lead TLE. \n\nThanks to those who have breakdown the logic and calculations, so I just need to find a way to coding my code much better. I wil explain my code :\n\n1. Create a heap to store the profit for each class along with the current pass and total student counts\n2. Populate initial values and heap\nCompute the initial pass ratio and calculate the profit of adding one student to that class using `CalculateProfit` then insert the class into the heap with the calculated profit.\n3. Build Max Heap\n4. Distribute extra students\nExtract the class with the maximum profit root of the heap, add one student to that class and update its pass ratio, recalculate the profit for this class after the addition of a student and update the heap with the new values and repeat this until all extra students are assigned.\n5. The heap is maintained using a simple binary heap structure and `HeapifyDown` ensures that the heap property is maintained by comparing parent and child nodes.\n6. Finally, the average pass ratio is computed by dividing the total pass ratio by the number of classes.\n\nSorry if I\'m bad at explaining, leave comments if you have any questions, I will reply. Please up vote.\n\n---\n# Code\n```csharp []\npublic class Solution {\n    public double MaxAverageRatio(int[][] classes, int extraStudents) {\n\n        int n = classes.Length;\n        double total = 0;\n        // Create a heap to store the profit for each class along with the current pass and total student counts\n        var heap = new (double Increment, int Passes, int Total)[n];\n        int heap_size = 0;\n\n        // Populate the heap with initial values and calculate the total pass ratio\n        for (int i = 0; i < n; i++) \n        {\n            int pass = classes[i][0], totalStudents = classes[i][1];\n            // Add the pass ratio for the current class to the total\n            total += (double)pass / totalStudents;\n            // Calculate the potential increment in pass ratio by adding 1 extra student\n            heap[heap_size++] = (CalculateProfit(pass, totalStudents), pass, totalStudents);\n        }\n\n        //  Build the heap to prioritize the class with the highest profit\n        BuildHeap(heap, heap_size);\n\n        // Assign extra students to the classes with the highest potential profit\n        while (extraStudents-- > 0) \n        {\n            var (maxIncrement, pass, totalStudents) = heap[0];\n\n            // If there is no increment possible, break\n            if (maxIncrement <= 0) \n            break;\n\n            total += maxIncrement;\n            pass++;\n            totalStudents++;\n            // Recalculate the new increment profit after adding a student\n            heap[0] = (CalculateProfit(pass, totalStudents), pass, totalStudents);\n            // Reheapify the heap to maintain the heap property\n            HeapifyDown(heap, 0, heap_size);\n        }\n        // Calculate and return the average pass ratio across all classes\n        return total / n;\n    }\n\n    // Calculate the profit, increase in pass ratio when adding a student to a class\n    private double CalculateProfit(int pass, int total) {\n        \n        double current_pass = (double)pass / total;\n        double new_pass = (double)(pass + 1) / (total + 1);\n        \n        return new_pass - current_pass;\n    }\n\n    // Build the max heap by reheapifying from the bottom to the top\n    private void BuildHeap((double Increment, int Passes, int Total)[] heap, int size) {\n\n        // Start from the last non leaf node and heapify upwards\n        for (int i = size / 2 - 1; i >= 0; i--) \n        {\n            HeapifyDown(heap, i, size);\n        }\n    }\n\n    // Heapify the heap from index i downwards to ensure the heap property is maintained\n    private void HeapifyDown((double Increment, int Passes, int Total)[] heap, int i, int size) {\n\n        // Repeat until the heap property is satisfied\n        while (true) \n        {\n            int largest = i;\n            int left = 2 * i + 1;\n            int right = 2 * i + 2;\n\n            // If left child exists and has larger increment\n            if (left < size && heap[left].Increment > heap[largest].Increment) \n            {\n                largest = left;\n            }\n            // If right child exists and has larger increment\n            if (right < size && heap[right].Increment > heap[largest].Increment) \n            {\n                largest = right;\n            }\n            // If the largest value is already at i, the heap property is satisfied\n            if (largest == i) \n            break;\n\n            // Swap the current node with the largest child\n            (heap[i], heap[largest]) = (heap[largest], heap[i]);\n            // Move to the child\n            i = largest;\n        }\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {\n\n        int n = classes.size();\n        double total = 0;\n        // Create a heap to store the profit for each class along with the current pass and total student counts\n        vector<tuple<double, int, int>> heap;\n\n        // Populate the heap with initial values and calculate the total pass ratio\n        for (int i = 0; i < n; i++) \n        {\n            int pass = classes[i][0], totalStudents = classes[i][1];\n            // Add the pass ratio for the current class to the total\n            total += (double)pass / totalStudents;\n            // Calculate the potential increment in pass ratio by adding 1 extra student\n            heap.push_back(make_tuple(CalculateProfit(pass, totalStudents), pass, totalStudents));\n        }\n\n        // Build the heap to prioritize the class with the highest profit\n        MakeHeap(heap);\n\n        // Assign extra students to the classes with the highest potential profit\n        while (extraStudents-- > 0) \n        {\n            auto [maxIncrement, pass, totalStudents] = heap[0];\n\n            // If there is no increment possible, break\n            if (maxIncrement <= 0)\n            break;\n\n            total += maxIncrement;\n            pass++;\n            totalStudents++;\n            // Recalculate the new increment profit after adding a student\n            heap[0] = make_tuple(CalculateProfit(pass, totalStudents), pass, totalStudents);\n            // Reheapify the heap to maintain the heap property\n            HeapifyDown(heap, 0);\n        }\n\n        // Calculate and return the average pass ratio across all classes\n        return total / n;\n    }\n\nprivate:\n    // Calculate the profit, increase in pass ratio when adding a student to a class\n    double CalculateProfit(int pass, int total) {\n\n        double current_pass = (double)pass / total;\n        double new_pass = (double)(pass + 1) / (total + 1);\n\n        return new_pass - current_pass;\n    }\n\n    // Build the max heap by reheapifying from the bottom to the top\n    void MakeHeap(vector<tuple<double, int, int>>& heap) {\n\n        // Start from the last non-leaf node and heapify upwards\n        for (int i = heap.size() / 2 - 1; i >= 0; i--) \n        {\n            HeapifyDown(heap, i);\n        }\n    }\n\n    // Heapify the heap from index i downwards to ensure the heap property is maintained\n    void HeapifyDown(vector<tuple<double, int, int>>& heap, int i) {\n\n        int size = heap.size();\n\n        while (true) \n        {\n            int largest = i;\n            int left = 2 * i + 1;\n            int right = 2 * i + 2;\n\n            // If left child exists and has a larger increment\n            if (left < size && get<0>(heap[left]) > get<0>(heap[largest])) \n            {\n                largest = left;\n            }\n            // If right child exists and has a larger increment\n            if (right < size && get<0>(heap[right]) > get<0>(heap[largest])) \n            {\n                largest = right;\n            }\n            // If the largest value is already at i, the heap property is satisfied\n            if (largest == i)\n            break;\n\n            // Swap the current node with the largest child\n            swap(heap[i], heap[largest]);\n            // Move to the child\n            i = largest;\n        }\n    }\n};\n```
['Greedy', 'Heap (Priority Queue)', 'C++', 'C#']