Welcome to Subscribe On Youtube

1947. Maximum Compatibility Score Sum

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

 

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.

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      private int[][] g;
      private boolean[] vis;
      private int m;
      private int ans;
  
      public int maxCompatibilitySum(int[][] students, int[][] mentors) {
          m = students.length;
          g = new int[m][m];
          vis = new boolean[m];
          for (int i = 0; i < m; ++i) {
              for (int j = 0; j < m; ++j) {
                  for (int k = 0; k < students[i].length; ++k) {
                      g[i][j] += students[i][k] == mentors[j][k] ? 1 : 0;
                  }
              }
          }
          dfs(0, 0);
          return ans;
      }
  
      private void dfs(int i, int t) {
          if (i == m) {
              ans = Math.max(ans, t);
              return;
          }
          for (int j = 0; j < m; ++j) {
              if (!vis[j]) {
                  vis[j] = true;
                  dfs(i + 1, t + g[i][j]);
                  vis[j] = false;
              }
          }
      }
  }
  

• class Solution {
  public:
      int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
          int m = students.size();
          int n = students[0].size();
          int g[m][m];
          memset(g, 0, sizeof g);
          bool vis[m];
          memset(vis, 0, sizeof vis);
          for (int i = 0; i < m; ++i) {
              for (int j = 0; j < m; ++j) {
                  for (int k = 0; k < n; ++k) {
                      g[i][j] += students[i][k] == mentors[j][k];
                  }
              }
          }
          int ans = 0;
          function<void(int, int)> dfs = [&](int i, int t) {
              if (i == m) {
                  ans = max(ans, t);
                  return;
              }
              for (int j = 0; j < m; ++j) {
                  if (!vis[j]) {
                      vis[j] = true;
                      dfs(i + 1, t + g[i][j]);
                      vis[j] = false;
                  }
              }
          };
          dfs(0, 0);
          return ans;
      }
  };
  

• class Solution:
      def maxCompatibilitySum(
          self, students: List[List[int]], mentors: List[List[int]]
      ) -> int:
          def dfs(i, t):
              if i == m:
                  nonlocal ans
                  ans = max(ans, t)
                  return
              for j in range(m):
                  if not vis[j]:
                      vis[j] = True
                      dfs(i + 1, t + g[i][j])
                      vis[j] = False
  
          m = len(students)
          g = [[0] * m for _ in range(m)]
          for i in range(m):
              for j in range(m):
                  g[i][j] = sum(a == b for a, b in zip(students[i], mentors[j]))
          vis = [False] * m
          ans = 0
          dfs(0, 0)
          return ans
  
  

• func maxCompatibilitySum(students [][]int, mentors [][]int) (ans int) {
  	m, n := len(students), len(students[0])
  	g := make([][]int, m)
  	vis := make([]bool, m)
  	for i := range g {
  		g[i] = make([]int, m)
  		for j := range g {
  			for k := 0; k < n; k++ {
  				if students[i][k] == mentors[j][k] {
  					g[i][j]++
  				}
  			}
  		}
  	}
  	var dfs func(int, int)
  	dfs = func(i, t int) {
  		if i == m {
  			ans = max(ans, t)
  			return
  		}
  		for j := 0; j < m; j++ {
  			if !vis[j] {
  				vis[j] = true
  				dfs(i+1, t+g[i][j])
  				vis[j] = false
  			}
  		}
  	}
  	dfs(0, 0)
  	return
  }
  

All Problems

All Solutions