Match Editorial

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 Problems

Value	250
Submission Rate	402 / 467 (86.08%)
Success Rate	374 / 402 (93.03%)
High Score	piyush___ for 249.69 points (0 mins 59 secs)
Average Score	202.42 (for 374 correct submissions)

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 point-size 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 inter-character pixels equal to one less than the number of characters in the sentence.

Value	500
Submission Rate	233 / 467 (49.89%)
Success Rate	166 / 233 (71.24%)
High Score	leiz for 438.13 points (10 mins 59 secs)
Average Score	247.60 (for 166 correct submissions)

Value	250
Submission Rate	301 / 333 (90.39%)
Success Rate	283 / 301 (94.02%)
High Score	Michael_Levin for 233.85 points (7 mins 34 secs)
Average Score	169.52 (for 283 correct submissions)

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):

wins[i]*games[j] < wins[j]*games[i]

Value	1000
Submission Rate	21 / 467 (4.50%)
Success Rate	16 / 21 (76.19%)
High Score	agray for 714.70 points (19 mins 40 secs)
Average Score	494.15 (for 16 correct submissions)

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²⁰ 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'.

Value	500
Submission Rate	135 / 333 (40.54%)
Success Rate	82 / 135 (60.74%)
High Score	misof for 397.80 points (15 mins 14 secs)
Average Score	270.79 (for 82 correct submissions)

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.

Value	1000
Submission Rate	7 / 333 (2.10%)
Success Rate	1 / 7 (14.29%)
High Score	misof for 451.71 points (45 mins 5 secs)
Average Score	451.71 (for 1 correct submission)

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!(n-k)!). Note that if k > n then choose(n,k) = 0.

Finally, the counts for each type of hand can be found as follows:

FIVE OF A KIND

Sum for each rank choose(rank[i],5)

ROYAL FLUSH

Sum for each suit, s, of the product of suit_ranks[s][i] with i from 10 to A

STRAIGHT FLUSH

Sum for each suit, s, of the number of straights flushes for that suit. Loop over the starting rank and take the product of the 5 ranks that make up the straight.

STRAIGHT

Similar to counting the number of straight flushes but use ranks[i] instead of suit_ranks[s][i] and also include straights starting with 10. Subtract the number of royal and straight flushes.

FLUSH

Sum for each suit, s, of choose(suits[s],5). Subtract the number of royal and straight flushes.

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].

FULL HOUSE

Sum for each pair of ranks, i and j, of choose(ranks[i],3)*choose(ranks[j],2). Subtract for each suit, s, choose(suit_ranks[s][i],3)*choose(suit_ranks[s][j],2).

FOUR OF A KIND

Sum for each pair of ranks, i and j, of choose(ranks[i],4)*choose(ranks[j],1). Subtract for each suit, s, choose(suit_ranks[s][i],4)*choose(suit_ranks[s][j],1).

THREE OF A KIND

Sum for each pair of ranks, i and j, of choose(ranks[i],3)*choose(deck_size-ranks[j],2). Subtract for each suit, s, choose(suit_ranks[s][i],3)*choose(suits[s]-suit_ranks[s][j],2). Subtract the number of full houses.

TWO PAIR

Sum for each pair of ranks, i and j, of choose(ranks[i],2)*choose(ranks[j],2)*(deck_size-ranks[i]-ranks[j]). Subtract for each suit, s, choose(suit_ranks[s][i],2)*choose(suit_ranks[s][j],2)*(suits[s]-suit_ranks[s][i]-suit_ranks[s][j]).

ONE PAIR

Sum for each quadruple of ranks, i, x, y, and z with x < y < z, of choose(ranks[i],2)*ranks[x]*ranks[y]*ranks[z]. Subtract for each suit, s, choose(suit_ranks[s][i],2)*suit_ranks[s][x]*suit_ranks[s][y]*suit_ranks[s][z].

NOTHING

choose(deck_size,5) - the counts of all other types of hands.