J: Draft Time

https://open.kattis.com/problems/drafttime

The algorithm used is a variant of the Gale-Shapley algorithm for stable matching:

While there exists an unmatched player $p$ who has not proposed to all teams:

• Let $t$ be the most preferred team that $p$ has not proposed to

• Assign $p$ to team $t$

• If $t$ was already full (i.e. already had $M$ players assigned), unassign the player that $t$ least prefers

Why does this algorithm work?

1. This algorithm always gives $M$ players to each team. This is because players can't be unassigned from a team until the team has $M$ other players. So, a player will only be unassigned at the end if all teams are full, and since we have a surplus of players (i.e. $N \cdot M \leq K$), all teams will be full.

2. There are no instabilities after running the algorithm. Suppose toward contradiction that there were, then there exists$P$ who is undrafted or would prefer to go to team $T$ over the team he got drafted by, and $T$ can draft more players or prefers $P$ to an already drafted player. However, $P$ must have proposed to $T$ (since he is either undrafted or prefers $T$ to current choice), and $T$ must have unassigned $P$ because $T$ found $M$ more-preferred players. So, $T$ must not prefer $P$ to its already drafted players.

Note that this algorithm always completes, so there's no case where you should print Hello darkness my old friend!

For implementation, you can use priority queues per team (sorted by the team's player preferences) to store matches, a stack/queue to store unmatched players, a hash map to keep track of the number of teams proposed to by each player, and hash maps to keep track of team/player preferences.

While the stack/queue is not empty, remove a player and match them to their next team (if they haven't proposed to all teams) by inserting in the team's priority queue. Then, if the priority queue has $M+1$ elements, pop the top (least preferred) player and add them back to the stack/queue.