April CookOff Contest Problem Editorials

Internet Media Types (written by David Stolp aka PieGuy)

The solution proceeds in two steps. The first step is to read and store pairs of strings, and the second step is to perform a series of lookups. The most effective way to store the media types is using an associative array (such as the STL map in C++, or HashMap in Java), however the list is small enough that an array of strings would suffice. Determining the file extension requires first finding the position of the final '.' character (using strrchr or rfind in C++, or lastIndexOf in Java), then discarding the remainder of the string (using substr in C++, or substring in Java).

Problem Setter Solution
Problem Tester Solution

A Prime Conjecture (written by David Stolp aka PieGuy)

Chef's conjecture is actually false for 127 and 351, but no other counterexamples are known. The conjecture is similar to Goldbach's weak conjecture, which states that every odd number greater than 7 can be expressed as the sum of three odd primes. Goldbach's weak conjecture his been conditionally proven, contingent on the Riemann hypothesis.

To solve Chef's conjecture for small numbers, it suffices to loop through all possible values of P₂ and P₃, for each value checking if N-P₂²-P₃³ is prime. This approach can be optimized by trying large values of P₃ first, since it's easier to find solutions to P₁+P₂² = N-P₃³ when the right hand side is small (due to the higher density of primes at lower levels).

Problem Setter Solution
Problem Tester Solution

The Grand Cook Off (written by David Stolp aka PieGuy)

It seems paradoxical that if 99 chefs start with 1 token each, it's just as likely that in the final cook-off one chef will have 98 tokens and the other will have 1 as it is that one will have 49 and the other 50. In fact, if we ask the question "How many different chefs' tokens will be held by one of the finalists?", each number from 1 to C-1 is equally likely. We can therefore solve the task as follows:

Denote by N the total number of tokens. For each number i between 1 and C-1, and each number j between 1 and N, compute the number of ways to choose i chefs whose total number of tokens is j. Divide this number by the number of ways to choose i chefs from C chefs (a binomial coefficient) in order to get the probability that a finalist has j tokens, given that their tokens come from i chefs. Then divide by C-1 to get the probability of a finalist having j tokens from i chefs. Since we're computing an expected value, we multiply by the token difference abs(j-(N-j)) and sum over all i,j pairs. This computation can be done using dynamic programming on a 2-dimensional array.

Problem Setter Solution
Problem Tester Solution

Product of Digits Again (written by David Stolp aka PieGuy)

There is a fairly well-known greedy algorithm for solving the product of digits problem in base 10. Simply take as many 9's as possible, then as many 8's as possible, and so on. For example, to find the smallest number whose product of digits is 1080, begin by taking out a 9 (leaving 120), then take out an 8 (leaving 15), then a 5 (leaving 3), then a 3, so the answer is 3589. Unfortunately this doesn't carry over to higher bases. Consider the number 2²*3⁴*5⁴ in base 19. Using the greedy approach, we'd first extract two 18's (leaving 5⁴), then four 5's, for an answer of 5555II. However, a better answer is 4FFFF (four 15's and one 4). Thus the subproblem of finding the smallest number in a fixed base must be solved with another method.

Additionally, the smallest base for which an answer is possible may not be base with the smallest answer. The smallest counterexample is "14". The number 18, written in base 5 is "33", whose product of digits is 9, which is "14" in base 5. However, the number 17, written in base 6 is "25", whose product of digits is 10, which is "14" is base 6.

To solve the problem, we iterate through every possible base, finding the smallest number in each base whose product of digits gives S. Since a number cannot exceed the product of its digits, we can stop when the string S evaluated in base B is greater than the smallest value of I found thus far. To find the smallest number in a fixed base, we use a modified Dijkstra's algorithm.

Problem Setter Solution
Problem Tester Solution

Frosting Cupcakes (written by David Stolp aka PieGuy)

Consider the following restatement of the problem:

N+1 walls have been erected, each one meter apart. A window of height S has been cut into each wall at a specific height. The i'th window is has a height of C_i higher than the previous window. Take a rubber string and attach it to the bottom of the window in the first wall, pass it through all of the remaining windows, and attach it to the bottom of the window in the last wall. Compute the sum of the squares of the slopes of the rubber string between each wall and the next.

The problem is equivalent because the specific energy function used is irrelevant, so long as it is convex. If we use sqrt(K²+1) instead of K² as the energy cost of producing K units of frosting, the optimal production schedule will remain unchanged. Using the former leads to the geometry problem above.

The problem can now be solved in linear time, by using an algorithm similar to a convex hull algorithm. We imagine 2 pieces of rubber, both initially attached to the bottom of the first window. We then, one window at a time, pull both pieces of rubber through the current window and attach them to the next. One piece of rubber always attaches to the bottom of the next window, the other always to the top. We keep a list, for each rubber string, of the window points it remains in contact with. We also keep track of the last point at which both pieces of rubber are in contact. Once a rubber string loses contact with a window, it will never again come in contact with that part of the window again. On each list we perform O(N) insertions, and O(N) deletions, so the overall runtime is O(N).

Problem Setter Solution
Problem Tester Solution