Knockout is a basketball game where players take turns shooting. It is played as a sequence of two-player contests, each of which has the possibility of "knocking out" one of those players.
Suppose the players are
A B C D and their chances of shooting and making a basket are
0.1 0.2 0.3 0.4 respectively, independently of the other player in the contest. The two players at the front of the line,
B, "fight." Since
A goes first, he is the defender, in danger of being eliminated, and
B is the attacker, and not in danger of immediate elimination.
A shoots first. If
A makes it,
A has successfully defended, and goes to the back of the line. The line would change to
B C D A. If
A doesn't make it, then
B shoots. If
B makes it, then
A is out and
B goes to the back of the line, so the line becomes
C D B. If neither
B makes it, the process repeats, with
A shooting again, until either
B makes a basket.
Suppose the line changed to
B C D A (
A had successfully defended). Now,
C "fight," with
B being the defender, and
C being the attacker. This process repeats until only one person is left over. That person is the winner.
Your task is to calculate the probabilities of each person winning given the chance that they will make a basket.
A list of numbers, such as
0.1 0.2 or
0.5 0.5 0.5 0.5, where the nth number is the chance that the nth player will make a basket. You can take this input in any format you like, including as the parameters to a function.
A list of numbers, where the nth number is the chance that the nth player will win the game. Your numbers must be accurate to at least two decimal places at least 90% of the time. This means that you can use a simulation-based approach. However, if your code is not simulation based (it is guaranteed to return a correct answer to at least 6 decimal places) then take away 30% from your score.
0.5 0.5: Call the players
p be the probability of A winning.
A has a
2/3 chance of successfully defending (since there's a
1/2 chance that
A scores, a
1/4 chance that
A misses and
B scores, and a
1/4 chance that both miss and the process repeats). If
A fails to defend, he is knocked out and
B wins. If
A defends, then the line becomes
B A. Since the situation is symmetric, the probability of
A winning is
(1 - p). We get:
p = 2/3 * (1 - p) + 1/3 * 0. Solving, we get
p = 2/5. The output should be
2/5 3/5 or
I'm not good enough with probability to do more complex examples.
If you need more test cases, here are a few:
0.1 0.2 0.3 0.4 --> 0.01 0.12 0.25 0.62 0.99 0.99 --> 0.5 0.5 (it's not exact, but if you round to two decimal places, you get 0.5 and 0.5)