1947. Maximum Compatibility Score Sum | 1704
This is a really helpful question! I need more backtracking.
Wrong but close implementation:
1class Solution:
2 def maxCompatibilitySum(
3 self, students: List[List[int]], mentors: List[List[int]]
4 ) -> int:
5 # brute force i.e., backtracking
6 # current_score = 0, remaining_students = [0, 1, 2], remaining_mentors = [0, 1, 2]
7 # current_score += student0 x mentor0, rs = [1, 2], rm = [1, 2]
8
9 def calculateScore(a: List[int], b: List[int]) -> int:
10 # assert len(a) == len(b)
11 result = 0
12 for i in range(len(a)):
13 if a[i] == b[i]:
14 result += 1
15 return result
16
17 def bt(score: int, rs: List[int], rm: List[int]) -> int:
18 # print("bt:", rs, rm)
19 if not rs or not rm:
20 return score
21
22 best_score = score
23 for i in range(len(rs)):
24 nrs = rs.copy()
25 del nrs[i]
26 for j in range(len(rm)):
27 nrm = rm.copy()
28 del nrm[j]
29 # print("nrs/rm:", nrs, nrm)
30 best_score = max(
31 best_score,
32 bt(score + calculateScore(students[i], mentors[j]), nrs, nrm),
33 )
34
35 return best_score
36
37 return bt(0, list(range(len(students))), list(range(len(mentors))))
The problem with the above code is that:
1for i in range(len(rs)):
2...
3 for j in range(len(rm)):
4...
5 calculateScore(students[i], mentors[j])
After the first deletion, rs might be [1, 2], but i = 0 would still access students[0] instead of students[1].
v2, TLE:
1class Solution:
2 def maxCompatibilitySum(
3 self, students: List[List[int]], mentors: List[List[int]]
4 ) -> int:
5 # brute force i.e., backtracking
6 # current_score = 0, remaining_students = [0, 1, 2], remaining_mentors = [0, 1, 2]
7 # current_score += student0 x mentor0, rs = [1, 2], rm = [1, 2]
8
9 def calculateScore(a: List[int], b: List[int]) -> int:
10 # assert len(a) == len(b)
11 result = 0
12 for i in range(len(a)):
13 if a[i] == b[i]:
14 result += 1
15 return result
16
17 def bt(score: int, rs: List[int], rm: List[int]) -> int:
18 if not rs or not rm:
19 return score
20
21 best_score = score
22 for i in range(len(rs)):
23 s_idx = rs[i]
24 nrs = rs[:i] + rs[i + 1 :]
25 for j in range(len(rm)):
26 m_idx = rm[j]
27 nrm = rm[:j] + rm[j + 1 :]
28 best_score = max(
29 best_score,
30 bt(
31 score + calculateScore(students[s_idx], mentors[m_idx]),
32 nrs,
33 nrm,
34 ),
35 )
36
37 return best_score
38
39 return bt(0, list(range(len(students))), list(range(len(mentors))))
This TLEs because it’s actually O((n!)^2).
8 students * 8 mentors * 7 students * 7 mentors * …
We are actually overcounting.
My current implementation:
s0m0, s1m1, s2m2
s0m0, s1m2, s2m1
s0m0, s2m1, s1m2 (!)
s0m0, s2m2, s1m1 (!)
…
If we lock the sequence of students, we can still consider all the possibilities:
s0m0, s1m1, s2m2
s0m0, s1m2, s2m1
s0m1, s1m0, s2m2 (good)
…
This also brings the complexity down to O(n * n!) which becomes O(n!).
1class Solution:
2 def maxCompatibilitySum(
3 self, students: List[List[int]], mentors: List[List[int]]
4 ) -> int:
5 # precomputing scores can cut some complexity (tho not decisive):
6 # s0m0, s1m1, s2m2
7 # s0m0, s1m2, s2m1
8 # s0m0 can be computed once and fetched later
9 n = len(students)
10
11 def calculateScore(a: List[int], b: List[int]) -> int:
12 result = 0
13 for i in range(len(a)):
14 if a[i] == b[i]:
15 result += 1
16 return result
17
18 score_table = [[0 for _ in range(n)] for _ in range(n)]
19 for i in range(n):
20 for j in range(n):
21 score_table[i][j] = calculateScore(students[i], mentors[j])
22
23 # lock student sequence to cut big O from `n! * n!` to `n! * n`
24 def bt(
25 current_score: int, current_student: int, remaining_mentors: List[int]
26 ) -> int:
27 if current_student >= n: # out of bounds == combo explored
28 return current_score
29
30 best_score = 0
31 for i in range(len(remaining_mentors)):
32 m_idx = remaining_mentors[i]
33 best_score = max(
34 best_score,
35 bt(
36 current_score + score_table[current_student][m_idx],
37 current_student + 1,
38 remaining_mentors[:i] + remaining_mentors[i + 1 :],
39 ),
40 )
41
42 return best_score
43
44 return bt(0, 0, list(range(len(mentors))))
Very useful question.
#Array #Backtracking #Python #Revisit