TopCoder problem "ChipRace" used in SRM 199 (Division I Level Two)

Problem Statement


Poker tournaments are usually played with chips of various denominations. For the purpose of this problem, assume that $5 and $25 chips are in play. At a predetermined time in the tournament, the $5 chips are removed from play and traded up for the equivalent value of $25 chips. For example, if a player has ten $5 chips, these would be replaced by two $25 chips. This is fine, as long as the number of $5 chips held by each player is a multiple of 5. However, it is likely that players will have a few chips left over after trading in their $5 chips in multiples of 5. These remaining chips are called "odd chips", and there are several way to deal with these. One method is to hold a "chip race".

To begin the chip race, the dealer determines the total number of $25 chips that will be awarded, by counting all the odd chips and dividing by 5 (rounding to the nearest integer). Then, the deck of cards is shuffled, and each player receives one card face up for each of his odd chips. The player with the highest card on the table is awarded one $25 chip, and then his cards are collected and removed. Then, the player with the highest card remaining is awarded the next $25 chip (if there are more than one), and his cards are collected and removed. This is repeated until all of the $25 chips have been awarded. Note that each player can win at most one $25 chip.

A standard deck consists of 52 cards, with 13 values and 4 suits. This is not important for this problem. Assume that the deck of cards consists of 52 unique cards, numbered 1 through 52.

For example, if there are five players, with 2, 3, 1, 0, and 2 odd chips, and if they are dealt the following cards:

    player  odd chips  cards
    ------  ---------  -------
    1       2          49, 35
    2       3          2, 24, 4
    3       1          27
    4       0
    5       2          3, 15

The total number of odd chips is 8, so two $25 chips would be awarded. Player 1 has the highest card (a 49), and would receive the first $25 chip. After his cards are removed, player 3 has the highest remaining card (a 27), and would receive the second $25 chip. Notice that even though player 1 initially had the first and second highest card, he still is only awarded a single chip. Players 2, 4, and 5 receive nothing.

Curious players may question the fairness of this technique. You are to answer such questions by writing a method to compute each player's probability of winning a chip in the chip race. You will be given a int[] chips, which contains the number of odd chips held by each player, and are to return a double[] with each player's probability of winning a chip. The returned double[] should have the same number of elements as chips, and element i of the returned double[] should correspond to element i of chips.



Method signature:double[] chances(int[] chips)
(be sure your method is public)


-The number of $25 chips awarded is equal to the total number of odd chips divided by 5 (rounded to the nearest integer).
-No player can win more than one $25 chip.
-Each element of the returned double[] must have an absolute or relative error of no more than 1e-9.


-chips will contain between 1 and 10 elements, inclusive.
-Each element in chips will be between 0 and 4, inclusive.


{ 1, 1 }
Returns: { 0.0,  0.0 }
There are only two $5 chips, and 2/5 rounds down to zero. So no $25 chips are awarded.
{ 1, 2 }
Returns: { 0.3333333333333333,  0.6666666666666666 }
There are three $5 chips, and 3/5 rounds up to 1, so one $25 chip is awarded. Three cards are dealt, and player 1 has a 1/3 chance of getting the highest card and player 2 has a 2/3 chance of getting the highest card.
{ 3, 2, 3 }
Returns: { 0.725,  0.55,  0.725 }
Two $25 chips are awarded. Player 2 has a 1/4 chance of winning the first chip. If either one of the other players wins the first chip, he will then have a 2/5 chance of winning the second chip. (1/4) + (3/4)*(2/5) = 0.55. Since there are a total of two chips awarded, the players' probabilities must sum to 2. Since each of the other players have the same chance of winning a chip, their probabilities are each 1/2 of (2 - 0.55), which is 0.725.
{ 0, 1, 2, 3, 4 }
{ 0.0,  0.23452380952380952,  0.4412698412698413,  0.6083333333333334,  0.7158730158730159 }
 { 0, 1, 1, 0, 0, 0, 0, 1, 1, 0 }
Returns: { 0.0,  0.25,  0.25,  0.0,  0.0,  0.0,  0.0,  0.25,  0.25,  0.0 }

Problem url:

Problem stats url:




lbackstrom , brett1479

Problem categories:

Advanced Math