Match Editorial

Snapdragon crushed the competition in Division One with an authoritative performance, winning the division by over 200 points. tomek remains absolutely perfect, tying Yarin for the longest perfection streak ever (seven matches). However all seven of Yarin's matches were in Division One. tomek has only competed in Division One six times to-date. Veloso, back in Division One after a brief slump in Division Two has turned up the heat again with a room win and the seventh highest score overall.

Division Two only saw four correct level three submissions. The fastest of those was from P.S who submitted in just under 40 minutes. Although P.S was rewarded with a 274 point rating jump, both fbird's and ozzie's performances on the level one and two problems were enough to make up for the deficit on the level three and P.S ended up in third place overall.

The Problems

Value	300
Submission Rate	197 / 214 (92.06%)
Success Rate	183 / 197 (92.89%)
High Score	Gladiator for 292.54 points

Implementation

To begin, we parse the values provided by each entry of the input array. We can do this with a simple tokenizer (such as a stringstream in C++), retrieving two floating point values from each string. As we do this, we maintain two running totals for the total cost and the total price.

Once we have the totals, we take the difference of the total cost from the total price. We then take this difference (which should be a floating point value) and divide it by the total price. We then multiply this percentage by 100 and truncate it (by casting it to an int) and return it.

Value	450
Submission Rate	189 / 214 (88.32%)
Success Rate	179 / 189 (94.71%)
High Score	liu for 438.84 points

Implementation

This problem is a simple string transformation that can be done in-place. We iterate through each character of the string. We then apply one of the following transformations to it:

In languages where strings are immutable (such as Java), we would have to construct a new string or do our work in a mutable string buffer, but the concept is the same.

Value	1000
Submission Rate	31 / 214 (14.49%)
Success Rate	4 / 31 (12.9%)
High Score	P.S for 483.44 points

Value	500
Submission Rate	79 / 137 (57.66%)
Success Rate	34 / 79 (43.04%)
High Score	ZorbaTHut for 442.90 points

Implementation

This problem is all about sorting. First we iterate through each of the three categories (columns). For each category, we sort the entries in descending order of their score in that category. We then assign their ranks for this category by iterating through this sorted list. The first entry in the list will be ranked 1st, of course. For each following entry, if its score is the same as the preceding entry, then it gets the same rank as the preceding entry. Otherwise, its rank is its (1-based) index in the sorted list. E.g.

rank[cat][i] = score[cat][i] == score[cat][i - 1] ? rank[cat][i - 1] : i + 1

Once we have done this for all three categories, we can easily determine the sum of the rankings for each entry. We then sort the entries again, in ascending order of rank, with descending order of score as the tiebreaker (and lexicographical ordering of the names as a further tiebreaker).

The most difficult aspect of this problem is maintaining the data with all the repeated sorts. The easiest thing to do is probably to build objects, each of which hold the name, three scores, three rankings, and total ranking (or a method for computing that on the fly). These objects can then be rearranged by whatever sort routines one uses as much as one wants. Then all is left is properly defining the comparison function for each of the two types of sorting involved.

Value	350
Submission Rate	114 / 137 (83.21%)
Success Rate	73 / 114 (64.04%)
High Score	malpt for 327.38 points

Implementation

This problem can be modeled as a nondeterministic finite automaton (NFA). That is, we iterate through each sequence of keystrokes. At each keystroke, we are in some set of states (which for this problem is a set of positions in the target cheat code). For each keystroke, we iterate through each state and, for each state, find as many states that can be reached from that state using that keystroke as possible. These become part of the new set of states.

For instance, initially our set of states consists of only one state: the beginning of the cheat code. When we read a keystroke, we see if it matches the next character in the cheat code. If it does, then we know that advancing the position by one gives one possible next state. If that character is the same as the previous keystroke entered, then we can also ignore it, which means the current state is also a possible next state. And, we can also always go back to the beginning of the cheat code as the next state.

We can represent the set of current states as a simple bitmask (e.g., an array of boolean values), where the ith value of the bitmask specifies whether or not position i in the cheat code is reachable at this point. Initially, bitmask[0] = true while the rest is false. We then proceed through the keystrokes and generate a new bitmask. After we process the keystroke, we replace the previous bitmask with the new one. If the nth bit of the bitmask is ever true, where n is the length of the cheat code, then we have a valid entry of the cheat code.

The trick to this problem is understanding the model (that is, how to map it to an NFA, and what an NFA is). The implementation is actually rather easy.

Value	1000
Submission Rate	18 / 137 (13.14%)
Success Rate	14 / 18 (77.78%)
High Score	vorthys for 893.76 points

Implementation

To begin, we use the information provided to build a graph. Initially, we have a graph with no edges and a vertex for each of the num objects. Then, for each equivalence given, we construct an edge between the two objects. Once we have constructed this graph, we then identify how many connected components there are. This gives us the number of distinct values we are working with.

If there are n connected components, then there are at most n distinct values among our objects. However, there may be fewer distinct objects, because there may be equivalences that weren't given to us. So, if there are n connected components, then there are at least 1 and at most n equivalence classes. When the objects are put in order, equivalent objects will be adjacent, so we can just treat all equivalent objects as a single object. Thus the problem is reduced to counting the number of ways to order n objects when there are no equivalences given.

Now, we must keep in mind that there may exist equivalences that were not given to us. In other words, the number of equivalence classes is at least 1 and at most n, and we know nothing about them. We must count each case distinctly. For each choice for the number of equivalence classes, we must count the number of ways we can partition all of the objects into that many groups, as each partition arbitrarily assigns objects to equivalence classes. We then multiply that value by the number of possible ways we can order our equivalence classes (which is simply the factorial of the number of equivalence classes).

The number of possible ways we can partition a set of n objects into k groups is given by a Stirling number of the second kind. The preceding link gives an overview of this concept, but it essentially boils down to the following recurrence relation (for partitioning n items into k groups):

S(n, k) = k * S(n - 1, k) + S(n - 1, k - 1)
S(n, n) = S(n, 1) = 1

This is a simple recurrence relation to implement (using basic memoization techniques). So, if we have n connected components, then the solution to this problem is:

sum = 0;
for(long long i = 1; i <= n; i++)
    sum += factorial(i) * S(n, i);