PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
This problem is a superset of the problem of partitioning a graph into perfect matchings, which is NP-complete. But that didn’t stop 8 competitors from producing optimal solutions to all of the test cases, including lightning-fast solutions by gennady.korotkevich and ACRush.
A brief note on the scoring mechanism: C * N is the number of single-handed chefs it would take to form the same numbef of chef teams. Supposing it costs the same amount to hire an ambidextrous chef an a single-handed chef, C*N-H is a measure of how much money Head Chef would save by hiring ambidextrous chefs. Dividing this value by M normalizes the test cases so that the theoretical maximum score on a test case is 1.
Construct a multigraph with N vertices (one for each tool), and for each of the M chefs add an edge between the vertices corresponding to the 2 tools that chef can use. Our task is to extract from this graph as many edge covers as possible, with the secondary goal of minimizing the total number of edges used. In the case that N is even and every tool is usable by the same number of chefs (that is, every vertex has the same degree), the problem reduces to finding a partitioning into perfect matchings, as mentioned above.
The condition that every tool is usable by at least one chef (that is, no vertex has degree 0) implies that an edge cover exists, and with at most N-1 vertices. Such an edge cover can be constructed as follows: Hire an arbitrary chef. Then for each remaining chef, hire that chef only if that chef can use a tool that none of the currently hired chefs can use. Initially, 1 chef is hired, and 2 chefs are usable. For each additional chef hired, the number of usable tools will increase by at least one, hence at all stages the total number of usable tools will exceed the number of chefs hired. In the end all N tools will be usable, thus at most N-1 chefs will have been hired. Note that in the worst case, the minimum edge cover contains exactly N-1 vertices: a graph with N-1 vertices of degree 1, and 1 vertex of degree N-1 (i.e. the star graph with N vertices).
An approach that did very well is greedily extracting minimum edge covers from the graph. Minumum edge covers can be found in polynomial time. By randomizing the order of the edges and repeating this process several times, the probability of finding an optimal solution increases with each iteration. Several of the winning solutions were based on this idea.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.