TOOLS - Editorial

PROBLEM LINKS

Practice
Contest

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).

@admin Code please.

Explanation was bit confusion,

In simple words it can be explained like,

we can use recursive solution to explore all possible solutions like function(tool1,tool2) but this will cause issue that while selecting tool2 we don’t know which tools are already used or delivered, so we can use bitmask to keep record or history of all previous tools details.

hence we can use dp with bitmasking like function(toolsSelected, toolsDelivery) both parameters can upto 2^8, denoting the tool used by its binary represention in particular index as 1.

Then it becomes cakewalk problem of dp.

Similar implementation: here