Greedy Proof
Hi Guys, this is kinda my first post on leetcode, applogies for bad grammer and formatting. Also it\'s been ages since I\'ve written a mathematical proof, so it
Hi Guys, this is kinda my first post on leetcode, applogies for bad grammer and formatting. Also it\'s been ages since I\'ve written a mathematical proof, so it might not be very accurate but hopefully it should be intutive. Hope this can help one of you. \n\n### Greedy Algorithm\nIteratively each brilient student is added to the class with the maximum delta pass ratio and pass ratio of this class is updated. \n\nFor a class `class_i` with `pass_i` students passing and `total_i` being the total number of students. The pass ratio is `pass_i/total_i` When a brilliant student is added, the pass ratio changes to `(pass_i+1)/(total_i+1)`. Therefore, the pass ratio increased by `(total_i-pass_i)/(pass_i*(pass_i+1))`  which we call as delta pass ratio.\n\n#### Lemma 1.  The delta pass ratio decreases as we keep on adding new brilliant student \nIn the above equation of the pass ratio, the Numerator is constant as we keep adding brilliant students, but the Denominator keeps decreasing. Hence, the benefits of adding a new brilliant student keeps decreasing for the `class_i` .\n\n\n#### Algorithm Proof - Proof by contradiction\n- Say at step 1 `class_i` has the highest delta pass ratio.\n- Now if we are picking `class_i` at step 1, then we are good.\n- If we are not picking `class_i` at step\n\t- If we pick `class_i` eventually at `step_x`, then simply swap the steps `step_1` and `step_x`. \n\t- If `class_i` is never picked up, \n\t\t- let `class_k` be the  class where last student `s_n` was added\n\t\t- delta pass ratio of `class_k` at step `s_(n-1)` will be less than delta pass ratio for `class_i` \n\t\t\t- since `class_i` has the highest delta pass ratio at `step_0` itself and delta pass ratio decreases with more steps \n\t\t- Hence this is a contradtion, as by changing `step_n` by choose `class_i` instead of `class_k`, the total ratio sum will increase. \n\n\n### Python code for reference \n\n``` python\nclass Solution:\n    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n        def delta(p, t):\n            return -(t-p)/(t*(t+1))\n        \n        ans = 0\n        heap = []\n        for class_i in classes:\n            heap.append((delta(*class_i), class_i))\n            ans += class_i[0]/class_i[1]\n        \n        heapq.heapify(heap)\n        for i in range(extraStudents):\n            delta_i, class_i = heapq.heappop(heap)\n            ans -= delta_i\n            class_i[0]+=1\n            class_i[1]+=1\n            heapq.heappush(heap, (delta(*class_i), class_i))\n        return ans/len(classes)\n```\n
['Greedy']