PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
Exhaustively enumerating all possible ways of visiting the tools and chefs will time out. With clever pruning, it might be possible to get such an approach accepted, but there is a simpler way to guarantee acceptance. It is an easy modification of the O(n^2 * 2^n) dynamic programming approach to the Hamiltonian cycle problem. Let S be a subset of the tools and cooks. Let d[S,k] denote the minimum distance required to visit all locations not in S starting from location k while observing the “carry at most 2 tools at a time” rule. Of course, S should be such that if a cook c is in S, then their requested tool t is also in S (call this property *).
Given such a pair (S,k), we can easily determine how many tools the Chef is holding at location k after visiting locations in S. To compute d[S,k], we recursively try to compute d[S+z,z] for each location z not in S as long as S+z still has property * and doesn’t leave the Chef holding more than 2 tools.
Then, d[S,k] is simply the minimum over d[S+z,z] + dist(z,k) over all valid z in S. The number of states is at most n * 3^n since each cook-tool pair has 3 states (neither visited, tool visited, or tool and cook visited) and for a fixed S and a fixed cook-tool pair, at most one of the cook or tool may appear as the location k in a valid pair (S,k).