X
Xerxes1986
I am trying to figure out this problem from TopCoder.com. The problem
is from a past competition that I am just trying to solve to help
increase my knowledge of Java. The problem is as follows:
"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."
And I have written the following code so far:
public class ChessMatch
{
public void main(String[] args)
{
}
public double bestExpectedScore(int[] my_team, int[] their_team, int
limit)
{
double bestScore = 0.0;
int[] my_team_ordered = new int[my_team.length];
for (int i=0; i < my_team.length; i++)
{
my_team_ordered = maxInArray(my_team);
for (int x=0; x < my_team.length; x++)
{
if (my_team[x] == my_team_ordered)
my_team[x] = 0;
}
}
my_team = my_team_ordered;
int[] is_movable = new int[my_team.length];
int[] not_movable = new int[my_team.length];
for (int i=0; i < is_movable.length; i++)
{
is_movable = 0;
not_movable = 0;
}
for (int i=0; i < my_team.length; i++)
{
for (int j=0; j < my_team.length; j++)
{
if (j > i)
{
if (my_team <= my_team[j] + limit)
{
for (int x = i; x < j+1; x++)
is_movable[x] = 1;
}
}
}
}
int numMovable = 0;
for (int i=0; i < is_movable.length; i++)
numMovable += is_movable;
int possibleCombos = 1;
for (int i=numPossibilities; i > 0; i--)
possibleCombos *= i;
if (possibleCombos == 1)
bestScore = ExpectedScore(my_team, their_team);
else
{
//Can't figure out where to go from here
}
return bestScore;
}
private double Score(int player_a, int player_b)
{
return (1.0/(1.0 + Math.pow(10, ((player_b - player_a)/400.0))));
}
private double ExpectedScore(int[] my_team, int[] their_team)
{
double result = 0.0;
for (int i=0; i < my_team.length; i++)
result += Score(my_team, their_team);
return result;
}
private int maxInArray(int[] array)
{
int result = array[0];
for (int i=1; i < array.length; i++)
{
if (array > result)
result = array;
}
return result;
}
}
I think that everything is done correctly in this code. The part where
I am stuck is in the "else" statement outlined in the code by the
comment. What I need to do is find all combinations for the order of
the team. Once that is done I can finish the program because I already
have the scoring methods set up. How would I go about finding how the
teams can be ordered?
I know how I would do it if the is_movable array looked like {1, 1, 1,
1, 1} or {1, 1, 1, 0, 0, 0} etc where there is only one group of
movable players but what if the is_movable array looked like this :
{1,1,1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0} ?? Any insight would be
awesome...THANKS
is from a past competition that I am just trying to solve to help
increase my knowledge of Java. The problem is as follows:
"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."
And I have written the following code so far:
public class ChessMatch
{
public void main(String[] args)
{
}
public double bestExpectedScore(int[] my_team, int[] their_team, int
limit)
{
double bestScore = 0.0;
int[] my_team_ordered = new int[my_team.length];
for (int i=0; i < my_team.length; i++)
{
my_team_ordered = maxInArray(my_team);
for (int x=0; x < my_team.length; x++)
{
if (my_team[x] == my_team_ordered)
my_team[x] = 0;
}
}
my_team = my_team_ordered;
int[] is_movable = new int[my_team.length];
int[] not_movable = new int[my_team.length];
for (int i=0; i < is_movable.length; i++)
{
is_movable = 0;
not_movable = 0;
}
for (int i=0; i < my_team.length; i++)
{
for (int j=0; j < my_team.length; j++)
{
if (j > i)
{
if (my_team <= my_team[j] + limit)
{
for (int x = i; x < j+1; x++)
is_movable[x] = 1;
}
}
}
}
int numMovable = 0;
for (int i=0; i < is_movable.length; i++)
numMovable += is_movable;
int possibleCombos = 1;
for (int i=numPossibilities; i > 0; i--)
possibleCombos *= i;
if (possibleCombos == 1)
bestScore = ExpectedScore(my_team, their_team);
else
{
//Can't figure out where to go from here
}
return bestScore;
}
private double Score(int player_a, int player_b)
{
return (1.0/(1.0 + Math.pow(10, ((player_b - player_a)/400.0))));
}
private double ExpectedScore(int[] my_team, int[] their_team)
{
double result = 0.0;
for (int i=0; i < my_team.length; i++)
result += Score(my_team, their_team);
return result;
}
private int maxInArray(int[] array)
{
int result = array[0];
for (int i=1; i < array.length; i++)
{
if (array > result)
result = array;
}
return result;
}
}
I think that everything is done correctly in this code. The part where
I am stuck is in the "else" statement outlined in the code by the
comment. What I need to do is find all combinations for the order of
the team. Once that is done I can finish the program because I already
have the scoring methods set up. How would I go about finding how the
teams can be ordered?
I know how I would do it if the is_movable array looked like {1, 1, 1,
1, 1} or {1, 1, 1, 0, 0, 0} etc where there is only one group of
movable players but what if the is_movable array looked like this :
{1,1,1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0} ?? Any insight would be
awesome...THANKS