~/problems

Problems

Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.

Counting

Catalan numbers

C(n) = sum C(i) C(n-i-1): trees, parenthesizations.

Quiz (8) Spot the pattern
Notes

Recognise it when: counting structures that split into two independent smaller ones: BSTs over 1..n, balanced parentheses, polygon triangulations, full binary trees.

\[ C(n) = \sum_{i=0}^{n-1} C(i)\,C(n-1-i), \quad C(0)=1, \qquad C(n) = \frac{1}{n+1}\binom{2n}{n} \]

c = [1] + [0] * n
for m in range(1, n + 1):
    c[m] = sum(c[i] * c[m - 1 - i] for i in range(m))

Values: 1, 1, 2, 5, 14, 42, 132, 429.

5 problems

Advanced & competitive

Counting Combinatorics, inclusion-exclusion, Catalan numbers.

Catalan numbers

esc