aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-08 17:19:49 -0600
committerJack Sangdahl <[email protected]>2024-09-08 17:19:49 -0600
commite4a7cbda66d8490df756a6170b1bf47afc428419 (patch)
treeeef471c731d7a3c4ea945069f400423b6657f481
parent06c62754e65808149019088ce0ccf4808748f5ef (diff)
downloadleetcode-e4a7cbda66d8490df756a6170b1bf47afc428419.tar.gz
leetcode-e4a7cbda66d8490df756a6170b1bf47afc428419.zip
1947. maximum compatibility score sum
-rw-r--r--max_compatibility_score_sum.c75
-rw-r--r--max_compatibility_score_sum.py53
2 files changed, 128 insertions, 0 deletions
diff --git a/max_compatibility_score_sum.c b/max_compatibility_score_sum.c
new file mode 100644
index 0000000..689e2c2
--- /dev/null
+++ b/max_compatibility_score_sum.c
@@ -0,0 +1,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
+}
diff --git a/max_compatibility_score_sum.py b/max_compatibility_score_sum.py
new file mode 100644
index 0000000..580a176
--- /dev/null
+++ b/max_compatibility_score_sum.py
@@ -0,0 +1,53 @@
+# 1947. Maximum Compatibility Score Sum
+
+"""
+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
+"""
+
+
+class Solution(object):
+ def maxCompatibilitySum(self, students, mentors):
+ """
+ :type students: List[List[int]]
+ :type mentors: List[List[int]]
+ :rtype: int
+ """
+ m = len(students)
+ score = [[0] * m for _ in range(m)]
+ for i in range(m):
+ for j in range(m):
+ score[i][j] = sum(x == y for x, y in zip(students[i], mentors[j]))
+
+ def dp(mask, j):
+ res = 0
+ for i in range(m):
+ if not mask & (1 << i):
+ res = max(res, dp(mask ^ (1 << i), j - 1) + score[i][j])
+ return res
+
+ return dp(1 << m, m - 1)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.maxCompatibilitySum(
+ students=[[1, 1, 0], [1, 0, 1], [0, 0, 1]],
+ mentors=[[1, 0, 0], [0, 0, 1], [1, 1, 0]],
+ )
+ )
+ print(
+ obj.maxCompatibilitySum(
+ students=[[0, 0], [0, 0], [0, 0]], mentors=[[1, 1], [1, 1], [1, 1]]
+ )
+ )