#1947

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Compatibility Score Sum

Assign students to mentors to maximize total compatibility using state transition dynamic programming with bitmask optimization.

array dynamic programming backtracking bit manipulation bitmask

Problem Statement

You are given two 2D integer arrays, students and mentors, representing answers to a survey. Each answer is either 0 or 1. The survey has n questions, and both arrays have m rows representing students and mentors respectively.

Each student must be assigned to exactly one mentor, and each mentor to one student. The compatibility score of a student-mentor pair is the count of answers that match. Compute the maximum sum of compatibility scores by assigning students to mentors optimally.

Examples

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

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

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 Approach

Precompute Compatibility Scores

Calculate the compatibility score for every possible student-mentor pair first. Store these in a matrix to avoid recalculating during the DP recursion, since each comparison is independent.

Use State Transition Dynamic Programming

Apply DP with a bitmask representing which mentors are assigned. For each DP state, try assigning an unassigned mentor to the current student and recursively compute the score. Memoize results to prevent redundant calculations.

Combine Recursion and Bitmask Optimization

Iterate through all students, updating the bitmask at each recursion. Track the maximum sum for all valid assignments and return the final total compatibility score. This avoids brute-force factorial complexity by leveraging overlapping subproblems.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m * 2^m) due to DP over all mentor assignment states. Space complexity is O(2^m) for memoization of bitmask states. Precomputing compatibility scores adds O(m^2 * n).

What Interviewers Usually Probe

Notice the problem requires considering all possible student-mentor pairings for maximal total score.
State transition DP with bitmasking is expected for efficient solution due to small constraints (m <= 8).
Watch for repeated calculation of compatibility scores, which memoization or precomputation avoids.

Common Pitfalls or Variants

Common pitfalls

Attempting brute-force permutations without memoization leads to factorial time complexity.
Not precomputing compatibility scores can increase runtime and mask DP logic clarity.
Incorrect bitmask updates can skip valid states or double-count mentors.

Follow-up variants

Maximize total compatibility when students or mentors can be left unassigned.
Allow multiple students per mentor and compute weighted compatibility scores.
Compute minimum total compatibility sum instead of maximum using similar DP state transitions.

FAQ

What is the main pattern in Maximum Compatibility Score Sum?

The core pattern is state transition dynamic programming using bitmasking to represent which mentors are already assigned.

Can we solve this problem without DP?

A naive approach using all permutations exists but is inefficient (O(m!)) and impractical for larger m; DP with bitmasking is preferred.

How do you compute compatibility between a student and a mentor?

Count the number of positions where the student's answer matches the mentor's answer in their survey arrays.

Why is bitmasking used in this problem?

Bitmasking efficiently tracks which mentors are assigned, allowing DP to represent state transitions compactly and avoid redundant recursion.

What are common mistakes when implementing this solution?

Common mistakes include double-counting mentors, forgetting memoization, and not precomputing compatibility scores, leading to incorrect sums or high runtime.

terminal

Solution

Solution 1: Preprocessing + Backtracking

We can first preprocess the compatibility score $g[i][j]$ between each student $i$ and mentor $j$, and then use a backtracking algorithm to solve the problem.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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

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

Continue Practicing

#1986 minimum number of work sessions to finish the tasks #1799 maximize score after n operations #1723 find minimum time to finish all jobs