JOIN
 Match Editorial
2005 TopCoder Collegiate Challenge
Qualification Problem Set 5

January 11-12, 2005

Summary

The results for this set were close. Im2Good got the top score, but 16 other competitors had scores within 100 of his.

The 250 was a simple simulation problem. The 1000 was a probability/dynamic programming problem.

Partially because of sample data on the 250 that omitted some cases, many competitors ended up with a total score of 0 and a positive score was enough to qualify on this set .

# The Problems

TimeOfPossession
Used as: Division One - Level One:
 Value 250 Submission Rate 141 / 168 (83.93%) Success Rate 78 / 141 (55.32%) High Score robymus for 239.51 points (4 mins 48 secs) Average Score 173.75 (for 78 correct submissions)

The sample input for this problem didn't include cases in which B started with the ball, or in which a posession change other than a "SWITCH" happened during the game, which tripped some competitors up. Aside from lack of sample input for all cases, this problem is straightforward.

Because of the note about multiple events, we know that the events are given in the order in which they happen. This means that we can go through the events in order, keeping track of which team posesses the ball after each event, and add up the segments of time during which team A has the ball.

A simple way to represent times is in seconds since the game started, which can be calculated from the clock time mm:ss as mm*60 + ss.

NestedRandomness
Used as: Division One - Level Three:
 Value 1000 Submission Rate 101 / 168 (60.12%) Success Rate 63 / 101 (62.38%) High Score Im2Good for 954.91 points (4 mins 59 secs) Average Score 710.61 (for 63 correct submissions)

The chance of getting the result x on a single call to randomInt(N) is 1/N for x | 0 ≤ x < N, or 0 otherwise.

Now consider nested calls. The result of a call depends on the result of earlier calls to randomInt. For example, if the first call to randomInt returns 5, then there is no chance of the second call returning 6.

On the nth call, the chance of the result being x depends on the result, r, of the n-1st call. If x ≥ r then there is no chance of randomInt(r) returning x. Otherwise the chance is 1/r. This means that in order to calculate the chance of getting x on the nth call to randomInt, we need to sum the probability of getting x over all possible return values, r, from the n-1st call.

As a recurrence, C(n,x), the chance of x being the result from the nth call to randomInt, can be expressed:

C(n,x) = (sum from i = x+1 to n of C(n-1, i)/i)

The table C can be built using dynamic programming:

```/* Initialize the table with the probabilities
* for the first call to randomInt */
for(int x = 0; x < N; x++)
chance[0][x] = 1.0/N;

/* Build the rest of the table using the recurrence for C */
for(int n = 1; n < nestings; n++)
for(int x = 0; x < N; x++)
for(int k = x+1; k < N; k++)
chance[n][x] += chance[n-1][k]/k;

/* Return the chance of the result being target */
return chance[nestings-1][target];
```

The algorithm above is O(N*N*nestings), which is small enough that it easily runs in 8 seconds for N = 1000 and nestings = 10. It is possible, however, to write an algorithm that runs in O(N*nestings). Notice that C(n,x) - C(n,x+1) = C(n-1, x+1)/(x+1). This suggests the following replacement for the nested loops in our algorithm:

```for(int n = 1; n < nestings; n++)
for(int x = N-n; x >= 0; x--)
chance[n][x] = chance[n][x+1] + chance[n-1][x+1]/(x+1);
```

By kaylin
TopCoder Member