##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1947.html

# 1947. Maximum Compatibility Score Sum

Medium

## Description

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 i-th 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 j-th 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 the sum of the compatibility scores.

Given students and mentors, return the maximum compatibility score sum that can be achieved.

Example 1:

Input: students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]]

Output: 8

Explanation: We assign students to mentors in the following way:

• student 0 to mentor 2 with a compatibility score of 3.
• student 1 to mentor 0 with a compatibility score of 2.
• student 2 to mentor 1 with a compatibility score of 3.

The compatibility score sum is 3 + 2 + 3 = 8.

Example 2:

Input: students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]]

Output: 0

Explanation: The compatibility score of any student-mentor pair is 0.

Constraints:

• m == students.length == mentors.length
• n == students[i].length == mentors[j].length
• 1 <= m, n <= 8
• students[i][k] is either 0 or 1.
• mentors[j][k] is either 0 or 1.

## Solution

Since both m and n do not exceed 8, each row in students and mentors can be considered as a binary representation and can be converted into an integer that does not exceed 255. After converting into integers, calculate the permutations of the m rows. For each permutation, calculate the compatibility score sum using bitwise operation, and return the maximum compatibility score sum.

• class Solution {
public int maxCompatibilitySum(int[][] students, int[][] mentors) {
int m = students.length, n = students.length;
int[] studentsNums = new int[m];
int[] mentorsNums = new int[m];
for (int i = 0; i < m; i++) {
studentsNums[i] = convertToNum(students[i]);
mentorsNums[i] = convertToNum(mentors[i]);
}
int[] nums = new int[m];
for (int i = 0; i < m; i++)
nums[i] = i;
int maxSum = 0;
List<List<Integer>> permutations = permute(nums);
for (List<Integer> permutation : permutations) {
int sum = 0;
for (int i = 0; i < m; i++)
sum += n - Integer.bitCount(studentsNums[i] ^ mentorsNums[permutation.get(i)]);
maxSum = Math.max(maxSum, sum);
}
return maxSum;
}

public int convertToNum(int[] arr) {
int num = 0;
int length = arr.length;
for (int i = 0; i < length; i++)
num += arr[i] << i;
return num;
}

public List<List<Integer>> permute(int[] nums) {
int length = nums.length;
List<List<Integer>> permutations = new ArrayList<List<Integer>>();
List<Integer> permutation = new ArrayList<Integer>();
for (int i = 0; i < length; i++)
backtrack(length, permutations, 0, permutation);
return permutations;
}

public void backtrack(int length, List<List<Integer>> permutations, int start, List<Integer> permutation) {
if (start == length)
else {
for (int i = start; i < length; i++) {
Collections.swap(permutation, start, i);
backtrack(length, permutations, start + 1, permutation);
Collections.swap(permutation, start, i);
}
}
}
}

############

class Solution {
private int[][] g;
private boolean[] vis;
private int m;
private int ans;

public int maxCompatibilitySum(int[][] students, int[][] mentors) {
m = students.length;
g = new int[m][m];
vis = new boolean[m];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = 0; k < students[i].length; ++k) {
g[i][j] += students[i][k] == mentors[j][k] ? 1 : 0;
}
}
}
dfs(0, 0);
return ans;
}

private void dfs(int i, int t) {
if (i == m) {
ans = Math.max(ans, t);
return;
}
for (int j = 0; j < m; ++j) {
if (!vis[j]) {
vis[j] = true;
dfs(i + 1, t + g[i][j]);
vis[j] = false;
}
}
}
}

• class Solution:
def maxCompatibilitySum(
self, students: List[List[int]], mentors: List[List[int]]
) -> int:
def dfs(i, t):
if i == m:
nonlocal ans
ans = max(ans, t)
return
for j in range(m):
if not vis[j]:
vis[j] = True
dfs(i + 1, t + g[i][j])
vis[j] = False

m = len(students)
g = [ * m for _ in range(m)]
for i in range(m):
for j in range(m):
g[i][j] = sum(a == b for a, b in zip(students[i], mentors[j]))
vis = [False] * m
ans = 0
dfs(0, 0)
return ans

############

# 1947. Maximum Compatibility Score Sum
# https://leetcode.com/problems/maximum-compatibility-score-sum/

class Solution:
def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
n = len(students)

def dfs(i, used, score):
if i == n: return score

res = float(-inf)

for j, mentor in enumerate(mentors):
if j in used: continue

ss = sum(int(a == b) for a, b in zip(students[i], mentor))
score += ss

res = max(res, dfs(i + 1, used, score))

used.remove(j)
score -= ss

return res

return dfs(0, set(), 0)


• class Solution {
public:
int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
int m = students.size();
int n = students.size();
int g[m][m];
memset(g, 0, sizeof g);
bool vis[m];
memset(vis, 0, sizeof vis);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = 0; k < n; ++k) {
g[i][j] += students[i][k] == mentors[j][k];
}
}
}
int ans = 0;
function<void(int, int)> dfs = [&](int i, int t) {
if (i == m) {
ans = max(ans, t);
return;
}
for (int j = 0; j < m; ++j) {
if (!vis[j]) {
vis[j] = true;
dfs(i + 1, t + g[i][j]);
vis[j] = false;
}
}
};
dfs(0, 0);
return ans;
}
};

• func maxCompatibilitySum(students [][]int, mentors [][]int) (ans int) {
m, n := len(students), len(students)
g := make([][]int, m)
vis := make([]bool, m)
for i := range g {
g[i] = make([]int, m)
for j := range g {
for k := 0; k < n; k++ {
if students[i][k] == mentors[j][k] {
g[i][j]++
}
}
}
}
var dfs func(int, int)
dfs = func(i, t int) {
if i == m {
ans = max(ans, t)
return
}
for j := 0; j < m; j++ {
if !vis[j] {
vis[j] = true
dfs(i+1, t+g[i][j])
vis[j] = false
}
}
}
dfs(0, 0)
return
}

func max(a, b int) int {
if a > b {
return a
}
return b
}