Tuesday, September 27, 2005 Match summary As a few of the Google Code Jam finalists were still making their way back to their respective homes, SRM 265 started early tuesday morning. In fact the top four placers were also finalists: ploh in fourth, venco taking third, Petr in second, and solving all three misof in first. They, as well as the other top three finishers in each room, were also awarded with a cash prize which gave further incentive to compete in the early match. The competition in division 2 was also fierce with 12 coders solving all three problems and the top two finishers in each room winning a prize. agray won the division and advances to division 1 for the first time, seliv took second, and competing for the first time bertas took third. The ProblemsFontSizeUsed as: Division Two  Level One:
This problem demonstrates an excellent use of a table. Typically the size of each character depends on which font face is used, whether the font is bold or italic, and the pointsize of the font. Modern fonts don't actually keep an image of each character but rather a mathematical description that can be used to calculate how to draw it at different sizes. In cases where these calculations can be time consuming it is a good idea to just draw each character once into a table. For this problem the entire character isn't drawn into a table, but the width of each character is. Thus to determine the width of a string you simply need to look each character up in the table and add its width to the running total. The only complications are dealing with uppercase letters, lowercase letters, and the space character separately. Finally you can add a number of intercharacter pixels equal to one less than the number of characters in the sentence. ScheduleStrengthUsed as: Division Two  Level Two: Used as: Division One  Level One:
Most sports have a way to break ties that will determine which team makes the play offs, but usually they are never used. Truthfully, how many of you know exactly how to determine who will advance to the finals of the TCO in case of a tie? In American football, however, since the season is only 16 games, ties are a common occurence allowing strength of schedule to come into play. This problem, although somewhat complex, is straight forward. As long as you follow each direction in the problem statement (which may require reading and rereading to get the details right) you can solve the problem. The first step is to calculate for each team their opponent's cumulative winning percentage. To do this simply count the number of wins and total number of games which a) are by a team that played the current team and b) are for a game that did not involve the current team. Once you have these two numbers then you know their opponent's cumulative winning percentage is wins/games. Now you can sort each team first on its opponent's winning percentage and secondly on the team's name. Here you must be careful how you do the sort if you are using floating point numbers. In this problem it's not too difficult to avoid floating point numbers by using the standard way to compare rational numbers (assuming wins[i] and games[i] are those used for calculating team i's opponent's cumulative winning percentage): PipePuzzle Used as: Division Two  Level Three:
It turns out that as you follow the flow of water you only need to make a decision as to how to place the 'L' pipes. If you encounter either a '' or a '+' then you can always place it such that the pipe is aligned along the direction that the water flows. Since there can be at most 20 'L' pipes there are at most 2^{20} paths. This is small enough that you can follow each path and count the number of pipes used. First start off at the square that contains the water source and keep track of which direction the water is flowing. Then move to the next square based on what the current direction is. If you've moved off the grid or onto the source then you know that the path has ended. Otherwise check that you haven't used the current pipe and then mark it used unless it is a '+' (the only pipes you can use more than once are the '+' pipes). If the current pipe is a '+' then change it to a '', since using one direction allows the other direction to be used (also note that you can never enter a pipe along the same direction since that would imply a cycle in the path, but there can't be a cycle since the source can never be entered). When the current pipe is '' or '+' then the direction of the water doesn't change so the next pipe will be in that direction. If the current pipe is 'L' then the path will split; it can either change the direction to turn right or left. You can then add one to the current path length and recursively follow the path to the next pipe. Once the path has ended, retrace it backwards marking the pipes unused and following the other direction as you come back to each 'L'. RecipeUsed as: Division One  Level Two:
The first complication to this problem is that each ingredient is given with different units, so it becomes easier to solve if they are all converted into a standard unit, the teaspoon. This is quite similar to how in many of the problems with time in hours, minutes, and seconds it is almost always easier to just convert everything into seconds. Now we can ask, given a recipe, what is the smallest amount that we can make and still keep them in proportion to each other. Let's name this smallest amount the minimum serving. Since the smallest measuring device we have is a teaspoon, the minimum serving will have to have an integral number of teaspoons of each ingredient. There is some number G>=1 such that if we make G minimum servings then we get the same amount as the original recipe, but what is not so obvious is that G is an integer. If G is not an integer then let H be the smallest integer less than G. We can make the original recipe and then take out H minimum servings and have some amount that is a fraction of the minimum serving yet still has each ingredient in proportion. This contradicts the definition of minimal serving, so G must be an integer. Since we can make G minimum servings to equal the original recipe, G must divide each ingredient. Conversely, if an integer d divides each ingredient in the original recipe then we can split each ingredient in the original recipe into d piles and make d batches of some serving amount with each ingredient still being used in the same proportion. Thus since G is a common divisor and each common divisor can make a serving of some size, the smallest serving will correspond to the largest common divisor. Therefore G is the greatest common divisor of all the ingredients. Now that the hard part is done, the next task is to determine how much to make. We must make some multiple of the minimum serving, and further we must make at least G minimum servings. Now we can loop through each ingredient in the bowl and determine the smallest number of minimum servings needed to fully use that ingredient by division rounding up; we must make a number of minimum servings equal to the maximum of these numbers. After knowing how much to make, it is a simple manner to loop through each ingredient and determine how much more to add to the bowl. Convert this into the most cups possible, then the most tablespoons, and keep the rest in teaspoons. PokerDeckUsed as: Division One  Level Three:
One of the things that makes a good poker player is being very familiar with the odds of making certain hands. Changing up the composition of cards or rules of the game (Such as having a full house less than a flush) can upset their game and even the playing field. Overall, this is a combinatorial problem. Instead of calculating the probability of each type of hand, we can count the number of hands which are that type. Once we know the counts, we can sort based on the count and break ties by the name of the type. Calculating the counts is not an easy task, and it can be simplified by how the data is represented. One way is to keep a few arrays: int ranks[13]; // ranks[i] = number of cards in the deck of rank i int suits[4]; // suits[i] = number of cards in the deck of suit i int suit_ranks[4][13]; // suit_ranks[i][j] = number of cards in the deck of suit i and rank j By reading the input, these arrays can be filled. During the calculating we will also need to calculate some binomial coefficients. choose(n,k) is the number of ways of selecting k items from a collection of n items. This can be calculated as n!/(k!(nk)!). Note that if k > n then choose(n,k) = 0. Finally, the counts for each type of hand can be found as follows:
The idea from here is to count each type of hand once using ranks[i] and then to subtract all of that type hand which would be flushes by using suit_ranks[s][i].

