A: Alphabet Cake

The key mistake I made during contest is that I didn’t notice the condition “no initial appears more than once on the cake.”!!!! Idea 1: Recursion ———-

1. If there is only 1 letter, we can fill the whole square with that letter

2. If there is more than 1 letter, we can make a cut repeatedly until we reach that base case, but how to make a cut?

Idea 2: Greedy

1. for each row, expand to all existing letters to its right

2. for each row, expand to all existing letters to its left

3. the remaining rows must be completely emtpy, we just run two copy passes to ensure they are copied, one from top to bottom, and then one
   from bottom to top

B: Ratatouille

The intuition is easy, but how to prove it?!!! Goal: we try to find the optimal solution which also has the minimum number of total servings

So we just sort the ranges by upper bound, and start with the the smallest possible servings, if we can form a kit, go, otherwise, discard all ranges that is not enough to make a kit

Proof: Suppose we have an optimal solution s(1)…s(2)…s(n)..s(n+1) and our solution is o(1)….o(n), while sum of s is smallest among all possible optimal solutions, and s picks lowest upper bound whenever possble for each ingredient

  1. By induction, we can prove that, when s(1)…s(i) = o(1)…o(n), we pick the same solution

  2. consider the first s(i) s.t. s(i) < o(i), this means when we are trying forming s(i), some of the ranges are picked by previous choices already, but it is not picked in S before i => contradiciton

  3. consider the case s(n+1) does not exist, the argument is similar