We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Compatibility Score Sum

Number: 2078

Difficulty: Medium

Paid? No

Companies: Meta

Problem Description

You are given two 2D arrays: students and mentors. Each array contains m arrays of length n where all entries are either 0 or 1. The i-th student and j-th mentor have provided n responses to a survey. The compatibility score between a student and a mentor is defined as the number of answers that are the same. Your task is to assign each student to one unique mentor (and vice versa) so that the sum of all compatibility scores is maximized.

Key Insights

  • Pre-calculate compatibility scores between every student-mentor pair to avoid redundant computation.
  • Since m and n are at most 8, bitmask dynamic programming (or backtracking with bitmasking) is a feasible approach.
  • Use recursion/DFS to explore all possible assignments using a bitmask to track which mentors have been paired.
  • Memorization (or DP table) can help avoid recomputation by caching the result for a given student index and mentor mask.

Space and Time Complexity

Time Complexity: O(m^2 * 2^m) – There are 2^m mentor masks and for each we consider up to m transitions, along with an O(m) compatibility calculation precomputed. Space Complexity: O(2^m) – For the DP memoization/cache plus additional space for the recursion stack.

Solution

We can solve this problem using a dynamic programming approach that leverages bitmasking. First, we precompute the compatibility score for each student-mentor pair by iterating through each survey answer. Then, we use recursion (or DFS) to try pairing each student with an available mentor. A bitmask is maintained to indicate which mentors have already been paired. With each recursive call, we add the current compatibility score and move on to the next student. Through memoization, we ensure that each state (student index and mask) is computed only once, leading to an efficient solution even though the algorithm examines all mentor assignments.

Code Solutions

# Python Code Solution

from functools import lru_cache

def maxCompatibilitySum(students, mentors):
    m = len(students)
    n = len(students[0])
    
    # Precompute compatibility scores for each pair (student, mentor)
    compatibility = [[0] * m for _ in range(m)]
    for i in range(m):
        for j in range(m):
            score = 0
            # Compare answers for student i and mentor j
            for k in range(n):
                if students[i][k] == mentors[j][k]:
                    score += 1
            compatibility[i][j] = score

    # Define DFS with memoization using bitmask for assigned mentors
    @lru_cache(maxsize=None)
    def dfs(student_index, mask):
        # If all students are assigned, return 0
        if student_index == m:
            return 0
        max_score = 0
        # Try assigning each available mentor to the current student
        for j in range(m):
            if mask & (1 << j) == 0:  # if mentor j not used 
                # Add the compatibility score and recursively assign next student 
                current_score = compatibility[student_index][j] + dfs(student_index + 1, mask | (1 << j))
                max_score = max(max_score, current_score)
        return max_score

    # Start recursion from first student with no mentor assigned
    return dfs(0, 0)

# Example usage:
# students = [[1,1,0],[1,0,1],[0,0,1]]
# mentors = [[1,0,0],[0,0,1],[1,1,0]]
# print(maxCompatibilitySum(students, mentors))  # Output: 8
← Back to All Questions