First blog post!
I want to write about a cool problem that appeared on the UKIEPC 2019 contest. Here is the statement:
You are a realtor in charge of buying and selling homes for $$$n \leq 100$$$ families. In total, there are $$$m \leq n(n-1)$$$ offers, with the $$$i$$$'th offer being family $$$a_i$$$ would like to buy family $$$b_i$$$'s home for $$$c_i$$$ dollars ($$$a_i \neq b_i$$$). In addition, the pair $$$(a_i, b_i)$$$ will occur at most once in the input.
The families agree that they will all purchase simultaneously, or stay in their original home. You earn a fixed commission of 5% on each purchase. How can you select a subset of purchases such that nobody ends up homeless and you maximise your earnings?
This problem is equivalent to the following: Given a weighted directed graph, decompose the graph into vertex disjoint cycles with maximum edge sum. Specifically, the vertices are the $$$n$$$ families, and the edges are from $$$a_i$$$ to $$$b_i$$$ with weight $$$c_i$$$. Your earnings are then just 5% of this sum.
The solution comes from this observation: A cycle decomposition can be described as a matching $$$dest_i$$$, the destination of family $$$i$$$ after all purchases. The matching requirement is $$$dest_i \neq dest_j$$$ if $$$i \neq j$$$, i.e., no two families share a home. We would like to maximise the sum of the values of each matching, which we define now: If there is an edge from $$$i$$$ to $$$dest_i$$$, then the value of the matching is the weight of the edge. Otherwise, if $$$i = dest_i$$$ the value is 0. Finally, in all other cases the value is $$$-\inf$$$. We can easily convert this to a minimisation problem by taking negatives and then apply the Hungarian algorithm in $$$n^3$$$ time.
Can anyone share other interesting problems involving matchings?
