Pitches
SRM 253 · 2005-07-23 · by legakis
Problem Statement
A struggling baseball pitcher is hoping to improve his results by analyzing the statistics of how various batters perform against each of his two types of pitches: his "fast ball" and his "curve ball". He has developed a model to help him decide which pitch to select in any given circumstance.
In the game of baseball (slightly simplified for this problem), each pitch thrown will result in one of three outcomes: a "strike", a "ball", or a "hit". If a batter ever gets a hit or accumulates 4 balls before accumulating 3 strikes, this is a victory for the batter. However, if he gets 3 strikes first, this is a victory for the pitcher. The running count of balls and strikes is collectively referred to as the "count".
For this analysis, both the pitcher and batter are modelled as having a table of probabilities computed before the game. For each of the 12 possible counts, the pitcher has a probability for selecting to throw a curve ball instead of a fast ball. Similarly, for each possible count, the batter has a probability for expecting the pitcher to throw a curve ball. Before each pitch, the pitcher randomly selects which pitch to throw and the batter randomly selects which pitch to expect strictly according to the probabilities in the table for the current count.
Computing the optimal values for the probabilities in this table depends on the statistics for how the batter performs for each of the 4 possible combinations of thrown and expected pitches. These statistics will be provided by an 8-element
pitcher throws batter expects ball strike hit
-------------- -------------- -------- -------- -----------------------
fast ball fast ball stats[0] stats[1] 1 - (stats[0]+stats[1])
fast ball curve ball stats[2] stats[3] 1 - (stats[2]+stats[3])
curve ball fast ball stats[4] stats[5] 1 - (stats[4]+stats[5])
curve ball curve ball stats[6] stats[7] 1 - (stats[6]+stats[7])
The pitcher attempts to maximize his chance of getting 3 strikes, knowing that the batter will be attempting to maximize his chance of getting 4 balls or a hit. For a given count, the optimal probability for the pitcher to throw a curve ball is the probability that minimizes the batter's ability to succeed. Similarly, the optimal probability for the batter to expect a curve ball is the probability that minimizes the pitcher's ability to succeed. In other words, the optimal pair of probabilities for a given count are such that if either the pitcher's or the batter's probability were to change, the other would be able to improve their chances by changing their probability as well. The optimal pair of probabilities forms an equilibrium, where neither the batter nor the pitcher can improve their chances if the other does not change their probability.
For example, consider the following (unrealistic) statistics: { 0, 0, 0, 1, 0, 1, 0, 0 }, with a count of 3 balls and 2 strikes. In this case, if the batter expects the same pitch that the pitcher throws, he will get a hit, otherwise, it will be a strike. The optimal probabilities are for both the pitcher and batter to select a curve ball exactly 50% of the time. 50% is optimal for the pitcher because if he were to prefer one pitch or the other, the batter could improve his performance by preferring that same pitch. Similarly, 50% is optimal for the batter because if he preferred one pitch or the other, the pitcher would be able to take advantage of that fact by preferring the opposite pitch.
Given the statistics in the format described above as a
Notes
- Your return value must have an absolute or relative error less than 1e-9.
Constraints
- stats will contain exactly 8 elements.
- Each element of stats will be between 0.0 and 1.0, inclusive.
- stats[0] + stats[1] will be less than or equal to 1.0.
- stats[2] + stats[3] will be less than or equal to 1.0.
- stats[4] + stats[5] will be less than or equal to 1.0.
- stats[6] + stats[7] will be less than or equal to 1.0.
- balls will be between 0 and 3, inclusive.
- strikes will be between 0 and 2, inclusive.
{ 0, 0,
0, 1,
0, 1,
0, 0 }
3
2
Returns: 0.5
This is the example in the problem statement.
{0.541360678953378,0.251311079561226,0.810364006439709,0.172433517475874,0.224491762214985,0.40885541054179,0.586207954897386,0.118656938732521}
0
0
Returns: 0.06393930309319609
{0.576011612426814,0.418368878292426,0.00659910848814249,0.466372046112021,0.289294236388617,0.280864375524416,0.556361780182097,0.382662625898313}
0
0
Returns: 0.1949923005099184
{ 0, 0, 0, 0.51, 0, 1, 0, 0.49 }
3
2
Returns: 0.5
{ 0.375, 0.25,
0.375, 0.25,
0.375, 0.25,
0.375, 0.25 }
0
2
Returns: 0.39208984375
{ 0.33, 0,
0, 1,
0.44, 0,
0, 1 }
2
1
Returns: 0.0
It doesn't matter which pitch the pitcher throws; if the batter expects a fast ball, he will always get a ball or a hit.
{ 0, 1,
0, 1,
0, 0,
0, 0 }
2
1
Returns: 1.0
It doesn't matter which pitch the batter expects; if the pitcher throws a fast ball, he will always get a strike.
Submissions are judged against all 87 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Pitches with a public method double strikeOut(vector<double> stats, int balls, int strikes) · 87 test cases · 2 s / 256 MB per case