ТренажёрTrainer

Тёплый стартWarm start

Карточки возвращаются через 1, 2, 4, 7, 14 и 21 день — в зависимости от того, насколько уверенно ты их вспомнил. «Не помню» отправляет карточку в самое начало.

Cards return after 1, 2, 4, 7, 14, and 21 days depending on how confidently you recalled them. “I don’t remember” sends a card back to the beginning.

107

к повтору сейчас

в работе

131

всего карточек

Комбинаторика день 1 осталось 107

Правило умножения: две оговорки, без которых оно не работает

The multiplication rule: two qualifications without which it does not work

Сначала сформулируй вслух. Попытка вспомнить закрепляет сильнее, чем чтение готового ответа.

Перемешанная практика

6 задач высокого доступного уровня: подборка покрывает все пройденные разделы. Это отдельная попытка — ответы из учебных дней сюда не подставляются. Сначала определи, что перед тобой, и только потом решай: на экзамене тему никто не подписывает.

6 problems at the strongest available level: this set covers every section you have completed. It is a separate attempt—answers from study days are not carried over. Identify what you are looking at before you solve it; the exam does not label the topic.

Собрать новый набор

S0801Уровень ШАДМатанализуровень ШАД · приём симметризации

Вычислите $\displaystyle\int_0^{\pi/2}\frac{dx}{1 + \tan^{\sqrt{2}}x}$. Ответ округлите до четырёх знаков после запятой.

Evaluate $\displaystyle\int_0^{\pi/2}\frac{dx}{1 + \tan^{\sqrt{2}}x}$. Round your answer to four decimal places.

ответ

Подсказка / Hint

Показатель $\sqrt2$ выглядит абсурдно — это подсказка, что ответ от него не зависит. Попробуй отражение $x \to \frac{\pi}{2} - x$.

The exponent $\sqrt2$ looks unnatural, suggesting that the answer does not depend on it. Try the reflection $x \to \frac{\pi}{2} - x$.

Решение / Solution

Обозначим интеграл $I$ и отразим отрезок: $a + b - x = \frac{\pi}{2} - x$. Отрезок переходит сам в себя, а $\tan\left(\frac\pi2 - x\right) = \frac{1}{\tan x}$:

$$I = \int_0^{\pi/2}\frac{dx}{1 + \tan^{-\sqrt2}x}$$

Домножим числитель и знаменатель на $\tan^{\sqrt2}x$:

$$I = \int_0^{\pi/2}\frac{\tan^{\sqrt2}x\,dx}{\tan^{\sqrt2}x + 1}$$

Теперь сложим два выражения для одного и того же $I$ — ровно как в задаче b0804:

$$2I = \int_0^{\pi/2}\frac{1 + \tan^{\sqrt2}x}{1 + \tan^{\sqrt2}x}\,dx = \int_0^{\pi/2}dx = \frac{\pi}{2}$$$$I = \frac{\pi}{4} \approx 0.7854$$

Как узнавать этот тип

Абсурдный параметр в условии — $\sqrt2$, $2025$, «произвольное $s$» — почти всегда означает, что ответ от него не зависит, и решать надо трюком, а не вычислением. Составители ставят такие параметры именно как сигнал.

Первообразная у этой функции существует — функция непрерывна, — но через элементарные функции не выражается: выписать её не поможет никакая техника. Отражение отрезка тоже не упрощает подынтегральное выражение, оно даёт второе выражение для того же числа, и всю работу делает сложение.

Denote the integral by $I$ and reflect the interval: $a + b - x = \frac{\pi}{2} - x$. The interval maps onto itself, and $\tan\left(\frac\pi2 - x\right) = \frac{1}{\tan x}$:

$$I = \int_0^{\pi/2}\frac{dx}{1 + \tan^{-\sqrt2}x}$$

Multiply the numerator and denominator by $\tan^{\sqrt2}x$:

$$I = \int_0^{\pi/2}\frac{\tan^{\sqrt2}x\,dx}{\tan^{\sqrt2}x + 1}$$

Now add the two expressions for the same $I$, exactly as in problem b0804:

$$2I = \int_0^{\pi/2}\frac{1 + \tan^{\sqrt2}x}{1 + \tan^{\sqrt2}x}\,dx = \int_0^{\pi/2}dx = \frac{\pi}{2}$$$$I = \frac{\pi}{4} \approx 0.7854$$

How to recognize this type of problem

An unnatural parameter in the statement—$\sqrt2$, $2025$, or “an arbitrary $s$”—almost always signals that the answer is independent of it and that the problem requires a structural argument rather than direct computation. Problem setters use such parameters deliberately as a clue.

This function has an antiderivative because it is continuous, but that antiderivative cannot be expressed in elementary functions, so no standard integration technique will produce a useful formula. Reflecting the interval does not simplify the integrand either; instead, it gives a second expression for the same quantity, and adding the two expressions completes the argument.

уверенность1 — угадал, 5 — уверен полностью

В журнал ошибок

S0901Уровень ШАДЛиналЭкзамен ШАД 2024, задача E «Давай поиграем»

Случайный вектор $\Psi$ в $\mathbb{R}^{n}$ имеет стандартное нормальное распределение (нулевое среднее, единичная матрица ковариаций). Два игрока заранее зафиксировали векторы $a$ и $l$.

В раунде $k$ разыгрывается независимая реализация $\psi_k$. Лёша получает одно очко, если

$$\sign\langle\psi_k, a\rangle \cdot \sign\langle\psi_k, l\rangle > 0$$

Артём получает одно очко, если это произведение отрицательно. Очки только начисляются: за проигранный раунд ничего не снимается. Случай нулевого произведения имеет нулевую вероятность и в счёт не идёт.

К чему стремится отношение числа очков Артёма к числу сыгранных раундов при $k \to \infty$? Дайте ответ для $a = (1, 0)$ и $l = (1, 1)$. Ответ округлите до четырёх знаков после запятой.

A random vector $\Psi$ in $\mathbb{R}^{n}$ has a standard normal distribution, with zero mean and the identity covariance matrix. Two players have fixed vectors $a$ and $l$ in advance.

In round $k$, an independent realization $\psi_k$ is drawn. Lyosha receives one point if

$$\sign\langle\psi_k, a\rangle \cdot \sign\langle\psi_k, l\rangle > 0$$

Artyom receives one point if this product is negative. Points are only awarded: no points are deducted for losing a round. The event that the product is zero has probability zero and is not included.

As $k \to \infty$, what does the ratio of Artyom's score to the number of rounds played approach? Give your answer for $a = (1, 0)$ and $l = (1, 1)$. Round your answer to four decimal places.

ответ

Подсказка / Hint

Исход раунда зависит только от знаков скалярных произведений, а значит только от угла. Длины векторов роли не играют.

The outcome of a round depends only on the signs of the inner products, and hence only on the angle. The lengths of the vectors do not matter.

Решение / Solution

Шаг 1. Понижение размерности. Пусть $\mathcal{L}$ — плоскость, натянутая на $a$ и $l$. Для любого вектора $\psi$ рассмотрим его ортогональную проекцию $\psi_1$ на $\mathcal{L}$. Разность $\psi - \psi_1$ перпендикулярна плоскости, а значит и обоим векторам:

$$\langle a, \psi\rangle = \langle a, \psi_1\rangle, \qquad \langle l, \psi\rangle = \langle l, \psi_1\rangle$$

Исход раунда зависит только от проекции. Задача из $n$-мерной стала плоской.

Шаг 2. Свойство нормального распределения. Проекция стандартного нормального вектора на плоскость — снова стандартный нормальный вектор, но размерности 2. Его направление распределено равномерно по окружности.

Шаг 3. Геометрическая вероятность. Условие $\langle\psi_1, a\rangle = 0$ задаёт на плоскости прямую, перпендикулярную $a$; условие $\langle\psi_1, l\rangle = 0$ — прямую, перпендикулярную $l$. Угол между этими двумя прямыми равен углу $\phi$ между самими $a$ и $l$. Две прямые режут плоскость на четыре сектора: два углового размера $\phi$, где знаки скалярных произведений расходятся, и два размера $\pi - \phi$, где знаки совпадают. Проверка: $2\phi + 2(\pi-\phi) = 2\pi$. Какая из двух пар шире, зависит от того, острый угол $\phi$ или тупой, и на ответ это не влияет.

Очко Артёму даётся ровно тогда, когда направление попало в сектор размера $\phi$, а направление распределено равномерно, значит

$$\P(\text{очко Артёму}) = \frac{2\phi}{2\pi} = \frac{\phi}{\pi}$$

Это ровно та формула, которая была получена на плоскости в задаче b0904.

Шаг 4. Закон больших чисел. Раунды независимы и одинаково распределены, очки только начисляются, поэтому число очков Артёма — это просто число выигранных им раундов. Отношение к числу раундов есть частота события, и она стремится к его вероятности:

$$\frac{\text{очки Артёма}}{\text{число раундов}} \longrightarrow \frac{\phi}{\pi} = \frac{1}{\pi}\arccos\frac{\langle a,l\rangle}{\|a\|\,\|l\|}$$

Подставляем данные. $\langle a,l\rangle = 1$, $\|a\| = 1$, $\|l\| = \sqrt2$, значит $\cos\phi = \frac{1}{\sqrt2}$ и $\phi = \frac{\pi}{4}$.

$$\frac{\phi}{\pi} = \frac{\pi/4}{\pi} = \frac14 = 0.2500$$

Где здесь теряют ответ

Соблазн посчитать «перевес»: если обозначить долю раундов Лёши через $p = 1 - \phi/\pi$, то разность $p - (1 - p) = 2p - 1$ равна $0.5$ и выглядит красиво. Но это ответ на другой вопрос — так считают, когда за проигранный раунд снимают очко. В нашем условии сказано прямо, что очки только начисляются, поэтому нужна сама доля, а не перевес.

Проверка здравым смыслом: доля обязана лежать в $[0, 1]$ и при $\phi \to 0$ (векторы почти сонаправлены) стремиться к нулю — Артёму почти нечего ловить. Формула $\phi/\pi$ этому отвечает.

Три идеи в одной задаче

Первая: проекция сохраняет скалярные произведения с векторами подпространства — поэтому многомерную задачу можно сплющить до плоской.

Вторая: направление нормального вектора распределено равномерно — здесь смыкаются линейная алгебра и геометрическая вероятность второго дня.

Третья: закон больших чисел превращает «отношение очков к раундам» в вероятность одного раунда.

Ни одна из них по отдельности не сложна, и каждая вполне может прийти на YMLS. Задача уровня ШАД отличается тем, что требует соединить все три.

Step 1. Reduce the dimension. Let $\mathcal{L}$ be the plane spanned by $a$ and $l$. For any vector $\psi$, let $\psi_1$ be its orthogonal projection onto $\mathcal{L}$. The difference $\psi - \psi_1$ is perpendicular to the plane and therefore to both vectors:

$$\langle a, \psi\rangle = \langle a, \psi_1\rangle, \qquad \langle l, \psi\rangle = \langle l, \psi_1\rangle$$

Thus, the outcome of the round depends only on the projection. The $n$-dimensional problem has been reduced to a planar one.

Step 2. Use a property of the normal distribution. The projection of a standard normal vector onto a plane is again a standard normal vector, now in two dimensions. Its direction is uniformly distributed on the circle.

Step 3. Calculate the geometric probability. In the plane, the condition $\langle\psi_1, a\rangle = 0$ defines a line perpendicular to $a$, while $\langle\psi_1, l\rangle = 0$ defines a line perpendicular to $l$. Rotating both vectors by $\frac{\pi}{2}$ preserves their angular separation modulo $\pi$. The four boundary rays divide the plane into alternating sectors: two with angular measure $\phi$, where the signs of the inner products differ, and two with angular measure $\pi - \phi$, where the signs agree. As a check, $2\phi + 2(\pi-\phi) = 2\pi$. Which pair of sectors is wider depends on whether $\phi$ is acute or obtuse, but this does not affect the formula.

Artyom receives a point precisely when the direction lies in one of the sectors of angular measure $\phi$. Since the direction is uniformly distributed,

$$\P(\text{Artyom scores}) = \frac{2\phi}{2\pi} = \frac{\phi}{\pi}$$

This is exactly the formula derived for the plane in problem b0904.

Step 4. Apply the law of large numbers. The rounds are independent and identically distributed, and points are only awarded, so Artyom's score is simply the number of rounds he wins. The ratio of his score to the number of rounds is the frequency of this event, which converges to its probability:

$$\frac{\text{Artyom's score}}{\text{number of rounds}} \longrightarrow \frac{\phi}{\pi} = \frac{1}{\pi}\arccos\frac{\langle a,l\rangle}{\|a\|\,\|l\|}$$

Substitute the given vectors. We have $\langle a,l\rangle = 1$, $\|a\| = 1$, and $\|l\| = \sqrt2$. Hence $\cos\phi = \frac{1}{\sqrt2}$ and $\phi = \frac{\pi}{4}$.

$$\frac{\phi}{\pi} = \frac{\pi/4}{\pi} = \frac14 = 0.2500$$

A common wrong turn

It is tempting to calculate the score margin. If $p = 1 - \phi/\pi$ denotes Lyosha's share of the rounds, then the difference $p - (1 - p) = 2p - 1$ equals $0.5$, which looks appealing. But that answers a different question: this calculation would apply if a point were deducted for losing a round. The problem explicitly states that points are only awarded, so we need the share itself, not the margin.

As a reasonableness check, the answer must lie in $[0, 1]$ and approach zero as $\phi \to 0$, when the vectors point in nearly the same direction and Artyom has almost no chance of scoring. The formula $\phi/\pi$ satisfies both conditions.

Three ideas in one problem

First: projection preserves inner products with vectors in the subspace, allowing us to flatten a high-dimensional problem into a planar one.

Second: the direction of a normal vector is uniformly distributed. This connects linear algebra with the geometric probability studied on Day 2.

Third: the law of large numbers turns the ratio of points to rounds into the probability of the outcome in a single round.

None of these ideas is difficult on its own, and any one of them could readily appear on YMLS. What makes this a SHAD-level problem is the need to combine all three.

уверенность1 — угадал, 5 — уверен полностью

В журнал ошибок

S0401Уровень ШАДСлучайные величиныОлимпиада ШАД 2025, задача «Инклюзивный марьяж»

Из стандартной колоды в 52 карты вынимают карты по одной без возвращения. Найдите математическое ожидание числа карт, которое нужно вынуть, чтобы среди них оказались и король, и дама. Считается общее число вынутых карт, включая последнюю. Ответ округлите до четырёх знаков после запятой.

Cards are drawn without replacement from a standard 52-card deck. Find the expected number of cards that must be drawn until both a king and a queen have appeared, counting the final card. Round to four decimal places.

ответ

Подсказка / Hint

И «номер первого короля», и «номер первой дамы» считаются леммой о промежутках. Максимум из них напрямую не считается: вспомни тождество $\max + \min = $ сумма и подумай, что такое здесь минимум.

The positions of the first king and the first queen are both handled by the gaps lemma. Their maximum is harder to compute directly: recall the identity $\max + \min = $ sum, and interpret the minimum here.

Решение / Solution

Лемма о промежутках. В колоде из $n$ карт помечены $k$. Среднее число карт, которое нужно вынуть до первой помеченной включительно, равно

$$\E = \frac{n+1}{k+1}$$

Доказательство закольцовыванием — самое короткое из существующих. Добавим сверху ещё одну помеченную карту и замкнём колоду из $n+1$ карты в круг. Случайно повернём круг. Теперь помеченных карт $k+1$, и они разбивают круг на $k+1$ дугу из непомеченных карт. Дуги переходят друг в друга поворотом, значит в среднем одинаковы, и в каждой $\frac{n-k}{k+1}$ карт.

Считая от добавленной карты, до первой настоящей помеченной надо пройти одну дугу и саму помеченную карту:

$$\E = \frac{n-k}{k+1} + 1 = \frac{n+1}{k+1}$$

Решение задачи. Пусть $\xi$ — номер первого короля, $\eta$ — первой дамы. Нужно $\E\max\{\xi, \eta\}$. Максимум напрямую считать тяжело, но выручает тождество

$$\max\{\xi,\eta\} + \min\{\xi,\eta\} = \xi + \eta$$

Здесь $\min\{\xi,\eta\}$ — момент появления первой из восьми выделенных карт (четыре короля и четыре дамы вместе). Все три величины считаются по лемме:

$$\E\xi = \E\eta = \frac{52+1}{4+1} = \frac{53}{5}, \qquad \E\min = \frac{52+1}{8+1} = \frac{53}{9}$$$$\E\max = \frac{53}{5} + \frac{53}{5} - \frac{53}{9} = \frac{689}{45} \approx 15.3111$$

Что забрать на YMLS

Два приёма, каждый из которых работает далеко за пределами этой задачи.

Первый — лемма $\frac{n+1}{k+1}$. Закрывает целый класс задач «сколько тянуть до первого нужного». В малом размере ты вывел её индикаторами в задаче b0405, здесь она применена трижды подряд — к королям, к дамам и к восьми картам сразу.

Второй — тождество $\max + \min$. Если максимум считать трудно, а минимум легко, считай минимум и вычитай. Это общий приём, а не трюк для карт: сегодня он уже работал в задаче про два кубика и в задаче про две равномерные точки.

Gaps lemma. In a deck of $n$ cards, suppose $k$ are marked. The expected number of cards drawn up to and including the first marked card is

$$\E = \frac{n+1}{k+1}$$

Circular proof. Add one marked card to the top and join the $n+1$ cards into a circle, then rotate the circle uniformly at random. The $k+1$ marked cards divide the circle into $k+1$ gaps of unmarked cards. Rotation permutes these gaps, so they have the same expected size, $\frac{n-k}{k+1}$.

Starting from the added card, reaching the first original marked card requires crossing one gap and then drawing the marked card itself:

$$\E = \frac{n-k}{k+1} + 1 = \frac{n+1}{k+1}$$

Apply the lemma. Let $\xi$ be the position of the first king and $\eta$ the position of the first queen. We need $\E\max\{\xi,\eta\}$. Use

$$\max\{\xi,\eta\} + \min\{\xi,\eta\} = \xi + \eta$$

Here $\min\{\xi,\eta\}$ is the position of the first among eight marked cards: the four kings and four queens together. The lemma gives

$$\E\xi = \E\eta = \frac{52+1}{4+1} = \frac{53}{5}, \qquad \E\min = \frac{52+1}{8+1} = \frac{53}{9}$$$$\E\max = \frac{53}{5} + \frac{53}{5} - \frac{53}{9} = \frac{689}{45} \approx 15.3111$$

What to carry into YMLS

Two techniques here apply far beyond this problem.

First, the $\frac{n+1}{k+1}$ gaps lemma. It resolves an entire class of “how many draws until the first target?” questions. You derived its small version using indicators in b0405; here it is applied three times—to kings, queens, and all eight marked cards.

Second, the identity $\max + \min$. When the maximum is hard and the minimum easy, compute the minimum and subtract. This is a general method, not a card trick; it already appeared in the problems about two dice and two uniform variables.

уверенность1 — угадал, 5 — уверен полностью

В журнал ошибок

S0301Уровень ШАДВероятностьпарадокс Гарднера, уровень ШАД

У человека двое детей. Известно, что хотя бы один из них — мальчик, родившийся во вторник. Найдите вероятность того, что оба ребёнка мальчики.

Считайте, что пол и день недели каждого ребёнка независимы, все семь дней и оба пола равновероятны. Ответ округлите до четырёх знаков после запятой.

A person has two children. It is known that at least one is a boy born on Tuesday. Find the probability that both children are boys.

Assume that each child's sex and day of birth are independent, with all seven days and both sexes equally likely. Round the answer to four decimal places.

ответ

Подсказка / Hint

Опиши каждого ребёнка парой «пол, день недели». Сколько всего таких пар и сколько комбинаций для двоих детей?

Describe each child by the pair “sex, day of the week.” How many such pairs are possible, and how many combinations are there for two children?

Решение / Solution

Каждый ребёнок описывается парой (пол, день недели) — всего $2 \cdot 7 = 14$ равновозможных вариантов. Для двоих детей: $14^2 = 196$ исходов.

Знаменатель — исходы, где есть мальчик-вторник. Считаем дополнением. Исходы, где мальчика-вторника нет: каждый ребёнок — один из $14 - 1 = 13$ прочих вариантов, то есть $13^2 = 169$. Значит подходящих $196 - 169 = 27$.

Числитель — оба мальчики и хотя бы один родился во вторник. Всего пар мальчиков $7^2 = 49$. Из них без вторника $6^2 = 36$. Остаётся $49 - 36 = 13$.

$$\P = \frac{13}{27} \approx 0.4815$$

Почему это ломает интуицию

Три условия про одну и ту же семью дают три разных ответа: «старший — мальчик» даёт $\frac12$ (задача w0302), «хотя бы один мальчик» — $\frac13$ (задача w0303), «хотя бы один мальчик, рождённый во вторник» — $\frac{13}{27} \approx 0.48$.

Казалось бы, день недели — посторонняя деталь, а ответ меняется. Причина: она меняет пространство исходов. Никакого словесного правила «чем подробнее условие, тем ответ ближе к $\frac12$» при этом нет: условие «хотя бы один мальчик, родившийся в понедельник или во вторник» тоже подробное, а даёт $\frac{49 - 5^2}{196 - 12^2} = \frac{24}{52} = \frac{6}{13} \approx 0.4615$ — меньше, чем один вторник. Ряд $\frac13$, $\frac{6}{13}$, $\frac{13}{27}$, $\frac12$ выстраивается только счётом, а в уроке стоит контрпример, где адресное условие роняет ответ до нуля.

Мораль для экзамена одна: выписывай $\Omega$ полностью и считай, а не рассуждай словами. В этой теме словесная интуиция подводит систематически.

Each child is described by a pair (sex, day of the week), giving $2 \cdot 7 = 14$ equally likely possibilities. Two children therefore produce $14^2 = 196$ outcomes.

Denominator—outcomes with a Tuesday-born boy. Use the complement. If there is no Tuesday-born boy, each child has one of the other $14 - 1 = 13$ descriptions, giving $13^2 = 169$ outcomes. Thus the condition leaves $196 - 169 = 27$ outcomes.

Numerator—both are boys and at least one was born on Tuesday. There are $7^2 = 49$ pairs of boys, of which $6^2 = 36$ contain no Tuesday birth. This leaves $49 - 36 = 13$.

$$\P = \frac{13}{27} \approx 0.4815$$

Why intuition fails here

Three conditions about the same family produce three different answers: “the older child is a boy” gives $\frac12$ (w0302), “at least one child is a boy” gives $\frac13$ (w0303), and “at least one is a boy born on Tuesday” gives $\frac{13}{27} \approx 0.48$.

The weekday may look irrelevant, but it changes the sample space. There is no verbal rule saying that a more detailed condition makes the answer closer to $\frac12$. For example, “at least one boy born on Monday or Tuesday” gives $\frac{49 - 5^2}{196 - 12^2} = \frac{24}{52} = \frac{6}{13} \approx 0.4615$, less than the Tuesday-only answer. The sequence $\frac13$, $\frac{6}{13}$, $\frac{13}{27}$, $\frac12$ emerges only from counting; the lesson even contains a counterexample where a condition specifying a particular child drives the answer to zero.

The exam lesson is simple: write out $\Omega$ completely and count instead of reasoning verbally. Verbal intuition is systematically unreliable in this topic.

уверенность1 — угадал, 5 — уверен полностью

В журнал ошибок

S0101Уровень ШАДКомбинаторикаЭкзамен ШАД 2024, задача D «Координаты в квадрате»

На клетчатой бумаге нарисован квадрат $n \times n$ по линиям сетки. Левая нижняя клетка имеет координаты $(1,1)$, правая верхняя — $(n,n)$. Внутри него по линиям сетки рисуют квадрат $(n-1) \times (n-1)$, внутри того — квадрат $(n-2) \times (n-2)$, и так далее, пока не получится квадрат $1 \times 1$. Он оказался клеткой с координатами $(x, y)$.

Сколько существует различных последовательностей квадратов с таким свойством? Дайте ответ для $n = 10$, $x = 4$, $y = 7$.

An $n \times n$ square is drawn along the grid lines of graph paper. The bottom-left cell has coordinates $(1,1)$ and the top-right cell has coordinates $(n,n)$. Inside it, an $(n-1) \times (n-1)$ square is drawn along the grid lines; inside that, an $(n-2) \times (n-2)$ square is drawn, and so on until a $1 \times 1$ square remains. The final square is the cell with coordinates $(x, y)$.

How many different sequences of squares have this property? Give the answer for $n = 10$, $x = 4$, and $y = 7$.

ответ

Подсказка / Hint

Как из квадрата $k \times k$ получается квадрат $(k-1) \times (k-1)$? Сколько у этого шага независимых решений?

How can a $(k-1) \times (k-1)$ square be obtained from a $k \times k$ square? How many independent choices does each step involve?

Решение / Solution

Ключевое наблюдение. Квадрат $(k-1) \times (k-1)$ помещается внутрь квадрата $k \times k$ ровно четырьмя способами: нужно отрезать один столбец — левый или правый — и одну строку — верхнюю или нижнюю. Причём отрезания столбцов и строк независимы.

Всего шагов $n - 1$. На каждом шаге мы отрезаем один столбец (слева или справа) и одну строку (сверху или снизу).

Столбцы. Закодируем историю отрезаний столбцов строкой из $n-1$ символов: Л, если на этом шаге отрезали левый столбец, П — если правый. Если за все $n-1$ шагов слева отрезали $x - 1$ столбец, то финальная клетка имеет первую координату $x$. Строк с ровно $x-1$ буквой Л ровно $\binom{n-1}{x-1}$ — вопрос снова свёлся к «на каких местах стоят символы одного вида».

Строки. Аналогично: $\binom{n-1}{y-1}$.

Любая комбинация даёт свою последовательность, поэтому перемножаем:

$$N = \binom{n-1}{x-1}\binom{n-1}{y-1}$$

Подставляем $n = 10$, $x = 4$, $y = 7$:

$$\binom{9}{3}\binom{9}{6} = 84 \cdot 84 = 7056$$

Что здесь стоит забрать

Приём разделения на независимые оси. Задача выглядела как перебор вложенных квадратов, а свелась к двум независимым строкам — «в каком порядке отрезали столбцы» и «в каком порядке отрезали строки». Как только удаётся расщепить задачу на независимые части, ответ становится произведением. Этот ход встретится ещё много раз.

Key observation. A $(k-1) \times (k-1)$ square can be placed inside a $k \times k$ square in exactly four ways: remove either the left or the right column, and either the top or the bottom row. The choices for rows and columns are independent.

There are $n - 1$ steps in total. At each step, one column (left or right) and one row (top or bottom) are removed.

Columns. Encode the history of column removals by a string of $n-1$ symbols: L if the left column was removed at that step and R if the right column was removed. The final cell has first coordinate $x$ exactly when a total of $x - 1$ columns were removed from the left. The number of strings with exactly $x-1$ occurrences of L is $\binom{n-1}{x-1}$; once again, the problem reduces to choosing the positions occupied by one type of symbol.

Rows. Similarly, there are $\binom{n-1}{y-1}$ possible row-removal histories.

Every pair of histories gives a distinct sequence of squares, so we multiply:

$$N = \binom{n-1}{x-1}\binom{n-1}{y-1}$$

Substituting $n = 10$, $x = 4$, and $y = 7$ gives

$$\binom{9}{3}\binom{9}{6} = 84 \cdot 84 = 7056$$

Main takeaway

Split the problem along independent axes. What looked like a search through nested squares becomes two independent strings: the order in which columns were removed and the order in which rows were removed. Whenever a problem splits into independent parts, the total count is the product of the counts for those parts. This technique will return often.

уверенность1 — угадал, 5 — уверен полностью

В журнал ошибок

S1101Уровень ШАДАлгоритмыОлимпиада ШАД 2025, задача «Похожие геномы»

Мерой похожести двух вирусов служит побитовое исключающее ИЛИ (XOR) их геномов: чем меньше XOR, тем более похожи вирусы.

В базе лежат геномы

[38, 18, 7, 52, 13, 25, 60, 3, 44, 29]

Найдите наименьший возможный XOR пары геномов, стоящих на разных позициях.

The similarity of two viruses is measured by the bitwise exclusive OR (XOR) of their genomes: the smaller the XOR, the more similar the viruses.

The database contains the genomes

[38, 18, 7, 52, 13, 25, 60, 3, 44, 29]

Find the smallest possible XOR of two genomes at distinct positions.

ответ

Подсказка / Hint

Для десяти чисел хватит перебора сорока пяти пар — приём из b1101, только вместо суммы XOR. Быстрый ход — тот же спуск по разрядам, что в мосте b1105, но в обратную сторону. А дальше подумай, как отвечать на такой запрос, если чисел $2 \cdot 10^5$ и они добавляются по одному.

With ten numbers, enumerating all forty-five pairs is enough; this is the technique from b1101, with XOR instead of addition. The fast approach uses the same bitwise descent as bridge problem b1105, but in the opposite direction. Then consider how to answer the query if there are $2 \cdot 10^5$ numbers arriving one by one.

Решение / Solution

Ответ для наших данных: 4 — пара $7$ и $3$: $7 \oplus 3 = 0111_2 \oplus 0011_2 = 0100_2 = 4$.

from itertools import combinations
print(min(x ^ y for x, y in combinations(G, 2)))   # 4

Перебор пар — это $O(n^2)$, здесь всего 45 пар. На олимпиадных ограничениях ($n$ до $2\cdot10^5$, числа до $2^{30}$) он не проходит, и нужен другой подход.

Правильное решение — префиксное дерево (бор) на битах.

Храним двоичные представления чисел в дереве как строки длины $K = 30$, от старших разрядов к младшим. При добавлении нового числа $X$ делаем два действия:

Ищем в боре число $Y$, дающее минимальный XOR с $X$. Спускаемся от корня; на каждой глубине пытаемся пойти по тому же биту, что у $X$ — тогда в этом разряде XOR даст ноль. Если такого перехода нет, идём по единственному имеющемуся.
Вставляем $X$ в бор.

Ответ поддерживаем как минимум по всем добавлениям.

Почему жадный спуск корректен. Пусть на глубине $d$ можно пойти двумя путями. Совпадение бита даёт в этом разряде ноль, несовпадение — единицу, то есть вклад $2^{K-d}$. Но по пункту блока «Мост» один старший разряд перевешивает все младшие вместе взятые, поэтому совпадение в старшем разряде выгоднее любого выигрыша во всех младших. Жадность оптимальна.

Сложность: $O(NK)$ по времени и памяти, где $K$ — число бит.

Проверка третьим способом

Работает правило из блока «Триггеры»: минимальный XOR всегда достигается на паре соседей в отсортированном порядке. Вот его вывод в две строки. Пусть $x < y < z$, и пусть $b$ — самый старший разряд, в котором $x$ и $z$ различаются: в нём у $x$ ноль, у $z$ единица, поэтому $x \oplus z \ge 2^{b}$. Все разряды старше $b$ у $x$ и $z$ совпадают, а $y$ лежит между ними, поэтому в старших разрядах $y$ совпадает с обоими; в самом разряде $b$ у $y$ стоит либо ноль, и тогда $x \oplus y < 2^{b}$, либо единица, и тогда $y \oplus z < 2^{b}$. В обоих случаях какая-то из более тесных пар строго лучше крайней — значит пару, между членами которой лежит третье число, можно не проверять.

Отсортируем: 3, 7, 13, 18, 25, 29, 38, 44, 52, 60 — и проверим только девять соседних пар вместо сорока пяти. Их XOR равны 4, 10, 31, 11, 4, 59, 10, 24, 8; наименьшее значение 4 достигается дважды: $3 \oplus 7 = 4$ и $25 \oplus 29 = 4$. Ответ сошёлся с перебором, и это независимая проверка, а не пересчёт того же самого.

Что забрать

Идея «старший разряд важнее всех младших вместе» — универсальная для битовых задач. Она превращает переборную задачу в жадный спуск по дереву, то есть в то же деление пополам, что и бинарный поиск, только режется не отрезок чисел, а множество кандидатов по очередному биту.

На YMLS такое вряд ли придёт в полном объёме, но сам приём «работать с числами поразрядно, от старших к младшим» вполне может понадобиться.

For the given data, the answer is 4, attained by 7 and 3: $7 \oplus 3 = 0111_2 \oplus 0011_2 = 0100_2 = 4$.

from itertools import combinations
print(min(x ^ y for x, y in combinations(G, 2)))   # 4

Pair enumeration takes $O(n^2)$ time and involves only 45 pairs here. It is too slow under olympiad constraints ($n$ up to $2\cdot10^5$, values below $2^{30}$), so a different approach is required.

The appropriate solution is a binary prefix tree, or binary trie.

Store the binary representations of the numbers in a tree as strings of length $K=30$, from the most significant bit to the least significant. When a new number $X$ arrives, perform two operations:

Find a number $Y$ in the trie minimizing its XOR with $X$. Descend from the root. At each depth, first try the branch with the same bit as $X$, which contributes zero at this position. If that branch does not exist, take the only available branch.
Insert $X$ into the trie.

Maintain the answer as the minimum over all insertions.

Why the greedy descent is correct. Suppose both branches are available at depth $d$. Matching the bit contributes zero at this position, while differing contributes one, with value $2^{K-d}$. One more significant bit outweighs all less significant bits combined, as established in the Bridge section. Therefore matching the more significant bit is preferable to any possible gain below it, and the greedy choice is optimal.

The time and space complexity are $O(NK)$, where $K$ is the number of bits.

A third method for checking

The rule from the Triggers section applies: the minimum XOR is always attained by two adjacent values in sorted order. Here is the proof. Let $x<y<z$, and let $b$ be the most significant bit at which $x$ and $z$ differ. At this bit, $x$ has zero and $z$ has one, so $x\oplus z \ge 2^b$. All bits above $b$ coincide in $x$ and $z$. Since $y$ lies between them, it agrees with both in those higher bits. At bit $b$, either $y$ has zero, giving $x\oplus y < 2^b$, or it has one, giving $y\oplus z < 2^b$. In either case, a closer pair is strictly better than the outer pair. Thus a pair with a third number between its members never needs to be checked.

Sort the values: 3, 7, 13, 18, 25, 29, 38, 44, 52, 60. Check only nine adjacent pairs rather than forty-five. Their XORs are 4, 10, 31, 11, 4, 59, 10, 24, 8. The minimum, 4, is attained twice: $3 \oplus 7 = 4$ and $25 \oplus 29 = 4$. This agrees with exhaustive search and is an independent check.

The takeaway

The principle “a more significant bit outweighs all less significant bits combined” is universal in bitwise problems. It turns an exhaustive search into a greedy tree descent: the same kind of halving as binary search, except that the candidate set is partitioned by the next bit rather than by a numeric interval.

A full-strength version is unlikely on YMLS, but the underlying technique of processing numbers bit by bit, from most significant to least significant, may well be useful.

уверенность1 — угадал, 5 — уверен полностью

В журнал ошибок