Match Editorial

The Problems

Value	250
Submission Rate	133/196 (67.86%)
Success Rate	85/133 (63.91%)
High Score	androm for 244.74 points

Reference implementation: fvolny4

For this problem, one only has to work with the amount of rum in the two bowls the punch can be ignored). That is, one should have two variables, rumAand rumB, representing the number of units of rum in bowls A and B, respectively. Initially, rumA = 360000 and rumB = 0.

Now, for each time the bowls are mixed, 120000 units of the liquid in bowl A are poured into bowl B. There will always be 360000 units of liquid in bowl A at the beginning of each mix. Thus one third of the units of rum in bowl A will be transferred to bowl B. That is, rumB += rumA / 3, and rumA -= rumA / 3. This brings the total volume of liquid in bowl B to480000 units.

Then 120000 units of liquid are poured back into bowl A. In this case, one fourth of the units of liquid in bowl B are poured into bowl A. Thus, rumA += rumB / 4 and rumB -= rumB / 4.

We simply repeat this simple process (which is just four lines of code) mixes times and return the final value of rumB.

Value	1000
Submission Rate	21/196 (10.71%)
Success Rate	4/ 21 (19.05%)
High Score	smai for 514.86 points

Reference implementation: smai

The easiest way to conceptualize this problem is to transform the input string array into a single array that can be indexed using the method described in the problem statement. To do this, initialize an empty array to represent the tree. If one needs to allocate storage initially (e.g., if using a java array), it helps to know that the exact size needed will be (1 << levels.length) - 1. Iterate through each string in the input array, and for each token in this string add a value to the tree array. To represent entries of *, use a value that is not between -100 and 100 inclusive.

Next, iterate through each element of the tree array (skipping the first), verifying that the element does not violate any of the rules for a binary search tree. To do this we check the value against each of its ancestors. It helps to know the following information that can be determined from a value's index in the tree array (note that all indices are counting from 1 in the following):

• The parent of the element at index i is at index i / 2
• If i is even, then it is the left child of its parent; if i is odd, it is the right child of its parent

So, for each element we check it against its ancestors, noting whether it is in the left or right subtree of each ancestor. If i is the 1-based index of the current element, initialize j = i. While j > 1, we compare the value at i to the value at j / 2. We do the division after the comparison so that we can determine which subtree of j / 2 that i is in (this information is lost after we do the integral division). If j % 2 == 0 and the value at i (which would be i - 1 using 0-based indexing) is greater than the value at j / 2 (which would be j / 2 - 1 using 0-based indexing), then a rule has been violated. Similarly, if j % 2 == 1 and the value at i is less than the value at j / 2, a rule has been violated. Also note that if the value of i's immediate ancestor is *, a rule has been violated. If you check this rule properly, there's no need to check it for all ancestor's of i. To continue to the next ancestor of i, divide j by 2.

If one can iterate through the elements from 2 to (1 << levels.length) - 1 inclusive using 1-based indexing without finding a rule violation, then the tree is valid. Otherwise, return the 1-based index of the first element found that violates a rule. The only trick is to keep the 0-based and 1-based indexing straight. The sample cases are sufficient for working this out.

Value	550
Submission Rate	81/196 (41.33%)
Success Rate	46/81 (56.79%)
High Score	rschutt for 495.06 points

Value	300
Submission Rate	125 / 136 (91.91%)
Success Rate	100 / 125 (80%)
High Score	Saxophonist for 281.77 points

There are two basic methods for solving this problem. The first is to simply hard code a mapping of keys to scales for all the possible inputs. The mapping is as follows:

This is simple enough, particularly if one has this mapping already available. However, for those that did not, the second method must be used. This method uses the table given in the problem specification:

It helps to note that each row represents a particular pitch, while the values in that row represent valid representations for that pitch.

The first note of a scale will begin with the note specifying its key, and we will start at the row containing the key. To find the next note of the scale, skip ahead the appropriate number of rows to find the row representing the next pitch of the scale. The amount of rows to skip are: 2, 2, 1, 2, 2, 2, and then 1. Note that this sums up to 12, and there are twelve rows in the table, so we will always end up where we started.

For each note in the scale, we have to pick the appropriate representation. If the previous note was A#, we need to pick a representation with a B at the beginning of it. If the previous note was a G, we need to pick a representation with a A at the beginning of it. We simply check the available representations at the current row to see if any begin with the appropriate note. If none do, then we return ERROR. Otherwise we append that note to our string.

This is simple enough to implement once the table has been initialized properly in the code. The rest is just handling the spaces between notes so that there is no trailing space.

Value	650
Submission Rate	38 / 136 (27.94%)
Success Rate	22 / 38 (57.89%)
High Score	NDBronson for 540.33 points

To solve this problem we iteratively tile over portions of the floor (following the rules given) until the entire floor is tiled. We then return how many iterations it took. Thus the problem reduces to locating the rectangle that should be tiled next.

A na•ve implementation would have six nested for loops: one for the top row of a rectangle; one for the bottom row; one for the left-most column; and for the right-most column; and then two more for loops to iterate through all the tiles within these bounds. However, the na•ve solution will never finish in time on a 50 x 50 input, as 50 ^ 6 is greater than 15 billion iterations.

However, a more efficient implementation that is equivalent to the na•ve solution is possible. Let h be the number of rows in the floor, and w be the number of columns. We iterate through each row and column (r, c) of the floor. Initialize a variable rwidth to w. If (r, c) is already tiled, skip it. Otherwise, we iterate through each r <= r' < h such that (r', c) has not yet been tiled and requires the same type of tile as (r, c). For each r' we find the smallest c' < c such that (r', c') cannot be part of a rectangle of the same type of tiles. If c' - c < rwidth, we update rwidth with the value of c' - c. At this point we know the dimensions of the largest possible rectangle with a top-left corner of (r, c) and bottom row of r'. We can then compare it against the best rectangle found so far, and update that if appropriate. The area is (r' - r + 1) * rwidth.

After a rectangle is chosen for tiling, we "tile" it by modifying the array in which we store the floor information (e.g., marking with 'T' as in the examples given in the problem statement).

Value	850
Submission Rate	32 / 136 (23.53%)
Success Rate	18 / 32 (56.25%)
High Score	John Dethridge for 724.82 points

Like many Level 3 problems, the solution to this problem embodies dynamic programming. That is, one can determine an appropriate algorithm via induction.

Suppose we sort the customers from left to right. Then suppose we already know the minimum cost for reaching just the first customer, and the minimum cost for reaching the first two customers, and so on up to the first n customers. Let these costs be stored in an array cost such that cost[i] is the minimum cost of reaching the left-most i customers (and cost[0] = 0 is the base case). Can we use this information to add a customer from the right?

In an optimal configuration, any tower that we build should always have a customer located at either extreme end of its range (for towers of height one it's the same customer on both ends). There's no sense in having the extent of the range terminate somewhere in the no-man's land between two customers. This means that if we add any customer to the right of a set of other customers, then there must exist a tower that just reaches this right-most customer. The left-most extent of this tower's arrange must be the location of either the new customer or one of the customers preceding it on the left.

We iterate through each of the customers that are to the left of the customer being added. For each one, we compute the cost of erecting a tower that can reach that customer and the new customer simultaneously (if the required height of such a tower exceeds the maximum height, its cost is infinity). This gives a cost (not necessarily the minimum) for covering all the previous customers as well as the new one. If we add a tower that covers both customer i and customer n + 1, then the resulting configuration costs cost[i - 1] plus the cost of that tower. If we consider all these possible configurations, as well as the configuration resulting from adding a tower of height 1 at the location of the new customer, we will encounter the one of minimum cost. We take the minimum and store it in cost[n + 1].

Once the problem and its solution are understood, it is trivial to implement. Other dynamic programming solutions are possible (I managed to come up with a very different O(n^2) one during the match), but this is the simplest one I've seen. One mistake that several people made (such as myself) was to implement their solution in such a way that an input of no customers caused a runtime error. This shows how important it is to read carefully over the notes and input constraints and consider their ramifications.