TopCoder problem "ChessMatch" used in TCCC05 Round 1 (Division I Level Three)

Problem Statement


Just before a chess match between two teams, each team's coach secretly determines an ordering of his team's players. The first players in each team then get to play against each other, the second players in each team play against each other, etc. The team with the most wins will win the match.

You are the coach for one of the teams, and you have somehow managed to find out the order of the players in the other team. Based on that, you want to order your players so that your team's expected score is maximized to your advantage. The expected score of a single game can be calculated by the following formula (which is directly derived from how the international chess rating system works):

EA = 1 / (1 + 10 (RB - RA)/400)

EB = 1 / (1 + 10 (RA - RB)/400)

where RA and RB are the ratings of player A and B, and EA and EB are the expected scores for each player. For instance, if RA is 2432 and RB is 2611, the expected score for player A is 1 / (1 + 10 179/400) = 0.263005239459. The expected score for a team is the sum of the expected scores for the players in that team.

To make things a bit more complicated, the players in a team must be ordered such that a player with rating x plays before all players with rating strictly less than x - lim, where lim is a given non-negative integer. For example, if lim is 100, a player with rating 2437 must play before a player with rating 2336 but not necessarily before a player with rating 2337.

Create a class ChessMatch containing the method bestExpectedScore which takes a int[] teamA, the ratings of your players (in no particular order); a int[] teamB, the ratings of your opponent's players in the order they will play; and an int lim, the limit determining how freely you can order your players. You can assume that your opponent's players will be ordered in accordance with lim. The method should return a double, your team's expected score if you order your players optimally.



Parameters:int[], int[], int
Method signature:double bestExpectedScore(int[] teamA, int[] teamB, int lim)
(be sure your method is public)


-Your return must have an absolute or relative error less than 1e-9.


-teamA will contain between 1 and 20 elements, inclusive.
-teamB will contain the same number of elements as teamA.
-Each element in teamA and teamB will be between 1500 and 3000, inclusive.
-lim will be between 0 and 1500, inclusive.
-teamB[i] + lim will be equal or greater than teamB[j] for j>i.


Returns: 1.4835736078879815

There are only four possible ways to order the players in teamA so that the constraints are fulfilled. These are:

{2399,2412,2239,2267}   Expected score: 1.48040986...
{2399,2412,2267,2239}   Expected score: 1.48357361...
{2412,2399,2239,2267}   Expected score: 1.47815348...
{2412,2399,2267,2239}   Expected score: 1.48131723...

Note that if we could order the players in teamA freely, the best way would have been to order them in reverse rating order, {2239, 2267, 2399, 2412}. However, this is not allowed, since 2239 and 2267 aren't allowed to appear before 2399 and 2412 as the difference is greater than the limit of 100.

Returns: 1.5332458652994558

The players are the same as in the previous example, but the limit has been increased to 150, and a couple of more orderings are now possible. The best one is {2267, 2412, 2399, 2239}.

Returns: 1.9936953816334797

teamA is superior, but the ordering still matters slightly.

Returns: 5.227676657319362

Since the limit is 1500, any ordering of the players is possible. The best one is {2191, 2187, 2132, 2080, 1786, 2380, 2156}.

Returns: 9.229777079272512

Problem url:

Problem stats url:




PabloGilberto , lbackstrom , vorthys

Problem categories:

Dynamic Programming, Search