A. Choosing rocket

The problem in brief

A crew must pick $k$ rocket components out of $n$ available ones, and the order in which they are picked does not matter. Your program reads the two natural numbers $n$ and $k$ and prints the number of possible choices. This is the binomial coefficient $\binom{n}{k}$, the most frequently used number in combinatorics and in probability. The only real difficulties are computing it without overflow or rounding errors, and handling edge cases.

How you are scored

The judge compares your printed integer with the exact answer on hidden tests (time limit 1 s, memory 64 MB). The statement gives no upper bound for $n$, so the answer may be a huge integer: an exact computation is the target.

The key idea

Count ordered choices, then divide by the orderings you over-counted. Picking the components one at a time, in order, there are $n$ choices for the first, $n-1$ for the second, ..., $n-k+1$ for the $k$-th. That counts each set of $k$ components once per possible order, that is $k!$ times. Hence

$$\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!} = \frac{n!}{k!\,(n-k)!}.$$

Two more facts make the computation clean:

• Symmetry: choosing the $k$ components you take is the same as choosing the $n-k$ you leave, so $\binom{n}{k} = \binom{n}{n-k}$. Always compute with the smaller of $k$ and $n-k$.
• Pascal's rule: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ (a given component is either taken or not). It gives a dynamic-programming alternative and a good self-check.

The figure shows why overflow matters: $\binom{100}{50}$ already has 30 digits. In C++ or Java, a 64-bit integer overflows from $\binom{67}{33}$ on, and computing $n!$ first overflows much earlier ($21! > 2^{63}$). Using floating point (math.factorial(n) / ... or scipy.special.comb without exact=True) silently loses digits beyond about $2^{53}$.

The full solution

Multiply and divide alternately, so the running value stays an exact integer and never grows much bigger than the answer:

def comb(n, k):
    if k < 0 or k > n:
        return 0                      # no way to choose more than you have
    k = min(k, n - k)                 # symmetry
    r = 1
    for i in range(1, k + 1):
        r = r * (n - k + i) // i      # r is now C(n-k+i, i), always an integer
    return r

Why is the floor division exact? After step $i$, $r = \binom{n-k+i}{i}$, which is an integer, and $\binom{n-k+i}{i} = \binom{n-k+i-1}{i-1}\cdot\frac{n-k+i}{i}$. So $r \cdot (n-k+i)$ is always divisible by $i$. The loop runs $\min(k, n-k)$ times; Python integers have arbitrary precision, so the answer is exact even with thousands of digits. (In Python 3.8+ math.comb(n, k) does the same thing; knowing how it works matters when you code in another language or need the value modulo a prime.)

Edge cases: $k = 0$ or $k = n$ give 1; $k > n$ gives 0.

solution.py --check verifies the function against brute-force enumeration of all subsets for $n \le 10$, against math.comb and Pascal's rule on 2000 random cases with $n \le 3000$.

Results

approach	correct on large tests?	why
multiplicative formula with exact integers	yes	exact, $O(\min(k, n-k))$ steps
math.comb	yes	same algorithm, built in
$n!/(k!(n-k)!)$ with Python integers	yes, but slower	huge intermediate numbers
same with 64-bit integers (C++)	no, from $n = 21$	$21!$ overflows
floating-point factorials	no, from about $n = 60$	only 53 bits of mantissa
enumerate all subsets	no	$\binom{40}{20} \approx 1.4 \times 10^{11}$ subsets

What to remember

• Count ordered selections, divide by the number of orderings: this reasoning recovers $\binom{n}{k}$ and many other counting formulas.
• Use symmetry, and alternate multiplications and divisions, so that every intermediate value is an exact integer.
• Combinatorial numbers explode: never compute factorials in fixed-size integers or floats when an exact answer is required.
• In ML, $\binom{n}{k}$ is everywhere: the number of feature subsets of size $k$ (why exhaustive feature selection is hopeless), the binomial distribution $\binom{n}{k}p^k(1-p)^{n-k}$ behind accuracy confidence intervals, the number of pairs $\binom{n}{2}$ in a similarity matrix.