# 15.12.2024 [1792. Maximum Average Pass Ratio]

Arrange `passed` students to improve average score #medium #heap

15.12.2024

1792. Maximum Average Pass Ratio medium blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/833

Problem TLDR

Arrange passed students to improve average score #medium #heap

Intuition

Didn't solve without a hint. The hint: choose the most significant difference that can be made.

Approach

• in Rust we can't put f64 into a heap, so convert into the big i64 numbers

Complexity

• Time complexity: O((n+m)log(n))

• Space complexity: O(n)

Code

    fun maxAverageRatio(classes: Array<IntArray>, extraStudents: Int): Double {
        val scores = PriorityQueue<IntArray>(compareBy({
            it[0].toDouble() / it[1] - (it[0] + 1).toDouble() / (it[1] + 1) }))
        scores += classes
        for (s in 1..extraStudents) 
          scores += scores.poll().also { it[0]++; it[1]++ }
        return scores.sumOf { it[0].toDouble() / it[1] } / classes.size
    }

    pub fn max_average_ratio(classes: Vec<Vec<i32>>, extra_students: i32) -> f64 {
        let d = |p: i64, t: i64| -> (i64, i64, i64) {
            (((t - p) * 10_000_000) / (t * t + t), p, t) };
        let mut h = BinaryHeap::from_iter(classes.iter().map(|c| { 
          d(c[0] as i64, c[1] as i64) }));
        for _ in 0..extra_students {
            let (_, p, t) = h.pop().unwrap(); h.push(d(p + 1, t + 1)) }
        h.iter().map(|&(d, p, t)| 
                     p as f64 / t as f64).sum::<f64>() / classes.len() as f64
    }

    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        auto f = [&](double p, double t) { return (p + 1) / (t + 1) - p / t; };
        double r = 0; priority_queue<tuple<double, int, int>> q;
        for (auto x: classes) r += (double) x[0] / x[1],
            q.push({f(x[0], x[1]), x[0], x[1]});
        while (extraStudents--) {
            auto [d, p, t] = q.top(); q.pop();
            r += d; q.push({f(p + 1, t + 1), p + 1, t + 1});
        }
        return r / classes. Size();
    }