Wednesday, July 9, 2003 Match summary 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 todate. 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. The ProblemsMarginCalculatorUsed as: DivisionII, Level 1:
ImplementationTo begin, we parse the values provided by each entry of the input array. We
can do this with a simple tokenizer (such as a 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
Used as: DivisionII, Level 2:
ImplementationThis problem is a simple string transformation that can be done inplace. 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. ContestScoreUsed as: DivisionII, Level 3: Used as: DivisionI, Level 2:
ImplementationThis 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 (1based) index in the sorted list. E.g.
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. CheatCodeUsed as: DivisionI, Level 1:
ImplementationThis 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, 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. Used as: DivisionI, Level 3:
ImplementationTo 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 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):
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); 
