October CookOff Contest Problem Editorials

Cooling Pies (written by David Stolp aka PieGuy)

The following greedy algorithm always finds the optimum answer:

1. Choose the lightest pie not yet on a rack
2. If none of the remaining racks can hold this pie, stop
3. Of all the racks that can hold this pie, place the pie on the rack with the smallest weight limit
4. If there are no more pies, stop. Otherwise, go back to step 1
   
   

You can find the solutions below:

Problem Testers Solution.

Birthday Candles (written by David Stolp aka PieGuy)

The answer will always be either a repdigit (a number composed of repeated instances of the same digit) or a power of 10. We find the smallest power of 10 that cannot be expressed, and for each digit we find the smallest repdigit that cannot be expressed, and take the smallest of these.

You can find the solutions below:

Problem Testers Solution.

The Perfect Chocolate Candy (written by David Stolp aka PieGuy)

Each candy can be thought of as having either a surplus of chocolate, or a deficit (which may also be thought of a negative surplus) of chocolate, defined as the amount of chocolate that would need to be removed (or added) in order for a particular candy to have the perfect ratio. If all candies have a positive surplus, or all candies have a negative, then no solution exists. Otherwise we wish to find some selection of candies whose total net surplus is zero. We first note that each candy's surplus, when multiplied by desiredCaramel, will yield an integer. That is, if we denote s_i = Chocolate_i*desiredCaramel - Caramel_i*desiredChocolate, then the surplus of candy i is s_i/desiredCaramel. Our task is to find integers p_i such that sum(s_i*p_i)=0, and not all p_i are 0. Equivalently, consider a graph where nodes are labeled ...-2, -1, 0, 1, 2... and there exists a directed edge from A to B if there is some candy i for which s_i=B-A. Our task is to find the shortest cycle in this graph.

The shortest cycle can be found using a breadth first search, but we need to keep the size of the graph small in order to make our search effective. If M is the maximum surplus, and m is the maximum deficit (that is, the negative value furthest from 0), then we need only consider nodes in the range [m*desiredCaramel, M*desiredCaramel]. To see this, suppose we have some collection of candies whose total net surplus is 0. We can add 1 candy at a time and form partial sums in such a way that the partial sum will always be in the range [m, M] as follows: whenever the partial sum is positive, choose a candy with negative surplus, otherwise choose a candy with positive surplus.

You can find the solutions below:

Problem Setters Solution.
Problem Testers Solution.

Two Chefs (written by David Stolp aka PieGuy)

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.

You can find the solutions below:

Problem Setters Solution.
Problem Testers Solution.

Product of Digits (written by David Stolp aka PieGuy)

We are given that the answer will have fewer than 700 digits (the maximum is actually 613). It suffices to find all solutions to the equation 2^a3^b5^c7^d=P(mod 1000000007), subject to a/3+b/2+c+d<700. To do this, we first make a list of all values Q such that 2^a3^b=Q(mod 1000000007) has a solution with a/3+b/2<700. We sort this list, so we can perform fast searches on it using binary search. Now for all possible values c and d with c+d<700 we check if 5^-c7^-dP is in our sorted list. If so, we've found a potential solution to the problem. Given candidate values of a, b, c, and d, we compute the answer by greedily taking as many 9's as possible, then as many 8's as possible, and so on, down to 2. Note that the digit 1 is never used, except when P itself is 1 or 0.

You can find the solutions below:

Problem Setters Solution.
Problem Testers Solution.