Динамика, жадность и Python как оружиеDynamic Programming, Greedy Methods, and Python as a Weapon

Opening: eight problems, six topics

Today’s bank is arranged like the exam: eight YMLS problems appear in mixed order, and that is how they will arrive on September 4—without a “probability” heading above the statement. Each is easier than what you solved on your strongest day in its topic; the danger is the first thirty seconds: a wrong first move costs twenty minutes that you do not have across eight problems.

Part 1. The first thirty seconds

The rule is: say the type and first move aloud, then pick up the pen. Do not start calculating until the statement has been translated into one sentence.

Seven of the eight rows are “Bridge” points; only the first is new, and Part 2 is devoted to it. If any of the seven takes more than a couple of seconds to recall, restore it now.

Part 2. Count the tail, not the value

Problem. A die is rolled $n$ times. What is the probability that the maximum equals $t$?

Direct counting requires casework: exactly one $t$ with all the rest smaller, exactly two with all the rest smaller, and so on—a sum of $n$ terms with binomial coefficients. The move that removes all the casework is this: “the maximum is at most $t$” means every roll is at most $t$; the conditions are independent, so the probability is a power. “Equals” is then obtained by subtracting the nested event “everything is at most $t-1$”:

For the minimum, mirror the argument: “the minimum is at least $t$” means every roll is at least $t$, so $\P(\min \ge t) = \left(\frac{7-t}{6}\right)^{n}$. This works for one reason: “at most $t$” is a condition on each trial separately, so the probability factors into a product, while “equals $t$” is a condition on the whole collection and does not factor.

The same move for expectation. The “Bridge” tail formula turns $\E X$ into a sum of $\P(X \ge k)$, and the work is to describe “$X \ge k$” in the language of the trials. Roll a die until the first six: the event $\{N \ge k\}$ means the first $k-1$ rolls were not six, so $\P(N \ge k) = (5/6)^{k-1}$ and $\E N = \frac{1}{1 - 5/6} = 6$—a geometric progression instead of a series with a factor k inside.

Part 3. Continuous outcome: inequality, region, area

When a point is chosen at random inside a figure, there are infinitely many outcomes and nothing to count: probability is an area fraction (“Bridge”). The whole job is to turn the verbal condition into a region. Example: this is final y0202 from day 2, brought here ready-made: $X$ and $Y$ are independent and uniform on $[0,1]$; find $\P(|X-Y| < 1/3)$. The pair $(X,Y)$ is uniform in the unit square, and $|x-y| < 1/3$ cuts out a strip along the diagonal. Outside the strip are two right triangles with legs $2/3$:

When the statement contains distance, a square root appears: squaring the inequality is legal here because both sides are nonnegative. After squaring, coordinate squares often cancel, and the boundary turns out to be a parabola—not a coincidence: “distance to a point equals distance to a line” is the definition of a parabola with a focus and directrix.

Part 4. Let the machine count: exact enumeration

The first question is the size of the outcome space. Yesterday’s reference is $10^8$ simple operations per second, so enumerating a few million outcomes is instant. Six die rolls are $6^6 = 46656$, permutations of six elements are $6! = 720$, and binary strings of length 12 number $2^{12} = 4096$: each can be enumerated faster than you can recall the formula. The boundary is around $10^7$: subsets of 20 items ($2^{20} \approx 10^6$) are still feasible, but permutations of 12 items ($12! \approx 4.8\cdot10^8$) are not.

import itertools
from fractions import Fraction as F

c = sum(1 for t in itertools.product(range(1, 7), repeat=6) if max(t) == 5)
print(c, F(c, 6**6), round(float(F(c, 6**6)), 4))   # 11529 427/1728 0.2471

The answer is exact: Fraction does not round along the way. Run the enumeration even when you have found a formula: two independent paths to the same number are the most reliable check.

Part 5. Let the machine count: dynamic programming

When the outcome space does not fit in enumeration, the same count can be done with dynamic programming. Ask three questions, always in this order: state—what smallest set of data describes the subproblem; transition—how the state value is expressed through values already computed; base—where it begins.

Example. How many ordered sequences of summands from $\{1,3,5\}$ add up to 30? State: $dp[i]$ is the number of ways to make sum $i$. Transition: look at the last summand, giving $dp[i] = dp[i-1] + dp[i-3] + dp[i-5]$; base: $dp[0] = 1$.

n = 30
dp = [0] * (n + 1); dp[0] = 1
for i in range(1, n + 1):
    for c in (1, 3, 5):
        if i >= c:
            dp[i] += dp[i - c]
print(dp[:6], dp[n])       # [1, 1, 1, 2, 3, 5] 390257

Check it by hand; it takes a minute and is mandatory: sum 4 comes from $1{+}1{+}1{+}1$, $1{+}3$, and $3{+}1$—exactly three sequences—and the output really has dp[4] = 3.

Part 6. Greedy methods: a first move you can prove

Sometimes enumeration is unnecessary: a locally best choice turns out to be globally correct, and everything hinges on the words “turns out.” Classic problem: given intervals, choose the maximum number of pairwise non-overlapping ones.

iv = [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)]
iv.sort(key=lambda p: p[1])        # by the RIGHT endpoint
cnt, end = 0, float('-inf')
for s, e in iv:
    if s >= end:
        cnt += 1; end = e
print(cnt)                         # 4

Part 7. Let the machine count: simulation

When the outcome is continuous, enumeration does not exist at all, and the integral is difficult, use Monte Carlo: repeat the experiment many times and take the fraction.

import numpy as np
rng = np.random.default_rng(0)
p = rng.random((5_000_000, 2))
print((np.abs(p[:, 0] - p[:, 1]) < 1/3).mean())     # 0.5557418 — the fourth digit is already wrong

The exact answer for this problem was calculated in Part 3: $5/9 = 0.5556$—five million trials did not deliver a reliable fourth digit.

Part 8. Symbolic computation in ten seconds

import sympy as sp, numpy as np
x = sp.Symbol('x')
print(sp.integrate(x**5 * sp.exp(-x), (x, 0, sp.oo)))                   # 120
print(sp.limit((sp.exp(x**2) - sp.cos(x)) / x**2, x, 0))                # 3/2
n = np.array([1., 2, 2]); p = np.array([1., 2, 3])
print(abs(n @ p - 6) / np.linalg.norm(n))                               # 1.6666666666666667
print(np.linalg.det(np.array([[3., 1, 2], [0, 5, 1], [4, 2, 7]])))      # 62.99999999999999

NumPy’s determinant is approximate: $62.99999999999999$ means exactly $63$; for an exact value, use sympy.Matrix. And if sympy is unavailable on September 4, replace symbolic answers with numeric ones: scipy.integrate.quad instead of sp.integrate, scipy.optimize.brentq instead of sp.nsolve, and mpmath.quad can even handle improper integrals over $[0,\infty)$. Check today that numpy, sympy, scipy, and mpmath import correctly. Discovering that in the exam costs a problem.

Finally, the in-person exam on September 20 will have no computer. Today’s arsenal is a weapon for September 4, not a replacement for the ability to calculate by hand.

What should stay in your head

1. Say the type and first move aloud, then pick up the pen. A wrong first move costs twenty minutes.
2. “The maximum or minimum equals $t$” is the difference of two tails; it is the tail that factors.
3. The expectation of an integer-valued variable is the sum of $\P(X \ge k)$; the work is describing that event in words.
4. Continuous outcome: inequality, region, area fraction; remove the root by squaring, and the boundary is often a parabola.
5. Fewer than a few million outcomes: exact enumeration with Fraction; more: dynamic programming.
6. Dynamic programming: state, transition, base. Loop order changes the meaning of the answer.
7. Greedy is correct only where an exchange argument applies.
8. Simulation gives three digits for a million trials and four for one hundred million.