Match Editorial

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 Problems

Value	250
Submission Rate	216 / 228 (94.74%)
Success Rate	207 / 216 (95.83%)
High Score	supernova for 248.98 points (1 mins 49 secs)
Average Score	229.59 (for 207 correct submissions)

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.

Value	500
Submission Rate	131 / 228 (57.46%)
Success Rate	73 / 131 (55.73%)
High Score	logged for 442.97 points (10 mins 28 secs)
Average Score	286.32 (for 73 correct submissions)

Value	250
Submission Rate	166 / 172 (96.51%)
Success Rate	139 / 166 (83.73%)
High Score	SnapDragon for 245.38 points (3 mins 54 secs)
Average Score	204.07 (for 139 correct submissions)

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.

Value	1000
Submission Rate	32 / 228 (14.04%)
Success Rate	15 / 32 (46.88%)
High Score	palmcron for 602.63 points (27 mins 11 secs)
Average Score	470.46 (for 15 correct submissions)

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.

Value	650
Submission Rate	54 / 172 (31.40%)
Success Rate	21 / 54 (38.89%)
High Score	tomek for 507.61 points (16 mins 0 secs)
Average Score	373.93 (for 21 correct submissions)

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 64-bit integer to hold the 50 bits (so be careful to use 1L << i, or the similar appropriate long-type 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 bitwise-or 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 non-contaminated, must have themselves begun the simulation non-contaminated. 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.

Value	900
Submission Rate	41 / 172 (23.84%)
Success Rate	7 / 41 (17.07%)
High Score	marian for 709.62 points (15 mins 36 secs)
Average Score	588.07 (for 6 correct submissions)

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.