Match Editorial

		MATCH EDITORIAL LINKS:
	Room 1 Review Archive   Rookie Review Discuss this match   Problem Set Want to write a feature?

My general impression of these problems is that they were relatively easy. However, the resulting statistics seem to indicate that the difficulty was just right. Regardless, this was a fun set of problems. My only suggestion to the author, axchma is to pick an easier-to-type handle if he ever again intends to use his handle in the input to a problem.

The Problems

Value	250
Submission Rate	332 / 347 (95.68%)
Success Rate	299 / 332 (90.06%)
High Score	jovian for 248.71 points

This is quite a simple problem to implement. Initialize a counter to 1. Iterate through the input string. For each instance of the letter 'e', increment the counter. Otherwise, if the counter is 0, return one plus the current index in the string, else decrement the counter. Of course, one can increment and decrement by 2 (or 50 or any constant, really), if one prefers.

Value	450
Submission Rate	323 / 347 (93.08%)
Success Rate	160 / 323 (49.54%)
High Score	ragnabot for 412.54 points

This problem simply tests one's ability to follow directions. Most of the types of phone numbers are easy to detect. A prefix of 1, 0, or 555; 11 occurring immediately after the first digit; and certain properties of the last four digits.

Checking whether a number is a vanity number is the most complex part. First one has to check if the four digits form an ascending or descending series. This can be done in one if-statement. Then one has to count up digits and see how many distinct digits there are. There are many ways of doing this: sorting the digits and counting the ``transitions'', accumulating occurences in an array and counting the non-zero values, etc.

Value	200
Submission Rate	259 / 265 (97.74%)
Success Rate	171 / 259 (66.02%)
High Score	wybili for 190.99 points

For each language, maintain a count of the number of non-amhcxa users of that particular language. Also maintain a separate count of users that come after amhcxa in the list of that particular language. If the second count is exactly three, then the number of challenges for that particular language will be three. If the second count is greater than three, then the number of challenges for that particular language will be zero. Otherwise, the number of challenges for that particular language will be equal to the total count of non-amhcxa users of that particular language. An alternative method is to simply simulate the challenges submitted by each non-amhcxa contestant.

The special case to look out for is when there are exactly three submissions using a particular language following amhcxa's submission. In this case, there will always be exactly three challenges if amhcxa chooses that language. This basically corresponds to avoiding counting self-challenges. Many people seem to have made this mistake.

Value	450
Submission Rate	176 / 265 (66.42%)
Success Rate	159 / 176 (90.34%)
High Score	bigg_nate for 441.28 points

Value	900
Submission Rate	79 / 347 (22.77%)
Success Rate	35 / 79 (44.3%)
High Score	Partorg for 786.61 points

This problem is an excellent, simple demonstration of dynamic programming. It proved to be quite easy for the Division-I contestants who knew how to do it, where only 15 out of 176 submissions failed.

It is clear from the potentially high values that can be returned that the approach of generating every possible permutation of dice rolls that can lead up to the desired sum is not tractable. Instead, we must find some way to reduce the problem.

We know how to solve the problem easily for the roll of one die (this is trivial). From the results of rolling one die, can we somehow easily determine the results of rolling another die? We can, because there are only six ways the additional die can be rolled, and this is completely independent from the result of the previous die. For each number obtained from the previous roll and for each possible roll of the additional die, we compute the sum and know that we have found a way to obtain that particular sum with two dice.

In fact, we can generalize this to any number of dice. Suppose we know how many possible ways there are to obtain any sum from rolling n dice. Let us denote this as S(n, v), meaning that the number of ways to obtain a sum of v from n dice is S(n, v). Each value of v for which S(n, v) > 0 will contribute its value to S(n + 1, v + i) for each 1 <= i <= 6. That is, S(n + 1, v) = S(n, v - 1) + S(n, v - 2) + ... + S(n, v - 6), where S(n, v) = 0 if v < 0.

This is what is known as a recurrence relation. All that is left are the initial conditions. The relation only really works if we assume a priori that there is exactly one way to obtain a sum of 0 with 0 dice. This gives S(0, 0) = 1. This is all we need to know to solve the problem. (Alternatively, we could assume S(1, i) = 1 for 1 <= i <= 6, but this can be derived from the simpler initial condition of S(0, 0) = 1).

Reducing a problem in this manner is known as dynamic programming (which sounds like a buzzword but really refers to a general algorithmic technique). It basically means we reduce a problem to the smaller version of the same problem, until we reach some base case. To do this we have to determine a way to get from the smaller version to the larger version while maintaining correctness. This approach only makes sense, of course, if deriving the answer to a larger problem from a smaller problem isn't too computationally intensive, and if the number of problems we'd have to solve for is reasonably small. In this case, deriving the solution of one problem from the next simpler problem is O(sum). The number of problems we solve is exactly numDice, and so the solution is O(numDice * sum).

To solve this problem we need to implement the computation of the recurrence relation which we derived. For this problem it is sufficient to initialize a two-dimensional array, where each row represents a value of n and each column represents a value of v (we'll call this array S because, after the computation is done, it will be equivalent to our recurrence relation S). We initialize the entire first row to zero, except for the first element which we initialize to 1 (S[0][0] = 1, our initial condition). The width of the array need only be as wide as the sum we are looking for (because once we obtain a sum greater than our target, we will never be able to reach our target from that combination of dice rolls). It should have a width of sum + 1, in fact, so that we can represent every possible sum from 0 to sum inclusive.

We then build our way up to knowing the value of S[numDice][sum], one die at a time. We have an outer for-loop, which iterates i from 1 to numDice inclusive. Nested in that loop we have another for-loop, which iterates j from i - 1 to sum inclusive. And nested in that loop we have another for-loop, which iterates k from 1 to 6, inclusive.

For each combination of i, j, k such that j + k <= sum, we add to the current value of S[i][j + k] the value of S[i - 1][j]. And that is the entire program. Once we complete populating the row for i = numDice, we simply return S[numDice][sum].

Many variations of this technique exist, of course. For example, only a one-dimensional array is really needed, if one updates the values in the array in descending order of indices.

Value	1000
Submission Rate	75 / 265 (28.3%)
Success Rate	29 / 75 (38.67%)
High Score	SnapDragon for 793.49 points

This is the only problem of the match that was really difficult (though, at least from my own perspective, it seemed easier than recent Division-I Level 3 problems). The solution was basically a depth-first search of all the graphs that can be constructed within the given constraints.

Our initial "position" in the depth-first search is a graph with no edges (all our graphs will have the exact same vertices). The depth-first traversal will consist of adding edges from the current vertex (which is initially the vertex whose degree is represented by the first value in the input array) until the current vertex has the desired degree. For each possible way of adding edges to the current vertex, we recursively build the graph with the next vertex as the current vertex.

We backtrack whenever the current vertex has a degree that is larger than its desired degree (or, if its desired degree is unreasonably large, as in greater than the number of vertices following it in the list, although this didn't seem to be an important optimization). Whenever we reach a vertex, we know we have satisfied the constraints for all the vertices preceding it, so the maximum depth in the vertex list that we reach gives the maximum i for which the graph is i-good.

We begin our implementation with a recursive function that attempts to build all possible edge combinations from the current vertex. For each edge combination that gives the current vertex the desired degree, it then recursively calls itself on the next vertex.

For each vertex, then, we must iterate through all combinations of vertices following it of a particular size. That is, if the vertex requires d more edges to reach its desired degree, and there are n vertices following it in the list, then there will be C(n, d) possible edge combinations. We need to iterate through each of these.

One method of doing this, which I've discussed in previous writeups, consists of a recursive function to build each combination and an array to represent which elements have already been added to the current combination. Another method is to iterate through all combinations, and simply filter out the ones of the desired size. As discussed previously, one can iterate through all combinations (that is, all subsets) from a set of size n by iterating through all values from 0 to (1 << n) - 1 inclusive. The binary representation of the iterator represents which elements are in (or not in) the subset. By counting the 1 bits (or the 0 bits if you're a pessimist), one can determine the subset size. This approach was used by SnapDragon.

Once we have an edge combination, we decrement the degree of each vertex attached to the current vertex by the set of edges by one. We can then recursively call our function on the next vertex, and after it returns, increment the degrees of those same vertices. Rather than keeping a separate count of running degree values, and comparing to the input list, we can simply decrement values in that list as we add edges and increment as we remove them (thus giving a list of "remaining" degrees). Whenever we visit a vertex that has a remaining degree less than 0, we know it cannot have the desired degree given the edges that have already been constructed, and so we return.

The value returned by our solution is then the highest index in the degree list that was visited. If the entire list was visited, we return -1. By constructing the solution carefully, so that no edge combinations are visited twice, the solution will be efficient enough.