JOIN
 Match Editorial
SRM 257
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 Problems

SubstitutionCode
Used as: Division Two - Level One:
 Value 250 Submission Rate 315 / 340 (92.65%) Success Rate 291 / 315 (92.38%) High Score kissaki for 249.31 points (1 mins 30 secs) Average Score 212.81 (for 291 correct submissions)

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.

BridgePts
Used as: Division Two - Level Two:
 Value 500 Submission Rate 297 / 336 (88.39%) Success Rate 238 / 297 (80.13%) High Score RNGAN for 492.35 points (3 mins 33 secs) Average Score 376.81 (for 238 correct submissions)

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.

TimeCard
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 139 / 340 (40.88%) Success Rate 33 / 139 (23.74%) High Score Minny for 738.74 points (18 mins 18 secs) Average Score 507.17 (for 33 correct submissions)

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:
 Value 300 Submission Rate 240 / 319 (75.24%) Success Rate 171 / 240 (71.25%) High Score antimatter for 290.16 points (5 mins 16 secs) Average Score 209.65 (for 171 correct submissions)

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 5th weight as d5 = 1-d1-d2-d3-d4. 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.

StockQuotes
Used as: Division One - Level Two:
 Value 450 Submission Rate 185 / 319 (57.99%) Success Rate 61 / 185 (32.97%) High Score m00tz for 381.52 points (12 mins 30 secs) Average Score 265.44 (for 61 correct submissions)

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.

The information corresponding to the inside quote is a bit more difficult to calculate. To calculate the inside quote, you need to keep track of the most recent quote from each of the exchanges that have issued at least one quote. The inside quote can be calculated from this information as described in the problem, by finding the highest bid and the lowest ask. After each new quote, you should recalculate the inside quote and see if it changed. If it changes, include that spread as part of the average spread, and increment the count.

Finally, you need to be particularly careful about the rounding mode you use for rounding your return to 2 digits. The default rounding mode in many methods is to round 0.005 towards the even number, not just up. Many solutions failed because they rounded 0.625 to 0.62 instead of 0.63.

Computers
Used as: Division One - Level Three:
 Value 1000 Submission Rate 32 / 319 (10.03%) Success Rate 19 / 32 (59.38%) High Score tmyklebu for 941.65 points (7 mins 9 secs) Average Score 585.31 (for 19 correct submissions)

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(n-minInComp*amount,minDif,0,amount), assuming that 0 is an acceptable value for minInComp.

So, our basic recurrence goes as follows:

```    //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 n-amount processors for amount computers
ret += go(n-amount,amount);
for(int i = 1 ;i<=amount;i++){
//assign i computers to have 0 processors.  The
//other amount-i computers must have at least minDif
//processors, so subtract (amount-i)*minDif from n,
//and i from amount and recurse.
ret += go(n-(amount-i)*minDif,amount-i);
}
return ret;
}
long choices(int n, int minDif, int minInComp, int amount) {
return go(n-minInComp*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.

By lbackstrom
TopCoder Member