There is a survey that consists of n questions where each question’s 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 ith student (0-indexed). 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 jth mentor (0-indexed).
Each student will be assigned to one mentor, and each mentor will have
one student assigned to them. The compatibility score of a student-mentor pair is the number of answers that are the same for both the student and the mentor.
For example, if the student’s answers were [1, _0_ , _1_] and the mentor’s answers were [0, _0_ , _1_], then their compatibility score is 2 because only the second and the third answers are the same.
You are tasked with finding the optimal student-mentor pairings to
maximize thesum of the compatibility scores.
Given students and mentors, return themaximum compatibility score sum that can be achieved.
Input: students =[[1,1,0],[1,0,1],[0,0,1]], mentors =[[1,0,0],[0,0,1],[1,1,0]]Output: 8Explanation: We assign students to mentors in the following way:- student 0 to mentor 2with a compatibility score of 3.- student 1 to mentor 0with a compatibility score of 2.- student 2 to mentor 1with a compatibility score of 3.The compatibility score sum is3+2+3=8.
Since the number of students/mentors is small (≤ 8), we can try all possible assignments efficiently using bitmasking. For each possible assignment of students to mentors, we calculate the total compatibility score and keep the maximum.
classSolution {
funmaxCompatibilitySum(students: Array<IntArray>, mentors: Array<IntArray>): Int {
val m = students.size
val n = students[0].size
val score = Array(m) { IntArray(m) }
for (i in0 until m)
for (j in0 until m)
for (k in0 until n)
if (students[i][k] == mentors[j][k]) score[i][j]++val dp = IntArray(1 shl m)
for (mask in0 until (1 shl m)) {
val cnt = mask.countOneBits()
if (cnt >= m) continuefor (j in0 until m) {
if ((mask and (1 shl j)) ==0) {
dp[mask or (1 shl j)] = maxOf(dp[mask or (1 shl j)], dp[mask] + score[cnt][j])
}
}
}
return dp[(1 shl m) - 1]
}
}
1
2
3
4
5
6
7
8
9
10
11
12
classSolution:
defmaxCompatibilitySum(self, students: list[list[int]], mentors: list[list[int]]) -> int:
m, n = len(students), len(students[0])
score = [[sum(s == t for s, t in zip(students[i], mentors[j])) for j in range(m)] for i in range(m)]
dp = [0] * (1<< m)
for mask in range(1<< m):
cnt = bin(mask).count('1')
if cnt >= m: continuefor j in range(m):
ifnot (mask & (1<< j)):
dp[mask | (1<< j)] = max(dp[mask | (1<< j)], dp[mask] + score[cnt][j])
return dp[(1<< m) -1]
impl Solution {
pubfnmax_compatibility_sum(students: Vec<Vec<i32>>, mentors: Vec<Vec<i32>>) -> i32 {
let m = students.len();
let n = students[0].len();
letmut score =vec![vec![0; m]; m];
for i in0..m {
for j in0..m {
for k in0..n {
if students[i][k] == mentors[j][k] {
score[i][j] +=1;
}
}
}
}
letmut dp =vec![0; 1<< m];
for mask in0..(1<< m) {
let cnt = mask.count_ones() asusize;
if cnt >= m { continue; }
for j in0..m {
if (mask & (1<< j)) ==0 {
let next = mask | (1<< j);
dp[next] = dp[next].max(dp[mask] + score[cnt][j]);
}
}
}
dp[(1<< m) -1]
}
}
⏰ Time complexity: O(m^2 * 2^m), where m is the number of students/mentors. We process each bitmask (2^m), and for each, try all m mentors, and precompute m^2 scores.
🧺 Space complexity: O(m^2 + 2^m), for the score matrix and DP array.