1947. Maximum Compatibility Score Sum

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 ith 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 jth 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.

class Solution {
    int dp[1<<8];
    int helper(vector<int>& A, vector<int>& B, int mask, int m, int p) {
        if(dp[mask] != -1) return dp[mask];
        int& res = dp[mask] = 0;
        int n = A.size();
        for(int j = 0; j < n; j++) {
            if(mask & (1<<j)) continue;
            res = max(res, m - __builtin_popcount(A[p] ^ B[j]) + helper(A,B,mask | (1<<j),m,p+1));
        }
        return res;
    }
public:
    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
        int n = students.size(), m = students[0].size();
        vector<int> A(n, 1<<10), B(n, 1<<10);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(students[i][j]) A[i] |= 1<<j;
                if(mentors[i][j]) B[i] |= 1<<j;
            }
        }
        memset(dp,-1,sizeof dp);
        dp[(1<<n) - 1] = 0;
        return helper(A,B,0,m,0);
    }
};