Here's the solution for the hard that I had in mind at the end of the contest:

- First, iterate over all possible
**cutoff**scores between 0 and 1000, and over**lastCutoff**(last person to score exactly cutoff points), between 1 and 25.

- For each such pair, calculate two arrays using DP:
- What is the probability that out of first
**x**persons, exactly**k**will advance (that means, score above**cutoff**, or equal to**cutoff**if their number is less than or equal to**lastCutoff**).

- The same for last
**x**persons.

- What is the probability that out of first
- In calculating those arrays, we make use of the fact that all scores are independent, so the DP is quite straightforward; we need to remember that we've already fixed the score of person
**lastCutoff**to**cutoff**(but this still has probability of 1/n, not 1).

- After we've got those arrays, let's calculate the probability of each person
**a**advancing, and being**b**-th highest ranked person in the finals. This is quite easy now: we need to multiply the probabilities of:**b**-1 people to advance from the first**a**-1 persons

**k**-**b**-1 people to advance from the last**totalPersons**-**a**persons

**a**-th person advancing. Here we need to keep in mind that if**a**is equal to**lastCutoff**, this should be the fixed 1/n probability since we're only interested in the case where he scores**cutoff**points.

- And finally we accumulate the above probabilities by semifinal number, to get the answer for the problem.

**timeOfInnerDP**)).

The good news is that I'll now have a lot of free time at the TCO and will do live commentary on all 3 remaining Algorithm rounds: Semifinal 2, Wildcard and Finals. I will post the commentary both here and on the TopCoder blog. Stay tuned :)

## No comments:

## Post a Comment