TopCoder Prediction Information

TopCoder’s rating system is designed based on the simplifying assumption that coders’ performances relative to each other can be modeled by considering each coder’s performance a random variable with a normal distribution. It is clear that this is simpler than reality, but over time each coder’s rating and volatility will nonetheless tend toward the mean and standard deviation, respectively, of his or her performance. Note that in the sense used here, “performance” is a hidden factor, not the actual score in competition. For the rating system, all that matters in competition is how coders perform relative to each other.

My simulations follow this exact model. Coders’ performances in each round are drawn from normal distributions with means and standard deviations equal to their respective ratings and volatilities. Since there is no fixed relationship between performance and score, there is no way to predict which coders will not receive a positive score based only on the rating system (this makes sense, because problem sets have varying levels of difficulty). Naturally, there is also no way to predict which coders, if any, will simply fail to show up. Thus, it is assumed that coders always receive a positive score and that all eligible coders for each round participate. Because performances are random doubles, ties are extremely unlikely and it is assumed that they will not occur (if they do, they will be broken arbitrarily).

Thus, a simulated round (other than the finals and the wildcard round) proceeds as follows:

1. Each coder is given a randomly generated performance.
2. In each room, the coder with the highest performance advances.
3. Of those remaining, those with the highest performances advance to fill the remaining spots in the next round.
4. The advancers are sorted by tournament seed (rating immediately prior to Round 1) to determine room placement in the next round.

A simulated tournament is the correct number of simulated rounds in a row, with the coders pre-sorted by seed for the first round.

The source code to my simulator is available for perusal. This is for the TCO 2003, and this is for the TCCC 2004. The latter has a special case for the wildcard round, plus some constants differ. It’s reasonably clean for a small personal project, but uncommented. There used to be a Java program here, but I converted the computational part to C++, which is why the identifiers and such look like they belong in a Java program.

Return to TopCoder Stuff.