How to Solve Maximum Compatibility Score Sum

This problem requires computing the maximum total compatibility score between students and mentors by exploring all valid assignments. Using state transition dynamic programming, we calculate compatibility for each student-mentor pair and track assignment states efficiently with bitmasking. The solution balances recursion and memoization to avoid recomputation while ensuring all possible pairings contribute to the optimal sum.

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

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.

How GhostInterview Helps

• Automatically generates the DP recursion structure and handles memoization of bitmask states.
• Precomputes all compatibility scores for each student-mentor pair to streamline recursive calculations.
• Tracks maximum compatibility efficiently while validating all possible assignments without manual state bookkeeping.

Topic Pages

• Array
• Dynamic Programming
• Backtracking
• Bit Manipulation
• Bitmask

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.