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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Compatibility Score Sum

Difficulty: Medium

Problem 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 and m mentors. Each student's answers are represented by a 2D integer array students, and each mentor's answers are represented by a 2D integer array mentors. The compatibility score of a student-mentor pair is the number of answers that are the same for both. The task is to find the optimal student-mentor pairings to maximize the sum of compatibility scores.

Key Insights

  • Each student can be paired with one mentor, and vice versa.
  • Compatibility score is calculated as the number of matching answers between a student and a mentor.
  • The problem can be solved using backtracking or dynamic programming due to the small constraints (1 ≤ m, n ≤ 8).
  • A bitmask can be used to represent the pairing of students and mentors efficiently.

Space and Time Complexity

Time Complexity: O(m! * n)
Space Complexity: O(m)

Solution

The solution involves using a backtracking approach to explore all possible pairings of students to mentors. Given the constraints, we can generate all permutations of the mentor indices and calculate the compatibility score for each pairing. The maximum score across all permutations is kept track of and returned. This approach leverages the fact that m is small, allowing us to explore m! permutations.

Code Solutions

def maxCompatibilitySum(students, mentors):
    from itertools import permutations

    def compatibility_score(student, mentor):
        return sum(s == m for s, m in zip(student, mentor))

    m = len(students)
    max_score = 0

    for perm in permutations(range(m)):
        current_score = sum(compatibility_score(students[i], mentors[perm[i]]) for i in range(m))
        max_score = max(max_score, current_score)

    return max_score
← Back to All Questions