Jonas Notes

Maximum Average Pass Ratio

2 min read

Problem

Maximum Average Pass Ratio

Approach

So we want to find the maximum average pass ratio. We can insert the brilliant students into the class to increase its pass rate. So, to increase the maximum average pass rate, should we try to increase the class with the lowest past rate? or the highest?

Ok, turns out it’s the same and doesn’t matter. But what matters here is when we do pass students / total students, we want to maximise the difference when we add one to the numerator and denominator. So I would think to maximise this difference, the total students must be the least. Hmmm… but when running this on an example given, its not the case. And I can’t seem to find an example whereby that is not true. I think I will code out the naive solution and print out the answer for the second example given.

Wrote out the naive solution pretty easily, and found out that there does not seem to be a discernable pattern that the naive solution chooses the fractions. Did some math on my IPad, and realised that we just need to maximise this formula . Think with this, we can create a max-heap and the solution will be pretty easy.

Was what I thought, then I realised I screwed up the formula… It should be instead. It’s pretty simple algebra, and I still messed it up.

Complexity

  • Time:
  • Space:

Code

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        # we need to maximise (d-n)/d(d+1)
        # construct the max heap
        # heapify in python is a min heap, so we need to -1 *
        heapq = [(-1 * (d-n)/(d*(d+1)), i) for i,(n,d) in enumerate(classes)]
        heapify(heapq)
 
        for _ in range(extraStudents):
            _, i = heappop(heapq)
            n,d = classes[i]
            classes[i] = [n+1,d+1]
            heappush(heapq, (-1 * (d-n)/((d+1)*(d+2)), i))
        
        fracs = [n/d for n,d in classes]
        return sum(fracs) / len(fracs)

Backlinks