Formatted question description: https://leetcode.ca/all/1947.html

1947. Maximum Compatibility Score Sum

Level

Medium

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 numbered from 0 to m - 1 and m mentors numbered from 0 to m - 1. The answers of the students are represented by a 2D integer array students where students[i] is an integer array that contains the answers of the i-th student (0-indexed). The answers of the mentors are represented by a 2D integer array mentors where mentors[j] is an integer array that contains the answers of the j-th mentor (0-indexed).

Each student will be assigned to one mentor, and each mentor will have one student assigned to them. The compatibility score of a student-mentor pair is the number of answers that are the same for both the student and the mentor.

  • For example, if the student’s answers were [1, 0, 1] and the mentor’s answers were [0, 0, 1], then their compatibility score is 2 because only the second and the third answers are the same.

You are tasked with finding the optimal student-mentor pairings to maximize the sum of the compatibility scores.

Given students and mentors, return the maximum compatibility score sum that can be achieved.

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

Explanation: 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

Explanation: 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

Since both m and n do not exceed 8, each row in students and mentors can be considered as a binary representation and can be converted into an integer that does not exceed 255. After converting into integers, calculate the permutations of the m rows. For each permutation, calculate the compatibility score sum using bitwise operation, and return the maximum compatibility score sum.

  • class Solution {
        public int maxCompatibilitySum(int[][] students, int[][] mentors) {
            int m = students.length, n = students[0].length;
            int[] studentsNums = new int[m];
            int[] mentorsNums = new int[m];
            for (int i = 0; i < m; i++) {
                studentsNums[i] = convertToNum(students[i]);
                mentorsNums[i] = convertToNum(mentors[i]);
            }
            int[] nums = new int[m];
            for (int i = 0; i < m; i++)
                nums[i] = i;
            int maxSum = 0;
            List<List<Integer>> permutations = permute(nums);
            for (List<Integer> permutation : permutations) {
                int sum = 0;
                for (int i = 0; i < m; i++)
                    sum += n - Integer.bitCount(studentsNums[i] ^ mentorsNums[permutation.get(i)]);
                maxSum = Math.max(maxSum, sum);
            }
            return maxSum;
        }
    
        public int convertToNum(int[] arr) {
            int num = 0;
            int length = arr.length;
            for (int i = 0; i < length; i++)
                num += arr[i] << i;
            return num;
        }
    
        public List<List<Integer>> permute(int[] nums) {
            int length = nums.length;
            List<List<Integer>> permutations = new ArrayList<List<Integer>>();
            List<Integer> permutation = new ArrayList<Integer>();
            for (int i = 0; i < length; i++)
                permutation.add(nums[i]);
            backtrack(length, permutations, 0, permutation);
            return permutations;
        }
    
        public void backtrack(int length, List<List<Integer>> permutations, int start, List<Integer> permutation) {
            if (start == length)
                permutations.add(new ArrayList<Integer>(permutation));
            else {
                for (int i = start; i < length; i++) {
                    Collections.swap(permutation, start, i);
                    backtrack(length, permutations, start + 1, permutation);
                    Collections.swap(permutation, start, i);
                }
            }
        }
    }
    
  • Todo
    
  • # 1947. Maximum Compatibility Score Sum
    # https://leetcode.com/problems/maximum-compatibility-score-sum/
    
    class Solution:
        def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
            n = len(students)
            
            def dfs(i, used, score):
                if i == n: return score
                
                res = float(-inf)
                
                for j, mentor in enumerate(mentors):
                    if j in used: continue
                        
                    ss = sum(int(a == b) for a, b in zip(students[i], mentor))
                    used.add(j)
                    score += ss
                    
                    res = max(res, dfs(i + 1, used, score))
    
                    used.remove(j)
                    score -= ss
                
                return res
            
            return dfs(0, set(), 0)
    
    

All Problems

All Solutions