PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
Perhaps the simplest approach is to use binary search problem coupled with a dynamic programming subroutine. Given a value T, we can determine if it is possible to prepare all dishes in time T. All dishes that can be prepared by the other cooks in time at most T will be delegated to them. For the remaining dishes, we run a subset-sum style algorithm to determine if the Chef and his assistant can prepare them in time T. This can be done by building a table d[] where d[k] is true if and only if there is some subset of dishes of total preparation time k. We only have to build this table up to time T. Let the total preparation time (by the Chef and his assitant) of the remaining dishes be S. Then the remaining dishes can be prepared in time T if and only if some k with k <= T and S-k <= T has d[k] being true. That is, the Chef can prepare some dishes in time k and his assistant can prepare the remaining in time S-k.
There is a direct dynamic programming approach that avoids binary search which avoids the O(log n) overhead of the binary search method (as long as some sorting is done before hand), but it’s simplest to describe this approach and it was fast enough for the problem.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.