
Match Editorial 
2005 TopCoder Collegiate Challenge
Qualification Problem Set 5January 1112, 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 n1^{st} 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 n1^{st} call.
As a recurrence, C(n,x), the chance of x being the result from
the n^{th} call to randomInt, can be expressed:
C(n,x) = (sum from i = x+1 to n of C(n1, 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[n1][k]/k;
/* Return the chance of the result being target */
return chance[nestings1][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(n1, 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 = Nn; x >= 0; x)
chance[n][x] = chance[n][x+1] + chance[n1][x+1]/(x+1);
By kaylin
TopCoder Member