TopCoder problem "KingOfTheCourt" used in SRM 222 (Division I Level Three)

Problem Statement

You and several friends are playing a tennis game called king of the court. The idea behind the game is that one person is the "king of the court", and each of the other players, in turn, tries to win two points before the king wins one point. An opponent who successfully scores two points without allowing the king to score becomes the new king of the court; otherwise, he returns to the back of the line to wait to play again. When the king is defeated, the winner becomes the new king, and the king returns to the back of the line. A player is declared the winner when he or she has been the king and consecutively defeated each of the other opponents.

You are given a int[] ability, where each element of ability is the relative skill level of each given player. The first element of ability refers to the player who is king initially. The remaining players are lined up to play, in the same order that they appear in ability.

On any given turn, the probability that a player A will win the point against player B is based upon their relative skill level. Thus, if two players have skill levels A and B, the probability that the first player will win the point (regardless of who is king) is A/(A+B).

You are to return a double indicating the probability that the player who is king initially will go on to win the game.

Definition

Class:	KingOfTheCourt
Method:	chancesOfWinning
Parameters:	int[]
Returns:	double
Method signature:	double chancesOfWinning(int[] ability)
(be sure your method is public)

Notes

At the start of the game, the king has not yet defeated any opponents.

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

Constraints

ability will contain between 2 and 7 elements, inclusive.

Each element of ability will be between 1 and 99, inclusive.

Examples

{ 1, 1 }

Returns: 0.8

Here, it is just you and a friend of the same ability. So, on any given point either of you has a 50% chance of winning. Thus, on each round, whoever is king has 75% odds, and the non-king has 25% odds.

Thus, there is a 75% chance you win the game on the first round, or a 25% chance that you go to another round, at which point there's a 25% chance of you once again becoming king. This suggests the following equation, where p is the probability that you win the game:

p = .75p + .25 * .25p

Solving, we get p = 80%

{ 2, 1 }

Returns: 0.9350649350649349

Here, you are twice as good as your friend, so the chances of you winning a round as king are 8/9. Your chances of winning while not king are 4/9. In an equation similar to above:

p = (8/9) * p + (1/9) * (4/9) * p

Solving, we get p = 72 / 77

{ 1, 2 }

Returns: 0.5844155844155844

Here, your friend is better than you. But, starting as king gives you some advantage.

p = (5/9) * p + (4/9) * (1/9) * p

Solving, we get p = 45 / 77

{ 1, 1, 1, 1 }

Returns: 0.5065812082824602

Now it's you with three other friends. Note that even though you're all of equal ability, starting as king provides a serious advantage.

{ 47, 82, 65, 99, 2, 14, 9 }

Returns: 0.22734781036506918

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3440

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5868&pm=3440

Writer:

timmac

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Advanced Math, Simulation, Sorting