Введение
В мае далёкого 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 - (1/2) R^2 sin varphi $inline$, тогда
$$display$$bar{S(varphi)} = frac{1}{pi}intlimits_{0}^{pi} dvarphi S(varphi) = (R^2 / 2 pi) intlimits_{0}^{pi} dvarphi (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$$sumlimits_{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_1times i_2 times ldots times i_N$inline$. Если мы хотим симулировать $inline$7$inline$-гранную кость, мы должны точки в этом пространстве поделить на $inline$7$inline$ групп равного размера, что сделать нельзя, ведь иначе произведение $inline$i_1times i_2 times ldots times i_N$inline$ должно будет делиться на $inline$7$inline$, а такого мы ещё не получили.
Задача 7
Пусть $inline$A$inline$, $inline$B$inline$ — квадратные вещественные матрицы. Доказать, что $inline$ mbox{det}left(E - ABright) = mbox{det}left(E - BAright).$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 ABright) = mbox{det}left(E - lambda BAright) $inline$ для любого вещественного числа $inline$lambda$inline$, и дальше просто возьмём $inline$lambda = 1.$inline$ Зачем это нужно? Это нужно для того, чтоб сделать норму матриц $inline$|AB|_2$inline$ меньше $inline$1$inline$. Когда рассмотрено очень маленькое $inline$lambda$inline$, можно смело написать такую цепочку (под следом матрицы можно передвигать по циклу):
$$display$$mbox{det}left(E - lambda ABright) = 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} - ldotsright) = \ = exp mbox{tr}left(-lambda BA - frac{lambda^2 (BA)^2}{2} - frac{lambda^3 (BA)^3}{3} - ldotsright) = mbox{det}(E - lambda BA).$$display$$
Здесь мы нагло использовали свойство $inline$mbox{tr}(AAAAAldots AAABBBBBldots BBB) = mbox{tr}(BBBBBldots BBBAAAAAldots 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} sumlimits_{k = 0}^{n - 1} sumlimits_{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}sumlimits_{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} sumlimits_{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) = sumlimits_{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$sumlimits_{x = 0}^{n - 1} a(x, 0) (-1)^x$inline$, то есть альтернированная сумма богатств в исходный момент времени. Таким образом, мы получаем
$$display$$ a(x, t) to frac{(-1)^x (-1)^t}{N}sumlimits_{b = 0}^{n - 1} a(b, 0) (-1)^b + frac{1}{N} sumlimits_{b = 0}^{n - 1} a(b, 0).$$display$$
Послесловие
За контрольную дали семь очков из восьми. Я не написал про трюк с $inline$lambda$inline$ в задаче про матрицы, а просто раскладывал — этого не заметили. Затем было собеседование. Меня ничего не спросили про экзамен, просто поговорили за жизнь, зачем я хочу поступать в ШАД (подготовьте ответ на этот вопрос!). Ребят, у кого было поменьше задач, просили решать что-то на месте, так тчо лучше придти в боевом расположени духа. Также будет возможность отапеллировать недоставленных за контрольную очков.
Обучение в ШАД мне сильно-сильно понравилось. Здесь всё время толкают какую-то теорию, читают по самым свежим статьям, а не по 50-летним книгам, и, самое главное, теория всегда подкреплена очень подходящей и логичной практикой.
Плюсы:
- Очень крутые курсы, разбегаются глаза: есть на любой вкус, от очень практических до очень теоретических, почти все современные отрасли компьютерных наук по свежим статьям.
- Преподаватели в основной массе огонь, не лень было после лабы вечером ехать на другой конец Москвы послушать.
- Классная подача материала, всё записывается на видео, можно не ходить. Сдавать можно удалённо, но ходить всё равно хочется.
- Здоровские однокурсники!
Как таковых, минусов я даже и не заметил. Кураторы ко всем относятся по-доброму, не торопятся отчислять. В Яндексе (помещениях Мамонтова) очень приятная атмосфера, кондиционеры, вкусняшки, удобные кресла, человеческая обстановка! И, главное, довольно большая свобода в выборе курсов и своего профиля даже в рамках выбранной специальности.
Поступайте в ШАД! И, да, забыл, разберитесь обязательно с формулой полного разложения определителя
$$display$$ mbox{det} A = epsilon^{i_1 i_2 i_3ldots i_N} a_{1 i_1} a_{2 i_2} ldots a_{N i_N}.$$display$$
Автор: nikitaastronaut
