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. |
| |
Definition |
| | | Class: | ChessMatch | | Method: | bestExpectedScore | | Parameters: | int[], int[], int | | Returns: | double | | Method signature: | double bestExpectedScore(int[] teamA, int[] teamB, int lim) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Your return must have an absolute or relative error less than 1e-9. |
| |
Constraints |
| - | 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. |
| |
Examples |
| 0) | |
| | {2239,2412,2399,2267} | {2534,2429,2340,2389} | 100 |
| 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.
|
|
|
| 1) | |
| | {2239,2412,2399,2267} | {2534,2429,2340,2389} | 150 |
| 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}.
|
|
|
| 2) | |
| | | Returns: 1.9936953816334797 | teamA is superior, but the ordering still matters slightly.
|
|
|
| 3) | |
| | {1786,2080,2156,2132,2187,2380,2191} | {1885,1851,1743,1714,2338,2167,1789} | 1500 |
| 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}.
|
|
|
| 4) | |
| | {1868,1797,2213,2085,1611,2002,2167,1908,
1773,1834,1766,2245,1582,2009,2233,2030} | {2138,2259,2109,2160,2295,2022,2043,2131,
1655,1716,1648,1779,1518,1570,1560,1677} | 200 |
| Returns: 9.229777079272512 | |
|