Match Editorial

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

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.

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-1^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 n-1^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(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