aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--maximum_average_pass_ratio.c130
-rw-r--r--maximum_average_pass_ratio.py39
2 files changed, 169 insertions, 0 deletions
diff --git a/maximum_average_pass_ratio.c b/maximum_average_pass_ratio.c
new file mode 100644
index 0000000..5a524bc
--- /dev/null
+++ b/maximum_average_pass_ratio.c
@@ -0,0 +1,130 @@
+// 1792. Maximum Average Pass Ratio
+#include "leetcode.h"
+
+/*
+ * there is a school that has classes of students and each class will be having
+ * a final exam. you are given a 2d integer array 'classes' where 'classes[i] =
+ * [pass_i, total_i]'. you know beforehand that in the i'th there are 'total_i'
+ * students, but only 'pass_i' students that will pass the exam. you are also
+ * given in integer 'extraStudents'. there are another 'extraStudents' brilliant
+ * students that are guaranteed to pass the exam of any class. return the
+ * maximum possible average pass ratio after assigning the 'extraStudents'
+ * students. answers within 10^-5 of the actual answer will be accepted.
+ */
+
+struct data {
+ double gain_rate;
+ int pass;
+ int total;
+};
+
+struct heap {
+ struct data *pq;
+ int size;
+ int capacity;
+};
+
+struct heap *heap_init(int n) {
+ struct heap *obj = (struct heap *)malloc(sizeof(struct heap));
+ obj->capacity = n;
+ obj->size = 0;
+ obj->pq = (struct data *)malloc(n * sizeof(struct data));
+ return obj;
+}
+
+void swap(struct data *a, struct data *b) {
+ struct data tmp = *a;
+ *a = *b;
+ *b = tmp;
+}
+
+void heap_up(struct heap *obj, int i) {
+ while (i > 0) {
+ int parent = ((i - 1) >> 1);
+ if (obj->pq[i].gain_rate > obj->pq[parent].gain_rate) {
+ swap(&(obj->pq[i]), &(obj->pq[parent]));
+ i = parent;
+ continue;
+ }
+ break;
+ }
+}
+
+void heap_down(struct heap *obj, int i) {
+ int largest = i, size = obj->size;
+ int left = ((i << 1) + 1), right = ((i << 1) + 2);
+ if (left < size && obj->pq[largest].gain_rate < obj->pq[left].gain_rate)
+ largest = left;
+ if (right < size && obj->pq[largest].gain_rate < obj->pq[right].gain_rate)
+ largest = right;
+ if (largest != i) {
+ swap(&(obj->pq[i]), &(obj->pq[largest]));
+ heap_down(obj, largest);
+ }
+}
+
+void heap_push(struct heap *obj, struct data new) {
+ if (obj->size == obj->capacity) {
+ obj->capacity <<= 1;
+ obj->pq =
+ (struct data *)realloc(obj->pq, obj->capacity * sizeof(struct data));
+ }
+ obj->pq[obj->size] = new;
+ heap_up(obj, obj->size);
+ ++obj->size;
+}
+
+struct data heap_pop(struct heap *obj) {
+ struct data top = obj->pq[0];
+ obj->pq[0] = obj->pq[--(obj->size)];
+ heap_down(obj, 0);
+ return top;
+}
+
+void heap_free(struct heap *obj) {
+ free(obj->pq);
+ free(obj);
+}
+
+static inline double gain(int pass, int total) {
+ return (double)(pass + 1) / (total + 1) - (double)pass / total;
+}
+
+double maxAverageRatio(int **classes, int classesSize, int *classesColSize,
+ int extraStudents) {
+ double ans = 0.0;
+ struct heap *obj = heap_init(classesSize);
+ for (int i = 0; i < classesSize; ++i) {
+ int pass = classes[i][0], total = classes[i][1];
+ ans += (double)pass / total;
+ struct data item = {gain(pass, total), pass, total};
+ heap_push(obj, item);
+ }
+ for (int i = 0; i < extraStudents; ++i) {
+ struct data top = heap_pop(obj);
+ int pass = top.pass, total = top.total;
+ ans -= (double)pass / total;
+ ++pass;
+ ++total;
+ ans += (double)pass / total;
+ struct data item = {gain(pass, total), pass, total};
+ heap_push(obj, item);
+ }
+ heap_free(obj);
+ return ans;
+}
+
+int main() {
+ int c1i[3][2] = {{1, 2}, {3, 5}, {2, 2}},
+ c2i[4][2] = {{2, 4}, {3, 9}, {4, 5}, {2, 10}};
+ struct two_d_arr *c1 =
+ two_d_arr_init(ARRAY_SIZE(c1i), ARRAY_SIZE(c1i[0]), c1i);
+ struct two_d_arr *c2 =
+ two_d_arr_init(ARRAY_SIZE(c2i), ARRAY_SIZE(c2i[0]), c2i);
+ printf("%f\n", maxAverageRatio(c1->arr, c1->row_size, c1->col_size,
+ 2)); // expect: 0.78333
+ printf("%f\n", maxAverageRatio(c2->arr, c2->row_size, c2->col_size,
+ 4)); // expect: 0.53485
+ two_d_arr_free(c1);
+ two_d_arr_free(c2);
+}
diff --git a/maximum_average_pass_ratio.py b/maximum_average_pass_ratio.py
new file mode 100644
index 0000000..41aa9fa
--- /dev/null
+++ b/maximum_average_pass_ratio.py
@@ -0,0 +1,39 @@
+# 1792. Maximum Average Pass Ratio
+import heapq
+
+"""
+there is a school that has classes of students and each class will be having
+a final exam. you are given a 2d integer array 'classes' where 'classes[i] =
+[pass_i, total_i]'. you know beforehand that in the i'th there are 'total_i'
+students, but only 'pass_i' students that will pass the exam. you are also
+given in integer 'extraStudents'. there are another 'extraStudents' brilliant
+students that are guaranteed to pass the exam of any class. return the
+maximum possible average pass ratio after assigning the 'extraStudents'
+students. answers within 10^-5 of the actual answer will be accepted.
+"""
+
+
+class Solution(object):
+ def maxAverageRatio(self, classes, extraStudents):
+ """
+ :type classes: List[List[int]]
+ :type extraStudents: int
+ :rtype: float
+ """
+ h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]
+ heapq.heapify(h)
+ while extraStudents:
+ v, a, b = heapq.heappop(h)
+ a += 1
+ b += 1
+ heapq.heappush(h, (-(a + 1) / (b + 1) + a / b, a, b))
+ extraStudents -= 1
+ return sum(a / b for v, a, b in h) / len(h)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxAverageRatio(classes=[[1, 2], [3, 5], [2, 2]], extraStudents=2))
+ print(
+ obj.maxAverageRatio(classes=[[2, 4], [3, 9], [4, 5], [2, 10]], extraStudents=4)
+ )