Всё, что должно быть под рукойEverything you need at hand

• Four ready-made ways to choose $k$ from $n$: with order and without replacement, $\frac{n!}{(n-k)!}$; without order and without replacement, $\binom{n}{k}$; with repetition and order, $n^k$; with repetition and without order, $\binom{n+k-1}{k}$
• $\binom{n}{k}=\binom{n}{n-k}$; $\sum_k\binom{n}{k}=2^n$; $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$
• Split a choice into groups: the condition divides the objects into groups—count each group as its own combination and multiply the groups
• Encode an arrangement as a string: write the outcome as a string of symbols; the question becomes which positions contain symbols of one kind
• Divide by overcounting (group allocation, also permutations with repeats): $\frac{n!}{n_1!\cdots n_m!}$; for equal-sized indistinguishable groups, divide once more by $m!$
• Count quantities instead of order—balls and dividers: $k$ balls of $n$ types in a row with $n-1$ dividers give the solutions of $x_1+\cdots+x_n=k$, exactly $\binom{n+k-1}{k}$
• Around a circle, with rotations indistinguishable: fix one object in a seat—then $(n-1)!$
• Count the forbidden cases: when direct counting has split into too many terms, count the forbidden cases and subtract them from the total
• Inclusion–exclusion: add single sets, subtract pairs, add back triples
• The rule “no two adjacent”: the number of binary strings of length $n$ with $k$ ones and no adjacent ones is $\binom{n-k+1}{k}$
• Derangements: $D_n=n!\sum_{k\le n}\frac{(-1)^k}{k!}$; the fraction tends to $e^{-1}$
• Number of divisors: $\tau\left(\prod p_i^{\alpha_i}\right)=\prod(\alpha_i+1)$
• Before counting, look for symmetry

• $\P(A)=\frac{|A|}{|\Omega|}$—only for equally likely outcomes. First say what determines the outcome and check equal likelihood
• Measure instead of counting: when there are infinitely many outcomes, probability is a fraction of length, area, or angular measure
• $\P(\bar A)=1-\P(A)$; $A\subset B\Rightarrow\P(A)\le\P(B)$; $\P(A\cup B)=\P(A)+\P(B)-\P(A\cap B)$
• Complement instead of direct counting: “at least one,” “all at once,” and “not all”—count the opposite event. “None” is already the complementary event, so count it directly as a product; there is nothing to subtract
• Independent events: $\P(A\cap B)=\P(A)\P(B)$, so multiply. Disjoint events: $\P(A\cap B)=0$, so add
• Strip in a square: a condition on the difference of two times makes a strip along the square’s diagonal; count it through its complement. Meeting: $1-\left(1-\frac tT\right)^2$
• Shrinking the space: “it is known that,” “it turned out that”—this chooses the denominator; recompute the fraction within the specified set
• $\P(A\mid B)=\frac{\P(A\cap B)}{\P(B)}$; $\P(B)=\sum_i\P(B\mid H_i)\P(H_i)$; $\P(H_k\mid B)=\frac{\P(B\mid H_k)\P(H_k)}{\P(B)}$
• Tree branch: multiply along a branch, add between branches, and the sum of all branches is 1
• Absolute counts: do Bayes with whole people out of 10,000 rather than by formula
• Odds rule: when there are exactly two hypotheses, multiply prior odds by the likelihood ratio; there is no need to calculate the denominator
• Bernoulli scheme: $\binom nk p^kq^{n-k}$
• Maximum and minimum: first compute $\P(X\le t)$—it factors

• $\E(aX+bY)=a\E X+b\E Y$—always, no independence needed
• $\D X=\E X^2-(\E X)^2$; $\D(X+Y)=\D X+\D Y$—only for independent variables
• Decompose into a sum of indicators: $X=\sum I_j\Rightarrow\E X=\sum\P(I_j=1)$. Read the same identity from right to left when the question asks for one summand’s probability
• If an indicator contains “at least once,” use the complement: $\P(I_j=1)=1-\P(\text{never})$
• Condition on the first step: $\E=1+(1-p)\E\Rightarrow\E=\frac1p$
• Process by stages: when the success probability changes, split into stages; a stage costs $\frac1{p_k}$ on average and stage expectations add. Coupon collector: $nH_n\approx n\ln n$
• Tail formula: $\E X=\sum_{k\ge1}\P(X\ge k)$ for nonnegative integer-valued variables
• Spacing lemma: before the first marked object among $k$ marks in a row of $n$, the average count through it is $\frac{n+1}{k+1}$
• $\max+\min=$ the sum—if the maximum is hard, compute the minimum
• $U[0,1]$, $n$ points: $\E[\min]=\frac1{n+1}$, $\E[\max]=\frac n{n+1}$
• $\E$, $\D$: Bernoulli $p,\,pq$; binomial $np,\,npq$; geometric $\frac1p,\frac{1-p}{p^2}$; Poisson $\lambda,\lambda$; uniform $\frac{a+b}2,\frac{(b-a)^2}{12}$; exponential $\frac1\lambda,\frac1{\lambda^2}$

• $f'(x)=\lim_{h\to0}\frac{f(x+h)-f(x)}{h}$; tangent $y=f(x_0)+f'(x_0)(x-x_0)$
• $(uv)'=u'v+uv'$; $\left(\frac uv\right)'=\frac{u'v-uv'}{v^2}$; $\big(f(g)\big)'=f'(g)\cdot g'$
• The question asks for a value, not a point: after finding $x_0$, substitute it back into $f$
• Tangency with an unknown contact point: the system $f(x_0)=kx_0+b$ and $f'(x_0)=k$
• Integer extremum: do not set the derivative to zero—the continuous maximum locates the candidate, then check the two neighboring integers
• For a radical derivative from the definition, multiply by the conjugate
• If the variable appears in both base and exponent, take logarithms
• $\sin x=x-\frac{x^3}{6}$; $\cos x=1-\frac{x^2}2+\frac{x^4}{24}$; $\tan x=x+\frac{x^3}3$
• $e^x=1+x+\frac{x^2}2+\frac{x^3}6$; $\ln(1+x)=x-\frac{x^2}2+\frac{x^3}3$; $(1+x)^\alpha=1+\alpha x+\frac{\alpha(\alpha-1)}2x^2$
• $\arcsin x=x+\frac{x^3}6$; $\arctan x=x-\frac{x^3}3$; $\sqrt{1+x}=1+\frac x2-\frac{x^2}8$
• The leading terms canceled—go back and keep one more term in the expansion
• $1^{\infty}$ → take logarithms and, at the end, exponentiate
• $\ln x\ll x^a\ll e^x\ll x!$
• $\int_0^1x^a(1-x)^b=\frac{a!b!}{(a+b+1)!}$; $\int_0^\infty x^ne^{-x}=n!$; $\int_0^\infty e^{-ax}\sin bx=\frac b{a^2+b^2}$
• Integration by parts: put in $u$ the factor simplified by differentiation. An exponential times a sine needs two rounds and an equation for the original integral
• A singular endpoint (infinity or a blow-up): replace the boundary with a letter $T$ and take the limit as the final operation
• Symmetrization: $\int_a^bf(x)dx=\int_a^bf(a+b-x)dx$
• Angle between curves: $\tan\varphi=\left|\frac{k_1-k_2}{1+k_1k_2}\right|$
• $x^a\ln x\to0$ as $x\to0^+$

• $\cos\varphi=\frac{\langle x,y\rangle}{\|x\|\|y\|}$; orthogonality $\iff\langle x,y\rangle=0$
• A coordinate-free figure: place a convenient vertex at the origin, align the edges with the axes, and write down two vectors
• Given only lengths and angles: turn each angle into a dot product $\|u\|\,\|v\|\cos\varphi$, then expand the squared norm
• $\proj_vu=\frac{\langle u,v\rangle}{\langle v,v\rangle}v$ is a vector; projection length is $\frac{|\langle u,v\rangle|}{\|v\|}$. Dimensional check: the vector has $\langle v,v\rangle$ below, while the length has only $\|v\|$
• $\|u+v\|^2=\|u\|^2+2\langle u,v\rangle+\|v\|^2$
• $|\langle x,y\rangle|\le\|x\|\|y\|$, with equality for collinear vectors; $|\cos\varphi|>1$ is always arithmetic error, never an exotic case
• Distance to the plane $\langle n,x\rangle=c$: $\frac{|\langle n,p\rangle-c|}{\|n\|}$; distance to a line is the length of the orthogonal component, with Pythagoras as a second check
• Gram matrix: $G_{ij}=\langle v_i,v_j\rangle$, dependence $\iff\det G=0$
• Kronecker–Capelli: consistent $\iff\rank A=\rank[A\mid b]$
• $\det(AB)=\det A\det B$; $\tr A=\sum\lambda_i$; $\det A=\prod\lambda_i$
• $\rank(A^TA)=\rank A$—the basis of least squares
• Diagonal dominance $\Rightarrow$ invertibility
• Vandermonde $=\prod_{i<j}(x_j-x_i)$
• $\begin{pmatrix}a&b\\c&d\end{pmatrix}^{-1}=\frac1{ad-bc}\begin{pmatrix}d&-b\\-c&a\end{pmatrix}$

• list: indexing $O(1)$, search $O(n)$. dict and set: $O(1)$ on average. deque: both ends $O(1)$. heap: $O(\log n)$
• $O(n^2)$ at $n=10^6$ takes 17 minutes. Rule of thumb: $10^8$ operations per second
• Five templates: hash table “seen before,” prefix sums, two pointers and a sliding window, binary search on the answer, and digit-by-digit processing
• Binary search: while lo < hi, hi = mid / lo = mid + 1
• Kadane: cur = max(v, cur+v), initialized with a[0]
• 0/1 knapsack—iterate over capacity backwards
• Levenshtein: take the minimum of three values
• Greedy interval selection—sort by the right endpoint
• Fibonacci: strings with no two consecutive ones. Tribonacci: no three consecutive ones
• Traps: string concatenation $O(n^2)$; forgetting the last RLE group; c[0] = 1 in prefix sums by remainder; best = a[0] in Kadane

Extension based on the Q1–Q18 sample

After the core course, follow 15 → 16 → 17 → 18 → 19. These are five additional sessions of up to four hours, without new dates. If you interleave them with the core course, complete each session's listed prerequisites first.

The minimum includes the whole lesson and model solution, the marked problems in every new chain, and all finals. Before the extension, recover the core exercises in the map's third column. Then take mocks 3 and 4, with error analysis and fresh mixed review between them. A total solved count alone does not identify unavailable methods.

The practice goal is to choose a method independently, justify transitions, and solve each represented type across both new sets. A numeric score does not assess proofs: compare them with the checklists after finishing. This sample establishes no official pass threshold, timing, or permitted tools. The new mocks use 180 minutes and paper work with a calculator as chosen practice settings.

The sample does not guarantee coverage of every possible exam topic. Existing problems, mocks, and calendar dates are retained; this addition expands preparation for the represented types without replacing the core course.

import numpy as np
rng = np.random.default_rng(0)
N = 5_000_000

# P(|X - Y| < 2/5) for X, Y ~ U[0,1]
p = rng.random((N, 2))
print((np.abs(p[:,0] - p[:,1]) < 2/5).mean())      # ~0.6400

# 5 dice, all results distinct
d = rng.integers(1, 7, size=(N, 5))
d.sort(axis=1)
print((np.diff(d, axis=1) > 0).all(axis=1).mean()) # ~0.0926

# random permutation: mean number of fixed points
perm = np.argsort(rng.random((200_000, 6)), axis=1)
print((perm == np.arange(6)).sum(1).mean())        # ~1.0

Accuracy is on the order of $1/\sqrt N$: a million trials give three correct digits, and one hundred million give four. Always fix the seed so the result is reproducible.

import itertools, math
from fractions import Fraction as F

# 4 dice, P(sum = 10)
c = sum(1 for t in itertools.product(range(1,7), repeat=4) if sum(t) == 10)
print(F(c, 6**4), float(F(c, 6**4)))       # 5/81  0.061728

# inclusion–exclusion check
print(sum(1 for n in range(1, 1001) if n % 3 and n % 7))   # 572

# combinations and factorials
math.comb(12, 5)        # 792
math.factorial(8)       # 40320

Fraction prevents accumulated rounding errors—round only at the very end.

import sympy as sp
x = sp.Symbol('x')

sp.limit((sp.exp(x**2) - sp.cos(x)) / x**2, x, 0)                # 3/2
sp.limit((1 + 3/x)**(2*x), x, sp.oo)                             # exp(6)
sp.integrate(x**2 * (1-x)**3, (x, 0, 1))                         # 1/60
sp.integrate(sp.exp(-3*x) * sp.cos(2*x), (x, 0, sp.oo))          # 3/13
sp.diff(sp.log(1 + x**2), x).subs(x, 2)                          # 4/5
sp.series(sp.log(1 + sp.sin(x)), x, 0, 6)                        # Taylor series
sp.solve(x**2 - 4*x - 12, x)                                     # [-2, 6]
sp.nsolve(sp.atan(x/5) - sp.pi*(20 - 3*x)/4, x, 6)               # numerical root

print(sp.N(sp.pi / 7, 6))                                        # 0.448799

sp.N(expr, 6) is a reliable way to obtain four decimal places without rounding mistakes.

import numpy as np
u = np.array([1., 2., 2.]); v = np.array([2., -1., 2.])

np.linalg.norm(u)                                  # Euclidean length
np.linalg.norm(u, 1)                               # Manhattan norm
u @ v                                              # dot product
u @ v / (np.linalg.norm(u) * np.linalg.norm(v))    # cosine of the angle
np.arccos(_)                                       # angle in radians
(u @ v / (v @ v)) * v                              # projection of u onto v

A = np.array([[3.,1,2],[0,5,1],[4,2,7]])
np.linalg.det(A)                                   # 63.0
np.linalg.matrix_rank(A)                           # 3
np.linalg.eigvals(A)                               # spectrum
np.linalg.inv(A)                                   # inverse
np.linalg.solve(A, b)                              # solution of the system

V = np.stack([u, v, w])
np.linalg.det(V @ V.T)                             # Gram determinant

A determinant computed with numpy is approximate: if you get $62.99999999999999$, the answer is $63$. For exact values, use sympy.Matrix.

def ok(k):
    """True if the condition holds for parameter k"""
    return sum(-(-p // k) for p in piles) <= h

lo, hi = 1, 10**9                 # hi is known to work
while lo < hi:
    mid = (lo + hi) // 2
    if ok(mid): hi = mid          # works—shrink from the right
    else:       lo = mid + 1      # fails—move from the left
print(lo)

# real-valued version: fixed number of iterations
lo, hi = 0.0, 1e9
for _ in range(100):
    mid = (lo + hi) / 2
    if ok(mid): hi = mid
    else:       lo = mid
print(hi)

Invariant: hi is always “good,” while lo is the boundary. For real values, it is simpler to run a fixed 100 iterations than to manage $\varepsilon$.

import numpy as np
from scipy.integrate import quad
from scipy.optimize import brentq

quad(lambda x: np.sin(x)*np.log(x), 0, 1)          # (value, error)
quad(lambda x: np.exp(-x**2), 0, np.inf)

brentq(lambda a: np.arctan(a/5) - np.pi*(20-3*a)/4, 1, 10)   # root on an interval

# if scipy is unavailable—trapezoids with numpy
t = np.linspace(0, 1, 2_000_001)
print(np.trapezoid(np.sqrt(1 - t**2), t) * 4)      # ≈ pi

# Newton’s method by hand—needed for the IN-PERSON exam
a = 6.0
for _ in range(5):
    g  = np.arctan(a/5) - np.pi*(20 - 3*a)/4
    gp = 5/(25 + a**2) + 3*np.pi/4
    a -= g/gp
print(round(a, 4))

Practice Newton’s method on paper: there will be no computer on September 20, and some problems there have numerical answers. Formula: $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$; four iterations usually suffice for four correct digits.

The online stage is only the first of three filters. After that, the format changes radically.

In-person written exam · September 20

Mathematics lasts about 3 hours, and programming 2 hours. Both subjects are taken in Tashkent on the same day. The key difference is that full justification is required. A numerical answer without a derivation does not count. There will be no computer.

Plan from September 6 through 19

September 5 is not part of the plan: it is the backup attempt day, kept free in case September 4 fails, and no study load is scheduled. Preparation for the written stage starts on September 6.

1. September 6. The eight online-stage conditions were already reconstructed from memory on September 4, in the 14:00–15:00 slot immediately after the attempt; this was not postponed because the next day you would recall half as much. Next to each problem, write its program day and ladder level. This immediately shows which levels were weak on the real exam. It is the best available source on the authors’ style.
2. September 7–12. Rewrite solutions from this bank in full: “given—required—solution—answer,” with every justification. A problem you solved in 5 minutes should take 20 minutes to present. The bank itself gives the order: for each day, first its final problems from “Where we are going,” then the required bridges. Six days with five written solutions each gives thirty solutions, all from levels 3 and 4. Within this period are two calendar dates unrelated to preparation: September 9 is the application deadline, so check that the application was submitted; September 10 closes the online-test window, and no attempt will be possible after it.
3. September 13–16. Programming without a computer: write code on paper, then type and check it. Log every discrepancy. The material is days 11 and 12.
4. September 17–18. Full written-format mock: 3 hours of mathematics with complete solutions, then 2 hours of programming on paper.
5. September 19. Light day. Cheat sheets, error log, sleep.

How to present a solution

• Write what is given and what is required on separate lines.
• Take the first move from the day’s triggers, but name it in words on paper: not “use the complement,” but “the direct count splits into overlapping cases, so count the complementary event.”
• Support every nontrivial transition with a reference: “by the law of total probability,” “by the Cauchy–Schwarz inequality,” or “because the function is continuous on the interval.”
• Check boundary cases explicitly: “when $a=0$, the denominator is zero; consider this separately.”
• Circle the answer. The grader should not have to search for it.
• Even an unsolved problem earns points for a correct start. Write everything you understand.

In-person interview · September 28 — October 4

Three parts of about 30 minutes each: mathematics, algorithms with live coding, and motivation.

Mathematics block

Quick definition questions plus two or three problems solved aloud. They test command of the language: can you formulate things precisely? Rehearse these aloud:

• Definition of a probability space.
• Definition of independence. An example of pairwise independent but not mutually independent events.
• Definition of a derivative. Definition of a limit.
• What is the rank of a matrix—three equivalent definitions.
• What is an eigenvector?
• Cauchy–Schwarz inequality: statement and when equality holds.
• Cosine similarity: why it is the cosine of an angle and how it differs from a dot product.

Algorithms block

1. Clarify boundary cases before writing code.
2. State the naive solution and its complexity aloud.
3. Propose an improvement and explain what makes it work.
4. Write code while verbalizing every step. Do not stay silent for more than 15 seconds.
5. Trace it by hand on two examples: a typical one and a boundary case.
6. State the final time and space complexity.

Motivation block

They check three things: whether you are ready for 20–30 hours per week for a year, whether your interest is genuine, and what you plan to do afterwards. Prepare honest answers, not “correct” ones.