Полный разбор первой части экзамена в ШАД 202014.05.2020 20:38

Привет! С вами Азат Калмыков, куратор в «ШАД Helper». Мы продолжаем наш цикл статей, в которых разбираем задачи для поступления в ШАД. На этот раз мы (я, Николай Проскурин и Александр Курилкин) посмотрим на решения первого этапа отбора в ШАД в этом году, который закончился совсем недавно. Итак, приступим.

A. Локальный минимум


При каких значениях параметра a первообразная функции $f(x)=\left(x^{4}-(a+1) x^{3}+(a-2) x^{2}+2 a x\right) \exp ^{\frac{\sin x^{2}+2}{5 x^{2}+2}}$ имеет не более одного локального минимума?

Решение
Заметим, что производная от первообразной — это исходная функция. Значит, нам нужно исследовать на смену знака нашу исходную функцию. Конкретно, надо понять, сколько раз функция меняет знак с минуса на плюс (то есть посчитать количество точек локального минимума).

Заметим, что экспонента всегда положительна, не влияет на знак, поэтому её можно откинуть и считать, что $f(x) = x^4 - (a + 1)x^3 + (a - 2)x^2 + 2ax$. Многочлен легко раскладывается на множители, потому что все его корни можно угадать: это $-1, 0, 2, a$. Значит, $f(x) = (x + 1)x(x - 2)(x - a)$.

Если многочлен имеет четыре различных корня, то он меняет знак в порядке $+ \to - \to + \to - \to +$, и потому имеет хотя бы два локальных минимума. Значит, нам могут подойти только $a = -1, 0, 2$. Прямая проверка показывает, что все они являются ответами.


B. Предел


Определите, при каком значении $a$ данный предел равен $\frac{1}{e}$:

$ \lim _{x \rightarrow +\inf }\left(\cos \sqrt{\frac{1}{x}}\right)^{\frac{x}{a}} $


Решение
Сначала посчитаем предел, приняв $a = 1$. Поскольку $\sqrt{\frac{1}{x}} \to 0$, мы можем разложить функцию в ряд Тейлора в нуле:

$\cos{\sqrt{\frac{1}{x}}} = 1 - \frac{1}{2!x} + \frac{1}{4!x^2} - \frac{1}{6!x^3} + \ldots$

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

$1 - \frac{1}{2x} < \cos{\sqrt{\frac{1}{x}}} < 1 - \frac{1}{2x} + \frac{1}{24x^2}$

Поскольку $x \to +\infty$, от возведения в степень $x$ неравенство сохранится, а при переходе к пределу изменится только строгость знаков. Левую часть можно посчитать сразу как следствие из второго замечательного предела, она равна $e^{-1/2}$. Покажем, что правая равна тому же:

$\lim_{x \to +\infty} \left( 1 - \frac{1}{2x} + \frac{1}{24x^2} \right)^x = \exp\left(\lim_{x \to +\infty} x \ln\left( 1 - \frac{1}{2x} + \frac{1}{24x^2} \right)\right) =$

$= \exp\left(\lim_{x \to +0} \frac{\ln\left( 1 - \frac{x}{2} + \frac{x^2}{24} \right)}{x}\right)$

Применяя правило Лопиталя, получаем требуемое. Значит:

$\lim_{x \to +\infty} \left(\cos{\sqrt{\frac{1}{x}}}\right)^x = e^{-1/2} \Rightarrow \lim_{x \to +\infty} \left(\cos{\sqrt{\frac{1}{x}}}\right)^{x/a} = e^{-1/2a}$

Откуда $a = \frac{1}{2}$.

Примечание: зная, что степенной ряд можно бесконечно дифференцировать в области сходимости, можно было пропустить шаг с оценкой ряда и сразу применить Лопиталя.


C. Локальный минимум


При какой минимальной длине шага градиентный спуск не сможет найти минимум функции $x^4+\cos 2 $, если $x_0=1$?

Решение
Вспомним, что шаг градиентного спуска при константной длине шага считатеся следующим образом:

$ x_k+1 = x_k - \lambda \triangledown f(x_k)$

.

В нашем случае градиент — это обычная одномерная производная, так что наша задача проще градиентного спуска в общем случае.

$ \triangledown f(x_k) = 4x_k^3 $

$x_0$ нам известно, давайте посчитаем $x_1$:

$x_1 = x_0 - \lambda 4x_0^3 = 1 - 4\lambda$

Давайте заметим что, при $x_1=-1$ значение градиента будет таким же по модулю, как в точке $x_0$, но иметь обратный знак. Таким образом, можно понять, что при таком варианте градиентный спуск будет «скакать» туда-сюда из точки $1$ в $-1$ и обратно. Таким образом, можно понять, что при $x_1=-1 \Leftrightarrow \lambda=0.5 $ градиентный спуск уже не найдёт точку минимума (это точка $0$). Но надо показать, что при меньших $ \lambda $ она будет найдена.

Это можно понять и интуитивно, но давайте попробуем доказать строго. Можно доказать что $ |x_{n+1}| \leq |x_n||1-4\lambda| $ по индукции. Здесь нам важно, что $ 0.5 > \lambda > 0 \Rightarrow |1 — 4\lambda| < 1$

База: $ |x_1| = |1 - 4\lambda| \leq 1 |1 - 4\lambda| = x_0 |1-4\lambda| $

Переход. $ |x_{n+1}| = |x_n - 4\lambda x_n^3| = |x_n| |1-4\lambda x_n^2|$. За счёт предположения индукции можем получить что $x_n < 1 \Rightarrow x_n^2 < 1$. Тогда $|x_{n+1}| \leq |x_n||1-4\lambda|$. Всё доказано.

Пользуясь доказанным, можно получить, что $|x_n|\leq |x_0||1-4\lambda|^n = |1-4\lambda|^n $. Так как знаем, что $|1-4\lambda| < 1$, то получим что $|x_n|$ сходится к нулю. Значит градиент находит минимум.


D. Собственный вектор


Определите, при каких значениях параметра a вектор $ \left(\begin{array}{l} 1 \\ 1 \\ a \end{array}\right) $ является собственным вектором матрицы

$ \left(\begin{array}{ccc} a & 1 & -1 \\ 1 & 2 & -1 \\ 0 & 0 & 1 \end{array}\right) $

Решение


E. Определитель


При каких значениях параметра $a$ максимален определитель матрицы, обратной к этой?

$ \left(\begin{array}{ccc} a & -7 & -3 \\ 6 & -10 & -a^{2} \\ 0 & a & 9 \end{array}\right) $

Решение


F. Проекции


Даны точки $ B(1,2,−3) $ и $C(2,2,1)$, а также плоскости $\alpha$: $2x−2y+z=0$ и $β$: $−x+2y+3z=0$. Найдите координаты точки $A$, если известно, что её ортогональная проекция на $\alpha$ совпадает с проекцией точки $B$, а на $\beta$ — с проекцией точки $С$.

Решение
Если $A = (x, y, z)$ имеет ту же проекцию на плоскость, что и $B$, то она лежит на прямой, перпендикулярной плоскости и содержащей $B$. Эту прямую можно задать параметрически, поскольку мы знаем точку и направляющий вектор, который совпадает с вектором нормали к $\alpha$ и потому равен $\overline{n}_1(2, -2, 1)$. Система для прямой:

$\begin{cases} x = 2t_1 + 1\\ y = -2t_1 + 2\\ z = t_1 - 3\\ \end{cases}$

Аналогично, $A$ лежит на прямой, проходящей через $C$ и перпендикулярной $\beta$. Вектор нормали: $\overline{n}_2(-1, 2, 3)$, система:

$\begin{cases} x = -t_2 + 2\\ y = -2t_2 + 2\\ z = 3t_2 + 1\\ \end{cases}$

Пересечение прямых и будет являться искомой точкой. Для её нахождения нужно определить $t_1$ и $t_2$, для этого достаточно приравнять первые два уравнения систем:

$\begin{cases} 2t_1 + 1 = -t_2 + 2\\ -2t_1 + 2 = 2t_2 + 2\\ \end{cases} \Leftrightarrow \begin{cases} 3 = t_2 + 4\\ -2t_1 + 2 = 2t_2 + 2\\ \end{cases} \Leftrightarrow \begin{cases} t_2 = -1\\ t_1 = 1\\ \end{cases}$

Подставив параметры в обе системы, убеждаемся, что получили одну и ту же точку $A(3, 0, -2)$, которая и является искомой.


G. Домино


В далёком созвездии Тау-Кита на каждой половинке костяшки домино стоит от $0$ до $N$ точек, причём для каждой пары чисел $(a,b)$ таких, что $a$ и $b$ целые от $0$ до $N$, существует ровно одна доминошка, содержащая оба этих числа. Космический турист прилетел и выбрал наугад перевёрнутую костяшку. При каком $N$ математическое ожидание модуля разности количеств точек на одной и на другой половине этой доминошки будет равно $2$?

Решение
Обозначим случайную величину за $\xi$, вероятностное пространство за $\Omega$ и образ случайной величины за $\xi(\Omega)$. Будем считать матожидание по формуле:

$E(\xi) = \sum_{k \in \xi(\Omega)} k \Pr[\xi = k] = 2$

Пусть $A_k$ — событие, что величина примет значение $K$, тогда $\Pr[\xi = k] = \frac{|A_k|}{|\Omega|}$. Домножив на $|\Omega|$, получаем:

$\sum_{k \in \xi(\Omega)} k |A_k|= 2 |\Omega| $

Посчитаем $|\Omega|$. Во-первых, в него входят доминошки с одинаковыми числами на половинках. Во-вторых, в него входят все возможные пары различных чисел, причем каждая по одному разу. Значит,

$|\Omega| = n + 1 + \frac{n(n + 1)}{2}$

.

Теперь посчитаем сумму. Понятно, что величина принимает значения от 0 до $n$. Сколько раз она принимает значение $k$? Ровно $n - k + 1$: благоприятные исходы — это доминошки $(0, k), (1, k + 1), \ldots, (n - k, n)$. Значит:

$\sum_{k \in \xi(\Omega)} k |A_k| = \sum_{k = 0}^n k(n - k + 1) = (n + 1)\sum_{k = 0}^n k - \sum_{k = 0}^n k^2 = \frac{n(n + 1)^2}{2} - $

$ - \frac{n(n + 1)(2n + 1)}{6} = \frac{n(n + 1)(n + 2)}{6} $

Получаем уравнение:

$\frac{n(n + 1)(n + 2)}{6} = (n + 1)(n + 2)$

Поскольку $n > 0$» />, получаем, что <img src=.


H. Экзамен


Два друга решили вместе пойти на экзамены в ШАД и договорились встретиться у входа с 14:00 до 15:00, но не договорились во сколько именно. Момент времени прихода каждого из них распределён равномерно на этом отрезке времени, но друзья нетерпеливые, поэтому через 15 минут ожидания они отчаиваются дождаться и заходят одни. Известно, что они встретились.

Найдите вероятность того, что оба пришли до 14:45.

Решение
Для того, чтобы решить эту задачу, нам нужно немного порисовать. А именно, давайте нарисуем квадрат 60×60. Ось x будет обозночать время прихода первого, y — второго.
938rvyxztw-fxsh4ptvw3urltzm.png
Событие «друзья встретились» изображено на рисунке красной областью. Событие «каждый пришёл до 14:45» обозначено пересечением 2 зелёных областей. Пользуясь тем, что время прихода каждого из друзей распределено равномерно, можем понять, что вероятность того, что «каждый пришёл до 14:45» при условии, что «друзья встретились» это отношение площади пересечения всех 3 областей к площади красной области. Применяя теорему пифагора и простой счёт, можем получить ответ $\frac{5}{7}$.


I. Случайная величина


Плотность распределения случайной величиы $\xi$ равна $p(x)=\frac{1}{\sin x}$ при $x$ от $\pi/2$ до $2 \arctan e$ и нулю при всех остальных $x$.

Найдите значение, которое эта случайная величина не превосходит с вероятностью $\frac{1}{2}$.

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

$\Pr(\xi \leq x) = \int\limits_{\pi/2}^x \frac{dt}{\sin{t}} = \int\limits_{1}^{\tan{x/2}} \frac{du}{u} = \ln{\tan{\frac{x}{2}}}$

Получили уравнение:

$\ln{\tan{\frac{x}{2}}} = \frac{1}{2} \Leftrightarrow \tan{\frac{x}{2}} = e^{1/2} \Leftrightarrow x = 2 \tan^{-1}{e^{1/2}}$



J. Найти среднее


Условие


Решение
Для простоты сначала рассмотрим вариацию со средним арифметическим. Чтобы вычислять его для отрезка за $О(1)$, необходимо находить сумму на отрезке за $O(1)$.

Это делается с помощью следующего трюка. Насчитаем массив sums, где $sums[i] = a[0] + a[1] + \dots + a[i]$. Так как $sums[i] = sums[i - 1] + a[i]$, то это можно сделать за $O(n)$. Теперь сумма на отрезке с $l$ по $r$ — это просто $sums[r] - sums[l - 1]$. Чтобы вычислить среднее арифметическое на отрезке, нужно еще поделить эту сумму на $r - l + 1$. Итого $O(1)$ на запрос и $O(n)$ на предподсчёт.

В вариации со средним геометрическим чуть посложнее. Так как теперь вместо суммы у нас умножение, числа могут расти довольно быстро, и произведение чисел на префиксе может быть настолько большим или маленьким, что не будет влезать в стандартные типы данных. Чтобы решить эту проблему, будем считать натуральный логарифм среднего геометрического, а потом просто возведем $e$ в эту степень. Школьная математика гласит, что $\ln ((a[l] \cdot ... \cdot a[r])^{\frac{1}{r - l + 1}}) = \frac{\ln a[l] \cdot \dots \cdot a[r]}{r - l + 1} = \frac{\ln a[l] + \dots + \ln a[r]}{r - l + 1}$, а сумму логарифмов можно посчитать за $О(1)$ с помощью описанного выше трюка.

Код: gist.github.com/Azatik1000/0b0d8496785169a8ac0d35a8c9e8e59f


K. Удалить последнего


Условие


Решение
Заведем unordered_set (C++) / HashSet (Java) / set (Python), куда будем класть уже встреченные числа. Пройдемся по массиву справа налево, для очередного числа проверим, есть ли оно в множестве встреченных чисел. Если нет, то добавим его в это множество. Если же есть, то добавим в конец вектора-ответа. В конце сделаем reverse вектора ответа за $O(n)$. Проверка на нахождение числа в хеш-таблице работает за $О(1)$, поэтому общая асимптотика по времени $O(n)$.

Код: gist.github.com/Azatik1000/2fef745e23c23eb020f21878980cae08


L. Доска объявлений


Условие

Костя решил развесить объявления о том, как наиболее правильно мыть руки.

Он нашел доску объявлений размером $W × H$, а его объявление имеет ширину a и пока неизвестную высоту не менее b. Костя хочет разместить объявление, чтобы оно не накрывало никакое уже размещенное на доске объявление. У нового объявления может быть общая граница с наклеенными или доской объявлений, но площадь пересечения с другими объявлениями должна быть нулевой.

Вам даны координаты наклеенных объявлений. Определите координаты области, где Костя может приклеить свое объявление так, чтобы высота объявления была как можно больше. Если таких областей несколько, то подойдет любая из них.

Про координаты. Левый нижний угол доски объявлений имеет координаты $(0, 0)$, а правый верхний — $(W, H)$. Для каждого уже наклеенного объявления нам известны координаты левого нижнего угла и правого верхнего углов.

Гарантируется, что подходящая область на доске объявлений всегда существует.

Формат ввода


В первой строке заданы размеры доски объявлений $W$, $H$ и размер объявления Кости $a$, $b$ ($1 \leq W$, $H \leq 100 000$, $1 \leq a \leq W$, $1 \leq b \leq H$).

Во второй строке записано число $n$ ($0 \leq n \leq 100$) — количество уже приклеенных объявлений.

Далее в $n$ строках записаны координаты объявлений $(x_{ld}, y_{ld})$ и $(x_{ru}, y_{ru})$ ($0 \leq x_{ld} < x_{ru} \leq W, 0 \leq y_{ld} < y_{ru} \leq H$). Объявления могут перекрываться, т.е. иметь ненулевую площадь пересечения.

Формат вывода


Выведите координаты левого нижнего $(x_{ld}, y_{ld})$ и правого верхнего $(x_{ru}, y_{ru})$ углов области, куда Костя может приклеить объявление. Область должна иметь ширину $a$ и наибольшую подходящую высоту (гарантируется, что не менее $b$). Никакая часть найденной области не должна быть занята наклеенными объявлениями.

Все числа должны быть целыми и неотрицательными.

Если подходящих областей несколько, выведите любую из них.

Пример 1


Пример 2


Пример 3



Решение
Найдем область максимальной высоты, в которую можно наклеить наше объявление. Заметим, что произведение $W * n$ не очень большое.

Переберем ширину $x$ (от $0$ до $W - a$), на которой будет находиться левая граница нашего объявления. Рассмотрим только те объявления, у которых ненулевая часть их площади находится на высоте от $x$ до $x + a$, остальные никак не мешают нам наклеить наше объявление. Для тех, которые попали в «полосу» от $x$ до $x + a$, выпишем пары $y$-координаты их нижней и верхней границ. Эти пары образуют отрезки, ни с одним из которых не должен пересекаться отрезок $(y_1, y_2)$, где $y_1$ и $y_2$ — это $y$-координаты нижней и верхней границы соответственно той области, куда мы наклеим наше объявление. Осталось максимизировать $y_2$ — $y_1$.

Для этого объединим все выписанные отрезки, добавив к ним для удобства $(0, 0)$ и $(h, h)$, соответствующие границам доски. Чтобы это сделать, отсортируем все отрезки по нижей, а при равенстве по верхней границе, и пройдемся по ним в отсортированном порядке. Если нижняя граница очередного отрезка ниже верхней границы последнего отрезка, то расширим последний до верхней границы очередного отрезка, иначе добавим в объединение очередной отрезок. После того, как мы получили объединение отрезков, ответом является максимальная разность между концами двух соседних в отсортированном порядке отрезков в объединении.

При максимизации ответа запоминаем подходящие границы и таким образом нходим ответ. Итого $O(W * n * \log n)$ по времени и $O(n)$ по памяти.

Код: gist.github.com/Azatik1000/2c07ebdd866ce20a4b5f5e6ee7408ad7

© Habrahabr.ru