WinningProbability
SRM 218 · 2004-11-04 · by lars2520
Problem Statement
To that end, you've come up with the following strategy. First, you will assume that there is some probability, p, that your team will win each game, and you will assume that each game is independent. For a given value of p, you can thus calculate the probability that your team won and lost as it did in the past. Now, let's say that for a given value of p, p1, the probability of the previous games turning out as they did is q1, and similarly for p2, the probability is q2. From this, you've decided that the true probability of your team winning a game is (q1/q2) times more likely to be p1 than it is to be p2. Considering all possible values of p, and taking into account the relative probabilities of each, determine the probability that your team will win the series.
Notes
- Your return must have an error of less than 1e-9.
Constraints
- prevWins and prevLosses will each be between 0 and 100, inclusive.
- gamesLeft will be between 1 and 15, inclusive.
- mustWin will be between 1 and gamesLeft, inclusive.
2 0 1 1 Returns: 0.75
Consider a few illustrative values of p: | prob of | prob of p | previous | winning series ----+----------+--------------- 0.0 | 0.0 | 0.0 0.1 | 0.01 | 0.1 0.2 | 0.04 | 0.2 0.3 | 0.09 | 0.3 0.4 | 0.16 | 0.4 0.5 | 0.25 | 0.5 0.6 | 0.36 | 0.6 0.7 | 0.49 | 0.7 0.8 | 0.64 | 0.8 0.9 | 0.81 | 0.9 1.0 | 1.0 | 1.0 So, p is 4 times more likely to be 1.0 than it is to be 0.5, and is definitely not 0. Considering only these values of p, and taking a weighted average, we find that the probability of winning the series is 0.786. Clearly, considering only 11 values of p does not yield the required accuracy, but if you consider all possible values, you find that your team has a probability of 0.75 of winning the series.
0 3 4 4 Returns: 0.0142857142857
After losing the first 3 games of the ALCS, the Red Sox had a probability of less than 2% of winning the series, according to this model.
20 3 5 1 Returns: 0.9995284409077
Your team only needs to win 1 out of 5 games, and in the past it has won 20/23, so your odds are high.
0 20 1 1 Returns: 0.0454545454545
Your team has never won in the past, so its unlikely they will this time.
0 0 1 1 Returns: 0.5
With no previous games, all values of p are equally likely, and as you would expect, there is a 50% chance that your team will win.
Submissions are judged against all 28 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WinningProbability with a public method double probability(int prevWins, int prevLosses, int gamesLeft, int mustWin) · 28 test cases · 2 s / 256 MB per case