Monday, August 8, 2005 Match summary With solid times on all three problems, Petr took first by over 100 points. tmyklebu had the best time one the hard problem by far, and despite a failed medium submission, he took second. kalinov took third thanks to a challenge. In division 2, sfcommand took first, followed by Minny and newcomer WSX. The ProblemsSubstitutionCodeUsed as: Division Two  Level One:
The simplest way to solve this problem was to look at each character in the code, starting from the first character, in order. As you go along, you keep an integer representing the value so far. If the character in the code is not in the key, you simply ignore it. Otherwise, you multiply the integer by 10, and add the number represented by the character. This is the standard way to parse numbers in any base: look at each character one at a time, multiplying by the base (10 in this case) and then adding each time. BridgePtsUsed as: Division Two  Level Two:
This problem was pretty straightforward. It's easy to add up the points for the jacks, queens, kings and aces. To add up the points for short suits, just count how many cards of each suit you have. TimeCardUsed as: Division Two  Level Three:
Working in 12 hour format is cumbersome. In these sorts of problems, it's typically best to convert the input format to a single integer, representing the number of minutes past midnight. The easiest way to do this is: int time = hour%12*60+minute; if(pm)time += 12*60;Once you have everything as an integer, it's easy to compute the duration between two time stamps: duration = (time2  time1 + 24*60)%(24*60);Adding up all the durations, you can figure out how many more minutes you need to reach 40 hours (or that this is impossible, in which case you return one of the two special cases). If you need minutes more minutes to reach 40 hours, and the last time is in last_time, then you can get off work at ret = (minutes + last_time) % (24*60) minutes past midnight. Finally, you need to convert this to the appropriate return format. You can compute the appropriate parts as follows: int hours = ret/60%12; if(hours == 0)hours = 12; int minutes = ret%60; boolean pm = ret >= 12*60;Predicting Used as: Division One  Level One:
Many coders missed the part of the problem that said that the weights must add up to exactly 1. Assuming you saw that, the problem wasn't too bad. Since you always predict from exactly 5 previous values, you can easily solve this with 4 nested loops, each going from 1 to +1 in increments of 0.1. You can calculate the 5^{th} weight as d5 = 1d1d2d3d4. Assuming that this fifth weight is between 1 and +1, inclusive, you can compute the weighted average for each of the values beyond the fifth, and find the average error as described. StockQuotesUsed as: Division One  Level Two:
The parts of the return corresponding to the exchanges are relatively simple to
calculate. Each new quote corresponds to a change in the quote, so the COUNT
part of the return is just the number of times that the exchange appeared in the
input. The average spread for an exchange is also pretty easy to calculate,
since it's just a simple average over the spread from the input for that exchange. Used as: Division One  Level Three:
There are a few different ways you can do the dynamic programming for this
problem. Since tmyklebu had the highest score, I'll describe a solution similar
to his. First, observe that each computer must have at least minInComp
processors. So, we can immediately remove minInComp*amount
processors, and reduce minInComp to 0, to get an equivalent problem.
Now, there are two basic cases that we need to handle. We can have some positive
number of computers with 0 processors (minInComp processors in the
original problem). Alternatively, we can have 0 computers with 0
processors, in which case the minDif doesn't come into play, as we could
have computers with just 1 processor. In the first case, we will account for
some of the computers and assign a number of processors to them. In this case,
the remaining computers must have at least minDif processors (the ones we
just assigned had 0 processors), so we
subtract that many processors and recurse. In the
second case, where we have 0 computers with 0 processors, all of the computers
must have at least 1 processor. In this case, we can subtract 1 processor for
each computer that we must make, and we still need to make the same number of
computers. In both cases, the key realization is that the answer to
choices(n,minDif,minInComp,amount) is the same as the answer to
choices(nminInComp*amount,minDif,0,amount), assuming that 0 is an acceptable
value for minInComp. //go() returns the number of ways to make amount //computers with n processors, assuming that the //minimum number of processors per computer is 0 long go(int n, int amount){ //too few processors, return 0 if(n<0)return 0; //1 way to assign 0 processors to the computers  //0 processors to each one if(n==0)return 1; //all computers assigned, but extra processors if(amount == 0)return 0; long ret = 0; //assign 0 computers with 0 processors. Each //computer must have at least one processor. //Same as namount processors for amount computers ret += go(namount,amount); for(int i = 1 ;i<=amount;i++){ //assign i computers to have 0 processors. The //other amounti computers must have at least minDif //processors, so subtract (amounti)*minDif from n, //and i from amount and recurse. ret += go(n(amounti)*minDif,amounti); } return ret; } long choices(int n, int minDif, int minInComp, int amount) { return go(nminInComp*amount,amount); }As you'd expect, you need to memoize your recursive function to make it run within the time limit. This is just standard dynamic programming though, and you can just use a 2D array. 
