D - Cooking Editorial by en_translator


The order of using the oven does not matter; only the assignment of an oven for each dish is essential.

Considering splitting the dishes into two sets depending on which of the two oven to assign, the problem is equivalent to “minimize the maximum sum of times required to cook the dishes for a division of the \(N\) dishes into two sets.”

Let \(S\) be \(T_1+\ldots+T_N\). We can assume that the time occupying the first oven is no less than that of the second one (if not, we can swap those two). Then, the duration of the first oven’s usage is at least \(S/2\). Since we want to minimize the time to use the first oven under this constraints, the problem is boiled down to “what is the minimum sum of a subset of \(T_1,\ldots,T_N\) that is greater than or equal to \(S/2\)?”

We can solve this problem if we can answer for each \(x\) “is there a subset of \(T_1,\ldots,T_N\) whose sum is \(x\)?” This is nothing more than a subset sum problem, so it can be found in a total of \(O(N \sum_i T_i)\) time with a DP (Dynamic Programming) with the following boolean value:
\(dp[i][j]=\) whether or not there is a subset of \(T_1,\ldots,T_i\) whose sum is \(j\).

posted:
last update: