progress

~/problems / Advanced DP / Bitmask DP

Pairing up lab partners

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium ~20 min

A chemistry teacher splits her n students (n even) into lab pairs. score[i][j] says how well i and j work together (symmetric, score[i][i] == 0).

Implement best_pairing(score: list[list[int]]) -> int: the largest total score of a pairing (0 when n = 0).

best_pairing([[0, 9, 8, 0],
              [9, 0, 0, 8],
              [8, 0, 0, 1],
              [0, 8, 1, 0]])  # 16   pairs (0, 2) and (1, 3): 8 + 8
                              #      grabbing the best pair (0, 1) first leaves (2, 3): only 9 + 1

0 <= n <= 18, scores 0..100.

⭐ Bonus: listing every pairing passes for small n; a speed test with 18 students (over 34 million pairings) earns a star with a table over subsets (2^18 entries).

Show hint

best[mask] is the top score for pairing the students in mask. To avoid repeats, always pair the lowest free student i with some free j, leading to best[mask | 1 << i | 1 << j].

Topic: Bitmask DP. dp[mask][last] over subsets (n <= ~20): TSP, assignment.

0:00
Ctrl ' run · Ctrl ↵ submit
esc