Faster Convergence | Heavy Math | C++ 64-91 ms 100%
IntuitionWe have an array of up to 105 classes containing class population (105, which is quite a large class) and the number of studends who are going to pass
# Intuition\nWe have an array of up to $10^5$ classes containing class population ($10^5$, which is quite a large class) and the number of studends who are going to pass a forthcoming exam successfully. We need to distribute up to $10^5$ extra studends across classes so as to maximize the average pass ratio, which is computed as the arithmetic average of pass ratios of individual classes.\n\nThere is a pretty obvious solution replicated all over the site and consisting of the following steps:\n1. Push all elements to a heap queue, using the influence factor to the class\'es pass ratio of adding one brillian student to it as a sort key. The influence factor is computed as $\\frac {p + 1} {t + 1} - \\frac p t = \\frac {t - p} {t \\times (t + 1)}$ where $t$ is the class population (number of students), and $p$ is the number of studends to pass the exam.\nSince it\'s not an integral number, a floating point type is typically used to hold it, along with the two initial class parameters (population and number of studends to pass the exam).\n2. Add studends one by one to the class whose ratio they would influence most. Since that would reduce the influence factor (the denominator grows with the numerator staying the same), the class should be repushed into some other position of the queue.\n3. Once there are no extra studends remaining, return the average pass ratio, which could be computed as the classes are being processed.\n\nThis ultimately results in some $O(n + s \\times log(n)))$ or even $O((n + s) \\times log(n)))$ time complexity where $s$ is the number of extra studends, and $n$ is the number of classes.\n\n# Approach\n\nGenerally we follow the same logic as described above, but not so blindly. Lets go through the steps and consider improvements.\n\n## Step 1 - Dump the Dead Weight\n\nAn unordered array can be converted into a heap in $O(n)$ time if we first populate it and then heapify it all at once. This is opposed to one-by-one element addition to a heap, resulting in some $O(n \\times log(n))$ asymptotic time.\n\nDo we really need to compute and store ratios, resulting in 128-bit tuples for queue elements (64 bit for rating and 32 bit for each of the two class parameters)? There is enough information for rating in the input data, and usually the memory access is a bottleneck, not the computation. The heap can run without storing ratios if we provide a comparator. Consider e.g. two elements $(p, t)$ and $(v, u)$ where $p$, $v$ are numbers of passing students, and $t$, $u$ are the total class populations. Then the expression $\\frac {t - p} {t \\times (t + 1)} < \\frac {u - v} {u \\times (u + 1)}$ can be converted to $(t - p) \\times v \\times (u + 1) < (u - v) \\times t \\times (t + 1)$, which is integer and does not require costly divisions to compute it. The max bit size of the expressions is somewhere around 50, therefore we have to allocate a 64-bit integer for it and not to forget to expand intermediate results.\n\nWe can also skip adding classes with 100% ratios ($p == t$) because their ratios won\'t be affected by extra studends. We still need to reflect them in the overall ratio, but don\'t have to place them onto our heap queue.\n\nSo we have lowered the queue\'s memory size more than twice, thus improving the memory locality.\n\nWe can also handle edge cases separately. E.g. if all classes are already brilliant, we can simply return 100% without any further processing. Also, if there is only one non-brilliant class, we end up adding all students to it and returning the resultant ratio (averaged out with the other rocket scientist 100% classes if any).\n\n## Step 2 - Improve Convergence\n\nDo we really need to process extra students one by one? Consider we have two classes $(p, t)$ and $(v, u)$, the first one being at the top of the queue, and the second one next to it. How many brilliant studends can we add to the first class so that its influence factor becomes barely lower than that of the second class? Let $d$ be the number of students to add.\n$\\frac {t - p} {(t + d) \\times (t + d + 1)} \\le \\frac {u - v} {u \\times (u + 1)}$\nThis can be transformed into a square inequality with regard to $d$:\n$d^2 + (2t + 1) \\times d + t \\times (t + 1) - \\frac {(t - p) \\times u \\times (u + 1)} {u - v} > 0$\nDespite a horrible appearance, its discriminant is computed relatively simply:\n$D = 4 \\times \\frac {(t - p) \\times u \\times (u + 1)} {u - v} + 1$\nThis expression is always positive, and we need the larger equation root as the minimal possible $d$ to add, applying the math rounding it (add $0.5$ and take the integer floor value).\n\nSo we can avoid twitching the top queue element back and forth if we have a hundred of studends to add to the class with a top influence factor. However this would work out only once on its own. If the numbers are large enough, once we add $d$ students to the first class, we engage into distributing students one at a time between the first and the second top classes, and may be other classes, because the factor difference becomes too small. What if we still have some $99000$ more students to distribute?\n\nWe are employing another trick to mitigate that. If the remaining number of the extra studends is high enough, we can try to compute a "fair share" $f$ to give it to the top class. Generally that should be in the order of $\\frac s m$ where $s$ is the remaining number of extra studends, and $m$ is the number of classes in the queue ($m \\le n$, see Step 1). The exact useful value of the "fair share", however, is smaller, because students could be distributed unevenly. We put it as $f = \\frac 1 4 \\times \\lceil \\frac s m \\rceil$, which is based on pure heuristic.\n\nOnce we have computed $d$ and $f$, we choose the larger one of them and ensure we always give at least one student to the top-influenced class. This way we improve the convergence time to an average of $m \\times log(s) \\times log(m)$, though with a high constant multiplier (since we cut only about $\\frac 1 {4m}$ off the remaining count). For a really small $s$ or large $m$, the convergence time degrates to $O(s \\times log(m))$.\n\n## Addition to Step 2\n\nAs pointed out by @yjian012, the "fair share" factor can be larger. $\\frac 1 2$ doesn\'t pass some tests, but $\\frac 1 3$ works and gives better convergence speed and execution time than $\\frac 1 4$. Some tuning around TC#87 shows that the value of $0.33744$ is about the max value being accepted. For further calculation speedup we represent it as a binary fraction $\\frac {44229} {2^{17}} \\approx 0.337440491$. However TC#87 operates relatively small values (class populations less than 1000), while we are interested in faster convergence for larger values in the first place. So we could put $\\frac 1 2$ or $\\frac 5 8$, or even $\\frac {21} {32}$ for larger populations.\n\nWe have also tried to exclude the square inequality solution, and the outcome it turned out to be even faster.\n\nThese manipulations don\'t affect the overall time complexity, but significantly reduce its constant multiplier.\n\n## Micro-Optimisations\n\nC++ offers a great level of control to the developer. E.g. if we have a vector of vectors (typically 24-byte values consisting of 3 pointers each: begin, end of size, end of capacity), we can reinterpret it as a vector of integers. This is what we do in the code example below, build a fully in-place $O(1)$ space solution.\n\nHowever once we have spoiled the pointer data, we should prevent the calling code from calling destructors on the small vectors. So we clear the large vector via an integer vector reference on return. This produces a leaky code (small vectors\' storage is not released), which does not matter for a one-off run of a student program, but in a production app the original vectors should be cleared and their allocation reset to 0 before writing over their pointer data. We skip that step to save processing time.\n\n# Complexity\n- Time complexity: $O(n + min(m \\times log(s), s) \\times log(m))$\nwhere $n$ is the number of classes, and $s$ is the number of extra  students\n\n- Space complexity: $O(1)$\n\n# Measurements\n\nThe indicators are clickable, referring to the relevant submission.\n\n|Language|Algorithm|Time, ms|Beating|Memory, Mb|Beating|\n|-|-|-|-|-|-|\n|C++|Square ineq + $\\frac 1 4$ share|[91](https://leetcode.com/problems/maximum-average-pass-ratio/submissions/1479497122)|100%|[83.74](https://leetcode.com/problems/maximum-average-pass-ratio/submissions/1479497122)|100%|\n|C++|Square ineq + $\\frac 1 3$ share|[84](https://leetcode.com/problems/maximum-average-pass-ratio/submissions/1480148450)|100%|[83.80](https://leetcode.com/problems/maximum-average-pass-ratio/submissions/1480148450)|100%|\n|C++|$\\frac {44229} {2^{17}}$ vs $\\frac 1 2$ share|[69](https://leetcode.com/problems/maximum-average-pass-ratio/submissions/1480194625)|100%|[83.95](https://leetcode.com/problems/maximum-average-pass-ratio/submissions/1480194625)|100%|\n|C++|$\\frac {44229} {2^{17}}$ vs $\\frac {21} {32}$ share|[64](https://leetcode.com/problems/maximum-average-pass-ratio/submissions/1480210858)|100%|[83.75](https://leetcode.com/problems/maximum-average-pass-ratio/submissions/1480210858)|100%|\n\n# Code\n```cpp [C++ 91 ms]\nclass Solution {\nprivate:\n    static constexpr uint8_t VSH = 17;\n    static constexpr uint VMASK = (1u << VSH) - 1u;\n\npublic:\n    static double maxAverageRatio(vector<vector<int>>& classes, uint s) {\n        const uint n = classes.size();\n        if (n == 1) {\n            const auto &x = classes.front();\n            const uint p = x[0], t = x[1];\n            return (double)(p + s) / (t + s);\n        }\n        vector<uint64_t> &qvec = (vector<uint64_t>&)classes;\n        uint64_t *const qdata = qvec.data();\n        const auto cmp = [](const uint64_t a, const uint64_t b) {\n            const uint t = a >> VSH, p = a & VMASK, u = b >> VSH, v = b & VMASK;\n            return (t - p) * (u + 1ull) * u < (u - v) * (t + 1ull) * t;\n        };\n        uint m = 0;\n        double res = 0.;\n        for (const auto &x : classes) {\n            const uint p = x[0], t = x[1];\n            if (p != t)\n                qdata[m++] = (uint64_t(t) << VSH) + p;\n            res += (double)p / t;\n        }\n        switch (m) {\n            case 0:\n                qvec.clear();\n                return 1.;\n            case 1: {\n                const auto x = *qdata;\n                qvec.clear();\n                const uint p = x & VMASK, t = x >> VSH;\n                return (double)(p + s) / (t + s);\n            }\n        }\n        make_heap(qdata, qdata + m, cmp);\n        while (true) {\n            const uint64_t x = *qdata;\n            const uint t = x >> VSH, p = x & VMASK, l = t - p;\n            pop_heap(qdata, qdata + m--, cmp);\n            const uint64_t y = *qdata;\n            const uint u = y >> VSH, v = y & VMASK;\n            const uint z = floor(sqrt((t - p) * (u + 1ull) * u / double(u - v) + 0.75)),\n                       f = (s + m) / (m + 1u) / 4u,\n                       d = max(z, t + f + !f) - t,\n                       e = min(d, s);\n            res += (p + e) / double(t + e) - p / (double) t;\n            s -= e;\n            if (!s) break;\n            qdata[m++] = x + e + (uint64_t(e) << VSH);\n            push_heap(qdata, qdata + m, cmp);\n        }\n        qvec.clear();\n        return res / n;\n    }\n};\n```\n``` cpp [C++ 84 ms]\nclass Solution {\nprivate:\n    static constexpr uint8_t VSH = 17;\n    static constexpr uint VMASK = (1u << VSH) - 1u;\n\npublic:\n    static double maxAverageRatio(vector<vector<int>>& classes, uint s) {\n        const uint n = classes.size();\n        if (n == 1) {\n            const auto &x = classes.front();\n            const uint p = x[0], t = x[1];\n            return (double)(p + s) / (t + s);\n        }\n        vector<uint64_t> &qvec = (vector<uint64_t>&)classes;\n        uint64_t *const qdata = qvec.data();\n        const auto cmp = [](const uint64_t a, const uint64_t b) {\n            const uint t = a >> VSH, p = a & VMASK, u = b >> VSH, v = b & VMASK;\n            return (t - p) * (u + 1ull) * u < (u - v) * (t + 1ull) * t;\n        };\n        uint m = 0;\n        double res = 0.;\n        for (const auto &x : classes) {\n            const uint p = x[0], t = x[1];\n            if (p != t)\n                qdata[m++] = (uint64_t(t) << VSH) + p;\n            res += (double)p / t;\n        }\n        switch (m) {\n            case 0:\n                qvec.clear();\n                return 1.;\n            case 1: {\n                const auto x = *qdata;\n                qvec.clear();\n                const uint p = x & VMASK, t = x >> VSH;\n                return (double)(p + s) / (t + s);\n            }\n        }\n        make_heap(qdata, qdata + m, cmp);\n        while (true) {\n            const uint64_t x = *qdata;\n            const uint t = x >> VSH, p = x & VMASK, l = t - p;\n            pop_heap(qdata, qdata + m--, cmp);\n            const uint64_t y = *qdata;\n            const uint u = y >> VSH, v = y & VMASK;\n            const uint z = floor(sqrt((t - p) * (u + 1ull) * u / double(u - v) + 0.75)),\n                       f = (s + m) / (m + 1u) / 3u,\n                       d = max(z, t + f + !f) - t,\n                       e = min(d, s);\n            res += (p + e) / double(t + e) - p / (double) t;\n            s -= e;\n            if (!s) break;\n            qdata[m++] = x + e + (uint64_t(e) << VSH);\n            push_heap(qdata, qdata + m, cmp);\n        }\n        qvec.clear();\n        return res / n;\n    }\n};\n```\n``` cpp [C++ 69 ms]\nclass Solution {\nprivate:\n    static constexpr uint8_t VSH = 17;\n    static constexpr uint VMASK = (1u << VSH) - 1u;\n\npublic:\n    static double maxAverageRatio(vector<vector<int>>& classes, uint s) {\n        const uint n = classes.size();\n        if (n == 1) {\n            const auto &x = classes.front();\n            const uint p = x[0], t = x[1];\n            return (double)(p + s) / (t + s);\n        }\n        vector<uint64_t> &qvec = (vector<uint64_t>&)classes;\n        uint64_t *const qdata = qvec.data();\n        const auto cmp = [](const uint64_t a, const uint64_t b) {\n            const uint t = a >> VSH, p = a & VMASK, u = b >> VSH, v = b & VMASK;\n            return (t - p) * (u + 1ull) * u < (u - v) * (t + 1ull) * t;\n        };\n        uint m = 0;\n        double res = 0.;\n        bool bigt = false;\n        for (const auto &x : classes) {\n            const uint p = x[0], t = x[1];\n            if (p != t) {\n                qdata[m++] = (uint64_t(t) << VSH) + p;\n                bigt |= t > 1000;\n            }\n            res += (double)p / t;\n        }\n        switch (m) {\n            case 0:\n                qvec.clear();\n                return 1.;\n            case 1: {\n                const auto x = *qdata;\n                qvec.clear();\n                const uint p = x & VMASK, t = x >> VSH;\n                return (double)(p + s) / (t + s);\n            }\n        }\n        const uint fmul = bigt ? 1u : 44229u;\n        const uint8_t fsh = bigt ? 1 : 17;\n        make_heap(qdata, qdata + m, cmp);\n        while (true) {\n            const uint64_t x = *qdata;\n            const uint t = x >> VSH, p = x & VMASK, l = t - p;\n            pop_heap(qdata, qdata + m--, cmp);\n            const uint64_t y = *qdata;\n            const uint u = y >> VSH, v = y & VMASK;\n            const uint f = (s + m) / (m + 1u) * fmul >> fsh,\n                       e = min(f + !f, s);\n            res += (p + e) / double(t + e) - p / (double) t;\n            s -= e;\n            if (!s) break;\n            qdata[m++] = x + e + (uint64_t(e) << VSH);\n            push_heap(qdata, qdata + m, cmp);\n        }\n        qvec.clear();\n        return res / n;\n    }\n};\n```\n``` cpp [C++ 64 ms]\nclass Solution {\nprivate:\n    static constexpr uint8_t VSH = 17;\n    static constexpr uint VMASK = (1u << VSH) - 1u;\n\npublic:\n    static double maxAverageRatio(vector<vector<int>>& classes, uint s) {\n        const uint n = classes.size();\n        if (n == 1) {\n            const auto &x = classes.front();\n            const uint p = x[0], t = x[1];\n            return (double)(p + s) / (t + s);\n        }\n        vector<uint64_t> &qvec = (vector<uint64_t>&)classes;\n        uint64_t *const qdata = qvec.data();\n        const auto cmp = [](const uint64_t a, const uint64_t b) {\n            const uint t = a >> VSH, p = a & VMASK, u = b >> VSH, v = b & VMASK;\n            return (t - p) * (u + 1ull) * u < (u - v) * (t + 1ull) * t;\n        };\n        uint m = 0;\n        double res = 0.;\n        bool bigt = false;\n        for (const auto &x : classes) {\n            const uint p = x[0], t = x[1];\n            if (p != t) {\n                qdata[m++] = (uint64_t(t) << VSH) + p;\n                bigt |= t > 1000;\n            }\n            res += (double)p / t;\n        }\n        switch (m) {\n            case 0:\n                qvec.clear();\n                return 1.;\n            case 1: {\n                const auto x = *qdata;\n                qvec.clear();\n                const uint p = x & VMASK, t = x >> VSH;\n                return (double)(p + s) / (t + s);\n            }\n        }\n        const uint fmul = bigt ? 21u : 44229u;\n        const uint8_t fsh = bigt ? 5 : 17;\n        make_heap(qdata, qdata + m, cmp);\n        while (true) {\n            const uint64_t x = *qdata;\n            const uint t = x >> VSH, p = x & VMASK, l = t - p;\n            pop_heap(qdata, qdata + m--, cmp);\n            const uint64_t y = *qdata;\n            const uint u = y >> VSH, v = y & VMASK;\n            const uint f = (s + m) / (m + 1u) * fmul >> fsh,\n                       e = min(f + !f, s);\n            res += (p + e) / double(t + e) - p / (double) t;\n            s -= e;\n            if (!s) break;\n            qdata[m++] = x + e + (uint64_t(e) << VSH);\n            push_heap(qdata, qdata + m, cmp);\n        }\n        qvec.clear();\n        return res / n;\n    }\n};\n```
['Array', 'Math', 'Greedy', 'Heap (Priority Queue)', 'C++']