TWOCHEFS - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

This problem can be solved using dynamic programming. We assign dishes to the ovens, one at a time, and in the order they must be completed, while memoizing:

memo[d1][d2][t] = number of minutes required to finish cooking all dishes, where

  • first chef’s first d1 dishes have been assigned to an oven
  • second chef’s first d2 dishes have been assigned to an oven
  • one of the ovens has just finished cooking all of the dishes assigned to it, and the other will finish cooking all of the dishes assigned to it in t minutes

From each state, the next dish we assign can be from either chef, and can go in either oven. In order to satisfy the order constraint, when we assign a dish to an oven we require it to finish cooking at the same time or after the last dish assigned to the other oven.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

//