[Из песочницы] Разбор вступительного экзамена ШАД-2015 и воспоминания выпускника 2017 года
Введение
В мае далёкого 2015 года я заканчивал бакалавриат факультета общей и прикладной физики МФТИ. В основном я занимаюсь квантовой теорией поля, но в тот момент я решил, что хотелось бы больше вникнуть в современный мир компьютерных наук, что можно попробовать совместить МФТИ с ШАД Yandex (две магистратуры). ШАД тогда уже был у всех на слуху, вокруг только и твердили, какой там жёсткий курс алгоритмов, мне понравился сайт (лол), тематика курсов, и я решился поступать.
В этом посте я хотел бы рассказать о том, как происходило моё поступление в ШАД, рассказать своё решение экзаменационного варианта (разборов ШАДовских заданий на просторах рунета не очень-то много) и поговорить о том, что понравилось / не понравилось в этом замечательном заведении.
Онлайн-отбор дался без особого труда, в 2015 году давали 12 задач на месяц, из которых больше половины были комбинаторикой с ответом в виде числа, и только ленивый бы не написал на каждую задачу скриптик, чтобы проверить ответ (одну задачу я вообще решил только так). Нынче, насколько мне известно, дают какое-то ограниченное время, в пределах нескольких часов.
После онлайн-этапа меня пригласили на экзамен. К экзамену я готовился около недели, и сам по себе он доставил мне большое удовольствие. За 4 часа необходимо было решить 7 задач по математике и составить один алгоритм (всего 8 заданий). Метематика требуется самая разнообразная: линейная алгебра, мат. анализ (чуть ли не $inline$\epsilon-\delta$inline$ формализм), комбинаторика и теор. вер., графы, преобразование Фурье и т.д. Мне кажется, это очень правильно от поступающих требовать именно знания математики, а не каких-нибудь там языков или скиллов (вообще в дальнейшем оказалось, что ШАД ориентирован именно на знание по сути, а не на технические детали).
Этот пост я хотел бы посвятить разбору варианта, который достался мне на экзамене. Закинувшись тремя чашками эспрессо и настойкой элеутерококка, я смог чистенько решить семь задач из восьми, и на восьмую я даже не успел посмотреть.
Мой экзамен
Задача 1
Квадратная матица $inline$A$inline$ такова, что $inline$\mbox{tr} AX = 0$inline$ для любой бесследовой $inline$X$inline$. Докажите, что матрица $inline$X$inline$ скалярная.
Решение
Эта задача сразу напомнила мне другую, немного более сложную задачу с физтеховского экзамена по линейной алгебре в первом семестре, где нужно было доказать, что коммутирует со всеми матрицами только скалярная матрица. Как и там, здесь нужно воспользоваться тем, что матрица $inline$X$inline$ любая, а значит, рассматривая матрицы $inline$X$inline$ различного вида, мы можем наложить ограничения на марицу $inline$A$inline$.
Сперва рассмотрим матрицу $inline$X$inline$ вида $inline$X_{i j} = \delta_{ik} \delta_{j l}$inline$, то есть матрицу, у которой все элементы 0 кроме единички, стоящей в $inline$k$inline$-той строке на $inline$l$inline$-той позиции. Так как мы помним, что $inline$X$inline$ — бесследовая матрица, $inline$l \neq k$inline$. Тогда уравнение из условия переписывается в виде (если в формуле индекс повторяется дважды, по нему подразумевается суммирование)
$$display$$ \mbox{tr}AX = A_{ij} X_{ji} = A_{ij} \delta_{ik} \delta_{jl} = A_{kl} = 0\;(k \neq l).$$display$$
То есть, лёгким движением руки мы доказали, что в матрице $inline$A$inline$ вне диагонали стоят только ноли. Если отбросить индексы, то мы всего лишь умножили матрицу $inline$A$inline$ на матрицу специального вида и получили некое ограничение.
Теперь мы знаем, что матрица $inline$A = \mbox{diag}(\lambda_1, \lambda_2, \ldots, \lambda_n)$inline$ — диагональная. Как доказать, что все её собственные числа равны? Для этого рассмотрим теперь матрицы $inline$X = \delta_{i l} \delta_{j l} — \delta_{i k} \delta_{j k}$inline$, то есть матрицы, у которых на $inline$l$inline$-том элементе диагонали стоит $inline$+1$inline$, а на $inline$k$inline$-том — $inline$-1$inline$. Аналогично умножив матрицы и взяв след, мы получаем $inline$\lambda_l — \lambda_k = 0$inline$ (след оказался равен всего лишь разности пары собственных чисел). По условию для любых $inline$k,\; l$inline$ это равенство должно выполняться, откуда следует, что все собственные числа равны, задача решена.
Задача 2
Придя на письменный экзамен в ШАД, студенты поняли, что среди любых четырёх человек хотя бы один уже знаком с тремя оставшимися. Докажите, что тогда среди любых четырёх человек хотя бы один уже знаком со всеми остальными студентами.
Решение
Эта задача меня чуть не убила, на экзамене я придумал ужасно сложное и убогое решение. Вот оно. Рекомендую в процессе чтения рисовать различные варианты в виде графов, тогда становится даже не так ужасно!
Рассмотрим произвольную четвёрку студентов $inline$A$inline$, $inline$B$inline$, $inline$C$inline$, $inline$D$inline$. Пусть, от противного, из них никто не знаком со всеми остальными студентами. Но по условию один из студентов (пусть это будет $inline$A$inline$) знает всех оставшихся троих. От противного мы заключили, что есть некий другой студент $inline$X$inline$, которого $inline$A$inline$ не знает.
В этом месте сделаем финт ушами и рассмотрим четвёрку $inline$A$inline$, $inline$B$inline$, $inline$C$inline$, $inline$X$inline$. В этой четвёрке должен быть студент, который знает всех троих. Это не может быть $inline$A$inline$ или $inline$X$inline$, так как они не знакомы, поэтому пусть $inline$B$inline$ знает всех троих (не важно, это может быть и $inline$C$inline$, пока симметрия между ними не нарушена).
Так как мы работаем от противного, то каждый студент в четвёрке $inline$ABCD$inline$ не знает кого-либо. Если в случае с $inline$A$inline$ мы были вынуждены взять незнакомца со стороны, то в случае с $inline$B$inline$ возможны два случая. Если $inline$B$inline$ не знает кого-то изнутри четвёрки $inline$ABCD$inline$, то это может быть только $inline$D$inline$, так как $inline$A$inline$ и $inline$C$inline$ он уже знает. Но в этом случае рассмотрим четвёрку $inline$AXBD$inline$. С учётом того, что $inline$A$inline$ не знает $inline$X$inline$ и $inline$D$inline$ не знает $inline$B$inline$, мы не можем удовлетворить условию о том, чтобы хотя бы один студент в четвёрке знал всех остальных троих.
Таким образом, $inline$B$inline$ и $inline$D$inline$ должны быть знакомы, а у $inline$B$inline$ должен быть незнакомый студент со стороны $inline$Z$inline$. Но тут и наступает конец. Рассмотрим четвёрку $inline$ABXZ$inline$. В ней невозможно устроить так, чтобы кто-то знал троих остальных студентов так как незнакомы $inline$A$inline$ и $inline$X$inline$, $inline$B$inline$ и $inline$Z$inline$, задача решена.
Задача 3
На окружности выбираются две случайные точки $inline$A$inline$, $inline$B$inline$, найди матожидание площади наименьшего из сегментов, на которые хорда $inline$AB$inline$ разбивает круг.
Решение
Как говорилось в одном анекдоте про прапорщика, «а что тут думать? трясти надо!». Зафиксируем точку $inline$A$inline$, а точку $inline$B$inline$ параметризуем углом $inline$\varphi$inline$ между радиус-векторами $inline$OA$inline$ и $inline$OB$inline$. Рассмотрим углы $inline$\varphi \in [0, \pi]$inline$. Площадь меньшего сегмента тогда будет равна $inline$S (\varphi) = \varphi R^2 / 2 — (½) R^2 \sin \varphi $inline$, тогда
$$display$$\bar{S (\varphi)} = \frac{1}{\pi}\int\limits_{0}^{\pi} d\varphi S (\varphi) = (R^2 / 2 \pi) \int\limits_{0}^{\pi} d\varphi (\varphi — \sin \varphi) = \frac{R^2}{2 \pi} \left (\frac{\pi^2}{2} — 2 \right) = \pi R^2 / 4 — R^2 / \pi.$$display$$
Задача 4
Дан массив из $inline$n$inline$ натуральных чисел. Предложите способ сортировки его по остатку от деления на 5 за линейное время и константную память.
Решение
В этом месте руки похолодели, я-ж не программист! Но спокойно, я же говорил, это экзамен по математике.
Сортировку нужно делать in-place, так как дополнительно можно затратить только константу памяти. Зафиксируем некий текущий остаток $inline$r$inline$ (сначала $inline$r = 0$inline$, в конце $inline$r = 4$inline$) и пойдём по массиву от начала до конца указателем $inline$j$inline$. Также заведём так называемый индекс вставки $inline$i$inline$, который изначально указывает на начало массива и затем только увеличивается.
Если элемент массива $inline$A[j]$inline$ имеет остаток $inline$r$inline$, мы должны поменять его местами с $inline$A[i]$inline$. После этого индекс $inline$i$inline$ мы увеличиваем до тех пор, пока $inline$A[i] = r (\mbox{mod}) 5$inline$ и останавливаем в тот момент, когда это равенство нарушается. Затем снова растим индекс $inline$j$inline$, пока снова не найдём $inline$A[j] = r (\mbox{mod} 5)$inline$, чтобы его перекинуть на позицию $inline$i$inline$.
В данном алгоритме есть некий инвариант, а именно, позади индекса $inline$i$inline$ все числа уже расставлены правильно (отсортированы по остатку). При одном проходе $inline$j$inline$ по всему массиву, позади $inline$i$inline$ будут лежать все элементы, которые при делении на $inline$5$inline$ дают в остатке $inline$0$inline$. При очередном проходе та же участь постигнет тех, кто делится с остатком $inline$1$inline$ и так далее. Всего потребуется 4 прохода (пятый будет уже не нужен).
Задача 5
Исследуйте на сходимость и абсолютную сходимость ряд
$$display$$\sum\limits_{n = 0}^{+\infty} \sin \pi \sqrt{n^2 + 1}. $$display$$
Решение
ШАД, ты серьёзно? Ну это-то зачем? Ладно…
Запишем
$$display$$ \sin \pi \sqrt{n^2 + 1} =\sin \pi n \sqrt{1 + 1/n^2} = \sin \left (\pi n + \frac{\pi}{2 n} + \mathcal{o}(n^{-2})\right) = (-1)^n \sin \left (\frac{\pi}{2 n} + \mathcal{o}(n^{-2})\right) = \\ = (-1)^n \left (\frac{\pi}{2 n} + \mathcal{o}(n^{-2}) \right).$$display$$
Видно, что ряд сходится условно. Слагаемое $inline$\mathcal{o (n^{-2})}$inline$ сходится по интегральному признаку, а слагаемое $inline$(-1)^n / n $inline$ сходится по признаку Дирихле. Если же рассмотреть абсолютную сходимость, надо вспомнить свойство $inline$|a + b| \geqslant |a| — |b|$inline$. Слагаемое $inline$b = \mathcal{o (n^{-2})}$inline$ всё ещё сходится по тому же интегральному признаку, а вот слагаемое $inline$ a \sim 1/n $inline$ расходится как сумма гармонического ряда, и потому весь ряд не сходится.
Задача 6
У вас имеется неограниченное количество костей в виде всех возможных правильных многогранников. Можно ли, однократно просив некоторый набор таких костей, симулировать бросок (а) правильной 7-гранной кости, (б) правильной 15-гранной кости?
Решение
Эту задачу на самом экзамене я не успел даже прочесть, так что это было вроде домашней работы. Всего правильных многогранников пять: пирамида (4), куб (6), октаэдр (8), додекаэдр (12), икосаэдр (20).
Заметим, что мы можем симулировать бросок $inline$5$inline$-гранной кости, беря остаток от деления на пять того, что выпало на икосаэдре. Аналогично, мы можем симулировать бросок трёхгранной кости, деля остаток от деления на $inline$3$inline$ от всего, что падает на пирамиде. Тогда, если $inline$d_3$inline$ и $inline$d_5$inline$ — результаты бросков таких костей, то результат броска $inline$15$inline$-гранной кости мы будем пересчитывать как $inline$d_{15} = 5 (d_3 — 1) + d_5.$inline$ Заметим, что здесь все исходы равновероятны, то есть это действительно правильная кость.
Тем не менее, бросок $inline$7$inline$-гранной кости симулировать нельзя. К данному моменту стало ясно, что если у нас честный кубик $inline$d_i$inline$, то мы можем симулировать любые делители $inline$i$inline$, а также, если у нас есть два честных кубика $inline$d_i$inline$ и $inline$d_j$inline$, мы можем симулировать произведение $inline$d_{ij}$inline$. Именно поэтому мы можем просимулировать любое число, раскладывающееся на простые множители $inline$2$inline$, $inline$3$inline$ и $inline$5$inline$ (других среди платоновых тел нет).
Предположим, что мы хотим просимулировать число, которое не раскладывается на произведение таких простых множителей. Кинем для этого $inline$N$inline$ костей $inline$d_{i_1},\; d_{i_2},\;\ldots,\; d_{i_N}$inline$, и числа, выпавшие на всех $inline$N$inline$ костях, запишем в один вектор, описывающий точку в гиперкубе размером $inline$i_1\times i_2 \times \ldots \times i_N$inline$. Если мы хотим симулировать $inline$7$inline$-гранную кость, мы должны точки в этом пространстве поделить на $inline$7$inline$ групп равного размера, что сделать нельзя, ведь иначе произведение $inline$i_1\times i_2 \times \ldots \times i_N$inline$ должно будет делиться на $inline$7$inline$, а такого мы ещё не получили.
Задача 7
Пусть $inline$A$inline$, $inline$B$inline$ — квадратные вещественные матрицы. Доказать, что $inline$ \mbox{det}\left (E — AB\right) = \mbox{det}\left (E — BA\right).$inline$
Решение
Здесь мне очень помогла формула, которую ужасно любят в теор. физике, и я сильно рекомендую её взять на вооружение тем, кто пойдёт на экзамен. Для любой матрицы $inline$A$inline$, у которой все собственные значения положительны, справедливо $inline$\mbox{det}A = \exp \mbox{tr} \log A.$inline$
Как же здесь применить нашу формулу? Я скажу сразу, мы будем раскладывать логарифм в ряд. Под логарифмом у нас будет стоять выражение вида $inline$E — AB$inline$, которое можно раскладывать в ряд, только если $inline$|AB|_2 < 1$inline$. Это совершенно полностью соответствует радиусу сходимости логарифма, но только во многомерном пространстве.
Для начале давайте переформулируем задание и докажем, что $inline$ \mbox{det}\left (E — \lambda AB\right) = \mbox{det}\left (E — \lambda BA\right) $inline$ для любого вещественного числа $inline$\lambda$inline$, и дальше просто возьмём $inline$\lambda = 1.$inline$ Зачем это нужно? Это нужно для того, чтоб сделать норму матриц $inline$|AB|_2$inline$ меньше $inline$1$inline$. Когда рассмотрено очень маленькое $inline$\lambda$inline$, можно смело написать такую цепочку (под следом матрицы можно передвигать по циклу):
$$display$$\mbox{det}\left (E — \lambda AB\right) = \exp \mbox{tr} \log (E — \lambda AB) = \exp \mbox{tr}\left (-\lambda AB — \frac{\lambda^2 (AB)^2}{2} — \frac{\lambda^3 (AB)^3}{3} — \ldots\right) = \\ = \exp \mbox{tr}\left (-\lambda BA — \frac{\lambda^2 (BA)^2}{2} — \frac{\lambda^3 (BA)^3}{3} — \ldots\right) = \mbox{det}(E — \lambda BA).$$display$$
Здесь мы нагло использовали свойство $inline$\mbox{tr}(AAAAA\ldots AAABBBBB\ldots BBB) = \mbox{tr}(BBBBB\ldots BBBAAAAA\ldots AAA).$inline$
Хорошо, мы доказали эту формулу для некоторого отрезка $inline$\lambda$inline$ вблизи ноля. Как же теперь распространить её на все $inline$\lambda$inline$, в частности $inline$\lambda = 1$inline$? Заметим, что в левой и правой части доказанной формулы стоят многочлены по $inline$\lambda$inline$ (ведь в определитель входят только произведения)! То есть, мы доказали, что два многогочлена совпадают на отрезке, но отсюда сразу следует, что они совпадают всюду на числовой прямой.
Задача 8
За столом сидят $inline$n$inline$ старателей, перед каждым из которых лежит кучка золотого песка. Каждую минуту все старатели берут половину песка из левой кучки и половину из правой кучки и кладут себе. Опишите асимптотическое поведение количества песка в кучках для произвольного $inline$n$inline$.
Решение
По сути, нам предлагается найти асимптотику решения вот такой разностной схемы (для любых начальных условий):
$$display$$a (x, t + 1) = \frac{a (x — 1, t) + a (x + 1, t)}{2},$$display$$
где $inline$a (x, t)$inline$ — количество золота у старателя, сидящего в позиции $inline$x$inline$ во время $inline$t$inline$. Координата $inline$x$inline$ замкнута в окружность, $inline$x = 0, 1, \ldots, n — 1$inline$.Такие вещи решаются множеством способов, но самый естественный — дискретное преобразование Фурье. Мы имеем дело с функцией, периодической по $inline$x$inline$, и её можно и нужно разложить в конечную сумму Фурье по $inline$x$inline$:
$$display$$a (x, t) = \frac{1}{N} \sum\limits_{k = 0}^{n — 1} \sum\limits_{\omega = 0}^{T — 1} \tilde{a}(k, t) e^{2 \pi i k x / n} .$$display$$
Это хозяйство должно удовлетворять нашему разностному уравнению, поэтому подставим эту сумму в уравнение явно и потребуем, чтоб коэффициенты при всех экспонентах слева и справа совпадали. По сути, мы просто сделали замену базиса (перешли к плоским волнам) и требуем, чтобы и в новом базисе у нас коэффициенты перед базисными векторами совпадали. Это приводит к уравнению
$$display$$ \tilde{a}(k, t + 1) = \frac{e^{2 \pi i k / n}\tilde{a}(k, t) + e^{-2 \pi i k / n}\tilde{a}(k, t)}{2} = \cos (2 \pi k /n)\tilde{a}(k, t).$$display$$
Для фиксированного $inline$k$inline$ это само по себе уравнение, которое аналогично решается ещё одним преобразованием Фурье. Будем обозначать преобразование Фурье по координате тильдой, а по координате + времени — крышечкой. Записав
$$display$$\tilde{a}(k, t) = \frac{1}{T}\sum\limits_{\omega = 0}^{T — 1} \hat{a}(k, \omega)e^{2 \pi i \omega t / T},$$display$$
подставив это в последнее уравнение и снова уравняв экспоненты, мы получаем$$display$$e^{2 \pi i \omega} = \cos (2 \pi i k).$$display$$
Мы получили так называемое дисперсионное соотношение. То есть, плоские волны здесь могут быть не с произвольными $inline$k,\;\omega$inline$, а только с теми, которые подчиняются этой формуле. Это дисперсионное соотношение — переформулировка исходного уравнения в новом базисе. Пусть мы зафиксировали какой-то импульс $inline$k$inline$ и пытаемся найти соответствующую частоту $inline$\omega$inline$, которая может существовать в такой системе.
Если косинус справа по модулю будет меньше единицы, то в комплексную экспоненту придётся подставлять комплексную частоту $inline$\omega = \omega' + i \omega''$inline$ (у которой будет мнимая часть). Как легко видеть, мнимая часть этой экспоненты тогда будет положительной ($inline$\omega'' > 0$inline$), тогда в экспоненту она войдёт как $inline$-2 \pi \omega'' / T$inline$ и уменьшит её модуль вслед за косинусом. Но, к счастью, такие частоты быстро отправятся на покой. Действительно, если мы посмотрим, какой вклад будут давать моды с такими частотами, мы увидим, что они будут по времени экспоненциально затухать. Такие моды в асимптотику давать вклада не будут.
Поэтому у нас остаётся два случая. Если $inline$n$inline$ — нечётное, то косинус бывает равным $inline$1$inline$ по модулю лишь однажды, когда $inline$k = 0$inline$. В этом случае $inline$\omega = 0$inline$. Эта плоская волна — всего лишь среднее. Получается, при нечётных $inline$n$inline$ никакой антересной динамики в бесконечности нет: богатство старателей сходится к среднему от того, что было изначально:
$$display$$ a (x, t) \to \frac{1}{N} \sum\limits_{b = 0}^{n — 1} a (b, 0).$$display$$
Если же $inline$n$inline$ нечётное, то косинус ещё может быть равен $inline$-1$inline$, если $inline$k = n / 2$inline$, а тогда возможно дополнительное решение $inline$\omega = T / 2,\; \tilde{a}(k, t) = \hat{a}(k, T / 2) (-1)^t/ T$inline$ (в сумме выживает только слагаемое, в котором вещественная $inline$ \omega $inline$, его мы и записали). В этом случае
$$display$$a (x, t) = \frac{1}{N} a (n / 2, t) = \frac{1}{NT} (-1)^x (-1)^t \hat{a}(n / 2, T / 2).$$display$$
Аналогично остаётся всего одно слагаемое, его и пишем. Теперь про решение нам почти всё известно. Это некая вот такая конструкция, которая меняет знак как при шаге по времени, так и при шаге по пространству. Заметьте, что если бы здесь $inline$n$inline$ не было чётным, это бы нарушило цикличность по окружности. Осталось только найти значение коэффициента.Взглянем на обратное преобразование Фурье:
$$display$$\hat{a}(n / 2, T / 2) (-1)^t / T= \tilde{a}(n / 2, t) = \sum\limits_{x = 0}^{n — 1} a (x, t) e^{-2 \pi i (n / 2) x / n}.$$display$$
При $inline$t = 0$inline$ слева стоит $inline$\hat{a}(k, \omega) / T$inline$, а справа стоит просто $inline$\sum\limits_{x = 0}^{n — 1} a (x, 0) (-1)^x$inline$, то есть альтернированная сумма богатств в исходный момент времени. Таким образом, мы получаем
$$display$$ a (x, t) \to \frac{(-1)^x (-1)^t}{N}\sum\limits_{b = 0}^{n — 1} a (b, 0) (-1)^b + \frac{1}{N} \sum\limits_{b = 0}^{n — 1} a (b, 0).$$display$$
Послесловие
За контрольную дали семь очков из восьми. Я не написал про трюк с $inline$\lambda$inline$ в задаче про матрицы, а просто раскладывал — этого не заметили. Затем было собеседование. Меня ничего не спросили про экзамен, просто поговорили за жизнь, зачем я хочу поступать в ШАД (подготовьте ответ на этот вопрос!). Ребят, у кого было поменьше задач, просили решать что-то на месте, так тчо лучше придти в боевом расположени духа. Также будет возможность отапеллировать недоставленных за контрольную очков.
Обучение в ШАД мне сильно-сильно понравилось. Здесь всё время толкают какую-то теорию, читают по самым свежим статьям, а не по 50-летним книгам, и, самое главное, теория всегда подкреплена очень подходящей и логичной практикой.
Плюсы:
- Очень крутые курсы, разбегаются глаза: есть на любой вкус, от очень практических до очень теоретических, почти все современные отрасли компьютерных наук по свежим статьям.
- Преподаватели в основной массе огонь, не лень было после лабы вечером ехать на другой конец Москвы послушать.
- Классная подача материала, всё записывается на видео, можно не ходить. Сдавать можно удалённо, но ходить всё равно хочется.
- Здоровские однокурсники!
Как таковых, минусов я даже и не заметил. Кураторы ко всем относятся по-доброму, не торопятся отчислять. В Яндексе (помещениях Мамонтова) очень приятная атмосфера, кондиционеры, вкусняшки, удобные кресла, человеческая обстановка! И, главное, довольно большая свобода в выборе курсов и своего профиля даже в рамках выбранной специальности.
Поступайте в ШАД! И, да, забыл, разберитесь обязательно с формулой полного разложения определителя
$$display$$ \mbox{det} A = \epsilon^{i_1 i_2 i_3\ldots i_N} a_{1 i_1} a_{2 i_2} \ldots a_{N i_N}.$$display$$
Комментарии (1)
20 апреля 2017 в 18:03
0↑
↓
«папа, а ты с кем это сейчас говорил?» (из старого анекдота)