aboutsummaryrefslogtreecommitdiff
path: root/max_compatibility_score_sum.c
blob: 689e2c28b36eaf506db4b117f66cbf8ad4378366 (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
// 1947. Maximum Compatibility Score Sum
#include "leetcode.h"

/*
 * there is a survey that consists of 'n' questions where each questions answer
 * is either 0 (no) or 1 (yes). the survey was given to 'm' students numbered
 * from 0 to 'm - 1' and 'm' mentors numbered from 0 to 'm - 1'. the answers of
 * the students are represented by a 2d integer array 'students' where
 * 'students[i]' is an integer array that contains the answers of the i'th
 * student. the answers of the mentors are represented by a 2d integer array
 * 'mentors' where 'mentors[j]' is an integer array that contains the answers of
 * the j'th mentor. each student will be assigned to one mentor. the
 * compatibility score of a student-mentor pair is the number of answers that
 * are the same for both student and mentor. given 'students' and 'mentors',
 * return the maximum compatibility score sum that can be achieved
 */

static int max;

void swap(int *arr, int x, int y) {
  int tmp = arr[x];
  arr[x] = arr[y];
  arr[y] = tmp;
}

void per(int *stu, int size, int **score, int start_idx) {
  if (start_idx == size) {
    int total = 0;
    for (int i = 0; i < size; i++)
      total += score[stu[i]][i];
    if (total > max)
      max = total;
    return;
  }
  for (int i = start_idx; i < size; i++) {
    swap(stu, start_idx, i);
    per(stu, size, score, start_idx + 1);
    swap(stu, start_idx, i);
  }
}

int maxCompatibilitySum(int **students, int studentsSize, int *studentsColSize,
                        int **mentors, int mentorsSize, int *mentorsColSize) {
  max = 0;
  int **score = (int **)calloc(studentsSize, sizeof(int *));
  for (int s = 0; s < studentsSize; s++) {
    score[s] = (int *)calloc(mentorsSize, sizeof(int));
    for (int m = 0; m < mentorsSize; m++)
      for (int i = 0; i < *studentsColSize; i++)
        score[s][m] += (students[s][i] == mentors[m][i]);
  }
  int *stu = (int *)malloc(studentsSize * sizeof(int));
  for (int i = 0; i < studentsSize; i++)
    stu[i] = i;
  per(stu, studentsSize, score, 0);
  free(stu);
  for (int i = 0; i < studentsSize; i++)
    free(score[i]);
  free(score);
  return max;
}

int main() {
  int s1[3][3] = {{1, 1, 0}, {1, 0, 1}, {0, 0, 1}},
      m1[3][3] = {{1, 0, 0}, {0, 0, 1}, {1, 1, 0}}, scs1[] = {3, 3, 3},
      mcs1[] = {3, 3, 3};
  int s2[3][2] = {{0, 0}, {0, 0}, {0, 0}}, m2[3][2] = {{1, 1}, {1, 1}, {1, 1}},
      scs2[] = {2, 2, 2}, mcs2[] = {2, 2, 2};
  printf("%d\n",
         maxCompatibilitySum((int **)s1, ARRAY_SIZE(s1), scs1, (int **)m1,
                             ARRAY_SIZE(m1), mcs1)); // expect: 8
  printf("%d\n",
         maxCompatibilitySum((int **)s2, ARRAY_SIZE(s2), scs2, (int **)m2,
                             ARRAY_SIZE(m2), mcs2)); // expect: 0
}