Wednesday, February 23, 2005 Match summary This match seemed to have a lot less challenges than other matches, but the systests were brutal for many coders, especially on the division 1 650 and 900. The top three slots in division 1 were taken by SnapDragon, tomek, and haha. In division 2, seven coders plowed their way through all three problems, with tomekW, palmcron, and dgott taking the top three slots. The ProblemsBritishCoinsUsed as: Division Two  Level One:
This problem is fairly straightforward, utilizing integer division and the modulus operator. First, note that there are 240 pence in a pound. Thus, pounds = pence / 240 (integer division). After that, we're left with pence % 240 (modulus operator) more pence. Then, divide the remaining pence by 12 to get the number of shillings. Take the remainder again, and that's the number of pence. Package those three values into an array, in that order, and we're done. WordFindUsed as: Division Two  Level Two: Used as: Division One  Level One:
The word search problem probably brought back the days of childhood, when we would do those puzzles in school, or just for fun. The requirement about how to deal with a word that appears more than once in the puzzle was hopefully a clue to how to proceed with the problem. If we search top to bottom, left to right, in each of the three directions, noting the location we find any of the words we're searching for, we know that we will always find the "first" match for any given word. We can optimize this a little by only checking words when we have a first character match, but given the size of the puzzle and the number of words, this was not necessary, and even a very unoptimized solution can run in time. StockHistoryUsed as: Division Two  Level Three:
The annotation on the last example of this problem was intended to not only clarify the goal of the problem, but was supposed to be a hint about how to proceed about coding a solution. With the requirement that we can only ever sell all of our holdings at the very end, the decision each month is only whether we should buy that month, or wait until some month in the future to buy. One solution works like this: work backwards from the end, and for each month, determine which stock offers the biggest percentage gain between that month and the end. Then, working from beginning to end, each month we either buy the best stock of that month or hold onto our money to buy the best stock in some future month, if it offers a better percentage return. Since we can buy fractional shares, we always invest all or nothing in a single best stock. Then, we do the same thing the next month, always picking either the best of the current month or any future month to invest all of our money for that month. Then, we simply total up our sales price, subtract out our initial investments, round off to the nearest integer, and we're done. CommunicableDiseaseUsed as: Division One  Level Two:
This problem was, in theory, representative of an experiment frequently done in high school biology classes to help demonstrate how quickly disease can spread. The biggest observation to make is that a small group of people can, after only a few contacts with others, result in many people becoming infected. Furthermore, once many people are infected, and have been in contact with several others, there is really no longer any way to trace the point(s) of origin. But, I digress... One efficient way to solve this problem is using bitmasks. You need to use a 64bit integer to hold the 50 bits (so be careful to use 1L << i, or the similar appropriate longtype declarator in your code) needed. Then, from round to round, use the bitmasks to keep track of whose samples are in whose vials. For instance, if vial #2 has bitmask 10110, then it contains solution from vials 0, 2 and 3. The bitwiseor operator is the key here. In pseudocode: mask[vial][round + 1] = mask[vial][round]  mask[donor1][round]  mask[donor2][round] ... Once you've calculated the final contents of each vial, you know that anyone who donated (directly or indirectly) to someone who ended noncontaminated, must have themselves begun the simulation noncontaminated. Taking the bitmasks of those who ended contaminated, and removing the bits corresponding to those vials known to have started negative leaves a bitmask of the potential contamination sources. If there's only one potential source, you know it was contaminated to begin with. If there's no potential source of the contamination, then you have invalid data. SalesPromotionUsed as: Division One  Level Three:
This problem had fewer submissions (and even fewer correct) than I would have suspected. I think part of the problem was a harder than usual medium leaving little time to work on the hard. Also, timeouts on large inputs, rounding errors, and a few other gotchas were all easy to do. It should come as no surprise that this is a dynamic programming problem. The DP is done in two dimensions, on total number of points used, and total number of half price items used. We can either keep track of the best possible total savings (in which case we initialize the array elements to 0) or the lowest total cost (in which case we initialize the array elements to some really high number). Then, we loop over each of the items, and work backwards through our array to check if adding the current item as half price or points will be better than our current best for the number of points and half price items. Working backwards is necessary to ensure we don't count the same item twice for points or half price. Then, since we have to use all of our points and half price items exactly, we just grab dp[points][halfPrice] to generate our result. 
