Exactly K Preferred Role Assignments
IMC Trading● MediumNEW GRADOAProblem statement
There are n distinct players and n distinct roles. Every player must receive exactly one role, and each role must be assigned to exactly one player.
For this exercise, assume each player has a different preferred role, so the preferences form a one-to-one mapping. Relabel players and roles so player i prefers role i.
Return the number of assignments in which exactly k players receive their preferred role. Count assignments, rather than their probability.
For this exercise, assume n and k generalize the reported five-player, two-match question. When n = 0 and k = 0, the empty assignment counts as one.
Complete countPreferredAssignments(n, k) and return the exact count as a signed 64-bit integer.
Function
countPreferredAssignments(n: int, k: int) → longExamples
Example 1
n = 5k = 2return = 20Choose the two matching players in C(5,2) = 10 ways. The other three players must all miss their preferred roles; their roles can be assigned in two cyclic arrangements. The total is 10 * 2 = 20.
Example 2
n = 3k = 1return = 3Choose one of the three players to receive their preferred role. The two remaining players must swap roles, giving exactly three assignments.
Example 3
n = 4k = 3return = 0If three players receive their preferred roles, only the fourth player and their own role remain. That player also matches, so exactly three matches is impossible.
Example 4
n = 0k = 0return = 1There is one empty assignment, and it has zero matches.
Constraints
- For this exercise, assume
0 <= n <= 20and0 <= k <= n. - All players and roles are distinct; every preferred role belongs to exactly one player.
- The exact count and intermediate values in the presented solutions fit in a signed 64-bit integer:
20! = 2432902008176640000.