JOIN
 Match Editorial
SRM 229
Monday, January 31, 2005

Match summary

SRM 229 was quite a bit easier than 228, and in division 1, ten coders solved all three problems successfully. Top amongst them was Jan_Kuipers, finishing in around 35 minutes. Next in line was haha, who finished just a few minutes later. Rounding out the top 3 was marian, over 100 points behind haha.

In division 2, things were a little harder, as a tricky easy problem caused many coders to stumble, and the hard problem was hard enough that only 6 coders even submitted it. entaroadun took top honors as the only one to successfully submit all three problems. Helped by 200 points in the challenge phase, nidonido took second in his first competition, with succcessful submission on the medium and hard problems. Rounding out the top 3 was Philya, with solutions for the easy and medium problems.

# The Problems

Highscore
Used as: Division Two - Level One:
 Value 250 Submission Rate 170 / 202 (84.16%) Success Rate 46 / 170 (27.06%) High Score entaroadun for 243.13 points (4 mins 48 secs) Average Score 177.73 (for 46 correct submissions)

This problem tripped a lot of people up, as evidenced by the low success rate. In fact, it set a new record for the lowest success rate every by a division 2 easy - beating out the previous record holder by over 14%! Of the failed solutions I looked at, most of them ended up calculating the ranks of all the scores in the table, and then trying to figure out the rank of the new score. Some of them inserted the new score into the table, and then sorted the table, finding the new ranks. Both of these approaches are way more complicated than is neccessary. Instead, notice that the rank of a score is exactly equal to the number of scores that beat it, plus 1. So, if no one beats you, then you are in first, or else tied for first. If 3 people beat you, you are in fourth, or tied for forth. Hence, the rank of the new score can be calculated with a simple for loop:

```    int place = 1;
for(i = 0 to scores.length-1){
if(newScore < scores[i]){
place ++;
}
}
```
Now, if the place is greater than the number of spaces return -1. Also, there is the special case where the new score ties the bottom of the list, but the list is already full. Both of these are pretty simple to check for:
```    if(place == numPlaces+1)
return -1;
if(scores.length == numPlaces-1 && scores[numPlaces-1] == score)
return -1;
```

Cafeteria
Used as: Division Two - Level Two:
 Value 500 Submission Rate 88 / 202 (43.56%) Success Rate 48 / 88 (54.55%) High Score {rustam} for 439.82 points (10 mins 48 secs) Average Score 297.05 (for 48 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 202 / 217 (93.09%) Success Rate 171 / 202 (84.65%) High Score jshute for 242.61 points (4 mins 59 secs) Average Score 188.24 (for 171 correct submissions)

Coders had better luck with this problem and there are a couple of different ways to go about it. I think that the most straightforward and intuitive method is to work backwards from 2:30PM. First calculate the latest a bus could leave the bus stop and still arrive at 2:30PM. Then calculate the last time before or equal to that when the bus would actually leave, given its offset. Finally, calculate the time you would have to leave to get to the bus stop. Of all the bus stops, find the minimum time at which you would have to leave. If you represent all of your times as minutes past midnight (2:30PM = 14*60+30 = 870) it will make things relatively simple:

```    int time = 14*60+30;
time -= drivingtime[i];
time -=(time-offset[i])%10;
time -= walkingtime[i];
```
The only part that you have to think about a little is the one that deals with the offset, and there are other ways to do it, though they require more typing (a loop, for instance).

At the end, you just had to convert the time into a string, being careful to get the leading zeros in the right place, and making sure you do all the hours correctly (the 12 in particular).

SnowClearing
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 6 / 202 (2.97%) Success Rate 3 / 6 (50.00%) High Score nidonido for 507.92 points (36 mins 29 secs) Average Score 460.50 (for 3 correct submissions)

```    for each dead end at (row,column)
do
look for an intersection at (row,column) != theGarage
such that for exactly one intersection (row',column')
connected to (row,column), isDead(row',column') == false
if (an intersection is found)
while(an intersection (row',column') is found)
```
Now, there are a lot of different ways to actually implement this approach. One way, which I am fond of, is to create a large two-dimensional boolean array for isDead, and then just loop over all intersections as long as the while condition above is true. At the end, just count the number of locations for which isDead is set to true. This approach runs rather slowly, but its fast enough for this problem. Here is an approach that is much faster:
```    int[][] adjNonDeadCount = new int[rows][columns]
int[][] queue = new int[1000][2];
int head = 0, tail = 0;
for each intersection in the input at (row,column){
if((row,column) == theGarage){
queue[tail][0] = row;
queue[tail][1] = column;
tail++;
}else{
}
}
int[] dr = {0,1,0,-1};
int[] dc = {1,0,-1,0};
for(i = 0 to 3){
row' = row + dr[i];
column' = column + dc[i];
if((row',column') and (row,column) are connected &&
queue[tail][0] = row';
queue[tail][1] = column';
tail++;
}
}
}
}
}
return tail;
```

Used as: Division One - Level Two:
 Value 500 Submission Rate 176 / 217 (81.11%) Success Rate 92 / 176 (52.27%) High Score Jan_Kuipers for 483.67 points (5 mins 15 secs) Average Score 358.24 (for 92 correct submissions)

This problem requires a bit of dynamic programming, though it is on the easy side as far as dynamic programming problems go. The first important bit of information to glean from the problem statement is that the company can only work on one product at a time. So, all you need to do is maximize the total amount of money the company can have, at each time, assuming it has just finished a product. Let's say I have X dollars at time T. If I make product i, where expense[i] ≤ X, then I can have X+revenue[i]-expense[i] at time T+ptime[i]. Since I can't stop in the middle of making a product, and there is no reason to delay starting a new product once one is done, all I need to worry about is how much money I can have after just finishing a product. This leads to some elegantly short code:

```        int[] maxMoney = new int[10000000];
maxMoney[0] = C;
for(int i = 0;i<maxMoney.length ; i++){
if(maxMoney[i] >= D)return i;
for(int j = 0; j<expense.length; j++){
if(maxMoney[i] >= expense[j])
maxMoney[i+ptime[j]] = max(maxMoney[i+ptime[j]],
maxMoney[i]+revenue[j]-expense[j]);
}
}
return -1;
```
1,000,000 is always enough time, if it's possible, since no ptime is more than 10, and if it is possible, you must profit at least 1. Hence, if you are making a profit, you are doing so at a rate of at least 0.1 per time unit, and (D-C)/0.1 = 10*(D-C) < 1,000,000 when D-C < 100,000.

An alternative approach is to do dynamic programming to compute the earliest time at which a particular amount of money could be achieved. I think it's a little bit harder to do it this way, but some people have an easier time with it, and it does run faster in this case.
```        if (C>=D)
return 0;
int [] bestTime = new int[D+1];
for (int i=0; i<bestTime.length; i++){
bestTime[i] = INF;
}
bestTime[C] = 0;
for (int i=C; i<D; i++) {
for (int j=0; j<ptime.length; j++){
if (expense[j]>i)
continue;
int money = min(D,i+revenue[j]-expense[j]);
if (bestTime[money]>bestTime[i]+ptime[j])
bestTime[money] = bestTime[i]+ptime[j];
}
}
if(bestTime[D] == INF)return -1;
return bestTime[D];
```

Hangman42
Used as: Division One - Level Three:
 Value 1000 Submission Rate 25 / 217 (11.52%) Success Rate 11 / 25 (44.00%) High Score Jan_Kuipers for 682.83 points (21 mins 35 secs) Average Score 538.46 (for 11 correct submissions)

This is a classic sort of game theory problem. The basic approach used by most people is always the same: recursion + memoization. You have some game state, and you want to know, what should the player whose turn it is do in that game state. As intuition suggests, he should consider all of his options, and imagine what his opponent would do in each situation. When imagining what his opponent would do, he is applying recursion, because his opponent will have to do essentially the same thing, although with a different game state. So, in pseudocode, we have something like:

```    //returns the probability of winning from G
double winningProbability(gameState G){
if(G is a 'game over' state){
if(player whose turn it is won)
return 1;
else
return 0;
}
ret = 0
foreach(move M from gameState G){
tmp = 0, cnt = 0;
foreach(hidden word W consistent with previous moves){
gameState G' = G after move M where W is the hidden word
double d;
if(currentPlayer goes again)
d = winningProbability(G');
else
d = 1-winningProbability(G');
tmp += d;
cnt ++;
}
ret = max(ret,tmp/cnt);
}
return ret;
}
```
So, when considering a move, M, there is some set of potential hidden words that are consistent with the previous moves. In practice, this set can be easily implemented as a bitmask, and is all that is needed to know the game state. The moves in the game are guessing a letter and guessing a word. So, what the algorithm is doing is checking to see, if the current player makes a guess, M, and the hidden word is really W, what is the probability that the current player will win. Of course, this is one minus the probability that the other player will win. After considering each possible hidden word, the overall probability is computed for the move as a simple average of the probabilities for each word.

To avoid repeating the same calculations over and over again, and timing out, you should add the standard memoization code to the beginning and end of your code:
```    if(dp[G] exists)return dp[G];

...

dp[G] = ret;
return ret;
```

By lbackstrom
TopCoder Member