Problem 286: Scoring Probabilities

Mathematical Foundation

Theorem (DP Characterization). Let $\text{dp}[i][j]$ denote the probability of scoring exactly $j$ points in the first $i$ shots. Then $\text{dp}[0][0] = 1$, $\text{dp}[0][j] = 0$ for $j > 0$, and

The function $g(q) = \text{dp}[50][20]$ is a polynomial of degree 50 in $1/q$.

Proof. Shot $i$ is an independent Bernoulli trial with success probability $1 - i/q$ and failure probability $i/q$. The recurrence follows from conditioning on the outcome of shot $i$. Since all 50 shots are independent with distinct success probabilities, the probability of exactly 20 successes is an elementary symmetric function of the success/failure probabilities, hence a rational function (in fact polynomial in $1/q$) of degree 50. $\quad\square$

Theorem (Existence and Uniqueness of Root). The equation $g(q) = 0.02$ has a unique solution in $(50, \infty)$.

Proof. At $q = 50$: $p_{50} = 0$, and the expected number of successes is $\sum_{k=1}^{49}(1 - k/50) = 24.5$. At $q \to \infty$: all $p_k \to 1$, so the probability mass concentrates at 50, making $P(X = 20) \to 0$.

For $q$ slightly above 50, the mean is near 24.5 and the distribution is spread, giving $P(X=20)$ a value well above 0.02. As $q$ increases, the mean shifts right and eventually $P(X=20)$ decreases below 0.02. By continuity and the intermediate value theorem, at least one root exists.

To show uniqueness: for large enough $q$ the distribution becomes sharply concentrated near 50, so $g(q) < 0.02$ for all sufficiently large $q$. In the transition region, one can verify numerically (or by analyzing the log-concavity of the Poisson-binomial distribution) that $g$ crosses the level 0.02 exactly once from above. $\quad\square$

Lemma (Bisection Convergence). The bisection method on $[q_{\text{lo}}, q_{\text{hi}}]$ with $g(q_{\text{lo}}) > 0.02 > g(q_{\text{hi}})$ converges to $d$ correct decimal places in $\lceil d \cdot \log_2 10 + \log_2(q_{\text{hi}} - q_{\text{lo}})\rceil$ iterations.

Proof. Standard bisection halves the interval at each step. $\quad\square$

Editorial

02, where shot k scores with probability (1 - k/q). We else. We use dynamic programming over the state space implied by the derivation, apply each admissible transition, and read the answer from the final table entry.

Pseudocode

    lo = 50.0
    hi = 100.0
    for iter = 1 to 200: // ensures > 50 digits of precision
        mid = (lo + hi) / 2
        If dp_eval(mid) > 0.02 then
            lo = mid
        else:
            hi = mid
    Return round(lo, 10)

    dp = array[0..50] initialized to 0
    dp[0] = 1.0
    For i from 1 to 50:
        p_hit = 1 - i/q
        p_miss = i/q
        for j = min(i, 20) downto 1:
            dp[j] = dp[j] * p_miss + dp[j-1] * p_hit
        dp[0] = dp[0] * p_miss
    Return dp[20]

Complexity Analysis

• Time: $O(I \cdot n \cdot t)$ where $I \approx 200$ bisection iterations, $n = 50$ shots, $t = 20$ target score. Total: $O(200 \cdot 50 \cdot 20) = O(200000)$.
• Space: $O(t) = O(20)$ using a rolling 1D DP array.

Answer

#include <bits/stdc++.h>
using namespace std;

// Compute P(exactly 20 scores in 50 shots) given q
double compute(double q) {
    // dp[j] = probability of exactly j scores so far
    vector<double> dp(21, 0.0);
    dp[0] = 1.0;
    for (int i = 1; i <= 50; i++) {
        double p_score = 1.0 - (double)i / q;  // probability of scoring shot i
        double p_miss = (double)i / q;
        // Update in reverse to avoid overwriting
        for (int j = min(i, 20); j >= 1; j--) {
            dp[j] = dp[j] * p_miss + dp[j - 1] * p_score;
        }
        dp[0] *= p_miss;
    }
    return dp[20];
}

int main() {
    double lo = 50.0, hi = 100.0;
    double target = 0.02;

    // Binary search for q
    for (int iter = 0; iter < 200; iter++) {
        double mid = (lo + hi) / 2.0;
        double val = compute(mid);
        if (val > target) {
            lo = mid;  // need larger q to decrease P(X=20)
        } else {
            hi = mid;
        }
    }

    printf("%.10f\n", (lo + hi) / 2.0);
    return 0;
}

"""
Problem 286: Scoring Probabilities

Find q such that the probability of scoring exactly 20 out of 50 shots
equals 0.02, where shot k scores with probability (1 - k/q).
"""

from decimal import Decimal, getcontext

getcontext().prec = 50

def compute_prob(q):
    """Compute P(exactly 20 scores) given q, using DP."""
    dp = [Decimal(0)] * 21
    dp[0] = Decimal(1)
    for i in range(1, 51):
        p_score = Decimal(1) - Decimal(i) / q
        p_miss = Decimal(i) / q
        for j in range(min(i, 20), 0, -1):
            dp[j] = dp[j] * p_miss + dp[j - 1] * p_score
        dp[0] *= p_miss
    return dp[20]

def solve():
    target = Decimal("0.02")
    lo = Decimal("50")
    hi = Decimal("100")

    for _ in range(200):
        mid = (lo + hi) / 2
        val = compute_prob(mid)
        if val > target:
            lo = mid
        else:
            hi = mid

    q = (lo + hi) / 2
    print(f"{q:.10f}")

if __name__ == "__main__":
    solve()

    # Optional visualization