aboutsummaryrefslogtreecommitdiff
path: root/maximum_average_pass_ratio.c
blob: 5a524bcd525f3b9e5b8879daca8fe81b7506f796 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
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);
}