Problem Description

The Maximum Compatibility Score Sum problem is as follows:

You are given two integer matrices students and mentors, both of size m x n. Each row represents a student or mentor, and each column represents an answer to a question (with values 0 or 1).

The compatibility score between a student and a mentor is the number of answers where their responses match (i.e., for each column, if students[i][j] == mentors[k][j], it counts as 1).

Your task is to pair each student with a different mentor (one-to-one matching, no reuse), so that the sum of compatibility scores for all pairs is maximized.

Constraints:

• Each student must be paired with exactly one mentor, and vice versa.
• You cannot reuse a mentor for more than one student.
• There is only one valid solution for each input.
• Both matrices have the same number of rows m (students and mentors).

Thought Process

Initially, it may seem that you could greedily pair each student with the mentor with whom they have the highest compatibility score. However, this doesn't guarantee a global maximum because pairing one student greedily could block another student from their best possible match.

The problem is essentially about finding the best way to assign students to mentors so that the total score is maximized. This is a classic example of the assignment problem or maximum weight matching in bipartite graphs.

For small values of m (since m <= 8 in Leetcode's constraints), we can afford to check all possible assignments (i.e., all permutations of mentor assignments to students).

For larger instances, a more optimized approach like the Hungarian Algorithm would be necessary, but for this problem, enumeration with memoization (dynamic programming with bitmasking) is optimal and efficient.

Solution Approach

We use dynamic programming with bitmasking to efficiently explore all possible assignments without redundant work. Here's the step-by-step approach:

1. Precompute compatibility scores:
   • For each student and each mentor, calculate the number of matching answers. Store these values in a score matrix score[i][j].
2. Recursive DP with memoization:
   • Let dp(mask) represent the maximum compatibility sum achievable by assigning students to the set of mentors represented by mask (a bitmask where each bit indicates if a mentor is already used).
   • At each step, pick the next student (based on the number of set bits in mask), and try assigning them to any unused mentor. For each possible assignment, update the mask and recurse.
   • Memoize the results to avoid recomputation.
3. Base Case:
   • If all mentors are assigned (mask has all bits set), return 0.
4. Return the result:
   • The answer is dp(0) (no mentors assigned yet).

This approach works efficiently due to the small size of m, since there are at most 2^m possible mentor assignment states.

Example Walkthrough

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

Step 1: Compute Compatibility Scores

• Student 0 vs Mentor 0: [1,1,0] vs [1,0,0] → matches at positions 0 and 2 ⇒ score = 2
• Student 0 vs Mentor 1: [1,1,0] vs [0,0,1] → matches nowhere ⇒ score = 0
• Student 0 vs Mentor 2: [1,1,0] vs [1,1,0] → matches at all positions ⇒ score = 3
• ... (similarly for others)

• Assign Student 0 to Mentor 2 (score 3), then recursively assign the next students to remaining mentors for the best total.
• Continue recursively, always picking the best available pairing at each step, and memoizing results.

• After evaluating all valid assignments, the DP will yield the maximum sum possible.

Time and Space Complexity

Brute-force Approach:

• Try all possible assignments (permutations) of mentors to students: O(m!) time.
• Space: O(1) (besides the input and score matrix).

• There are 2^m possible masks (mentor assignment states), and for each, at most m choices.
• Time: O(m^2 * 2^m) (since for each mask, we can try all m mentors, and for each student).
• Space: O(2^m) for the DP memoization table.

Summary

The Maximum Compatibility Score Sum problem is a classic assignment problem that can be solved efficiently with dynamic programming and bitmasking, thanks to the small input size. By precomputing pairwise scores and systematically considering all assignment possibilities, we ensure that the global maximum is found. The elegance of this approach lies in its use of bitmasking to compactly represent assignment states and memoization to avoid redundant computation.

This problem is a great example of how classic combinatorial optimization techniques can be applied when constraints are small, and how thinking beyond greedy or brute-force can lead to efficient, elegant solutions.

Code Implementation

from functools import lru_cache

class Solution:
    def maxCompatibilitySum(self, students, mentors):
        m, n = len(students), len(students[0])
        # Precompute compatibility scores
        score = [[sum(int(a == b) for a, b in zip(students[i], mentors[j])) for j in range(m)] for i in range(m)]
        
        @lru_cache(None)
        def dp(mask):
            i = bin(mask).count('1')  # Number of students assigned so far
            if i == m:
                return 0
            res = 0
            for j in range(m):
                if not (mask & (1 << j)):
                    res = max(res, score[i][j] + dp(mask | (1 << j)))
            return res
        return dp(0)
      

class Solution {
public:
    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
        int m = students.size(), n = students[0].size();
        vector<vector<int>> score(m, vector<int>(m, 0));
        // Precompute compatibility scores
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < m; ++j)
                for (int k = 0; k < n; ++k)
                    if (students[i][k] == mentors[j][k])
                        score[i][j]++;
        vector<int> dp(1 << m, -1);
        function<int(int)> dfs = [&](int mask) {
            int i = __builtin_popcount(mask);
            if (i == m) return 0;
            if (dp[mask] != -1) return dp[mask];
            int res = 0;
            for (int j = 0; j < m; ++j) {
                if (!(mask & (1 << j))) {
                    res = max(res, score[i][j] + dfs(mask | (1 << j)));
                }
            }
            return dp[mask] = res;
        };
        return dfs(0);
    }
};
      

class Solution {
    public int maxCompatibilitySum(int[][] students, int[][] mentors) {
        int m = students.length, n = students[0].length;
        int[][] score = new int[m][m];
        // Precompute compatibility scores
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < m; ++j)
                for (int k = 0; k < n; ++k)
                    if (students[i][k] == mentors[j][k])
                        score[i][j]++;
        int[] dp = new int[1 << m];
        Arrays.fill(dp, -1);
        return dfs(0, 0, m, score, dp);
    }
    private int dfs(int mask, int i, int m, int[][] score, int[] dp) {
        if (i == m) return 0;
        if (dp[mask] != -1) return dp[mask];
        int res = 0;
        for (int j = 0; j < m; ++j) {
            if ((mask & (1 << j)) == 0) {
                res = Math.max(res, score[i][j] + dfs(mask | (1 << j), i + 1, m, score, dp));
            }
        }
        dp[mask] = res;
        return res;
    }
}
      

var maxCompatibilitySum = function(students, mentors) {
    const m = students.length, n = students[0].length;
    const score = Array.from({length: m}, () => Array(m).fill(0));
    // Precompute compatibility scores
    for (let i = 0; i < m; ++i)
        for (let j = 0; j < m; ++j)
            for (let k = 0; k < n; ++k)
                if (students[i][k] === mentors[j][k])
                    score[i][j]++;
    const memo = new Map();
    function dp(mask) {
        if (memo.has(mask)) return memo.get(mask);
        const i = mask.toString(2).split('1').length - 1;
        if (i === m) return 0;
        let res = 0;
        for (let j = 0; j < m; ++j) {
            if ((mask & (1 << j)) === 0) {
                res = Math.max(res, score[i][j] + dp(mask | (1 << j)));
            }
        }
        memo.set(mask, res);
        return res;
    }
    return dp(0);
};