Рассмотрим раскладку ЙЦУКЕН. Каждую букву, расположенную на раскладке клавиатуры, будем обозначать парой чисел $(n, m)$, где $n$ — ряд клавиш, $m$ — номер клавиши в ряду, считая слева направо. Например, «ш» обозначим за (1, 8), «ы» — за (2, 2), «ю» — за (3, 9).
Определение 1. Межбуквенным расстоянием Павленко $r\,(a, b)$ между клавишами $a = (i,\,j)$ и $b = (k, l)$ называется целое неотрицательное число $|k - i| + |l - j|$.
Определение 2. Межсловным расстоянием Павленко между словами $s$ и $t$ одинаковой длины $k$ называется величина $\sum_{i=1}^k r\,(s_i, t_i)$.
Дан граф, заданный количеством рёбер. Требуется понять, не сломал ли кто бедному графу ребро.
"YES"
или "NO"
в зависимости от ответа на задачу.
Задачи по теории чисел
Результаты
Список тем для рефератов
1.1. Нахождение локального минимума. Метода псевдоградиентного спуска.
Под функцией я буду понимать отображение из некоторого множества $M$ решений в множество действительных чисел $\mathbb R$. Под решениями я подразумеваю кандидатов на решение -- все элементы множества, в котором содержится решение нашей задачи.
Рассмотрим какую-нибудь функцию, значения которой мы умеем вычислять. Например, $F(x,y)=\sin \left(\frac 12x^2-\frac 14y^2+3\right)\cos(2x+1-e^y)$. Вычислять значения этой функции мы можем с лёгкостью, но вот поискать её точки минимума с помощью учебника математики и ручки с бумагой -- задача уже неразрешимая для обычного школьника. А задача перед нами стоит следующая: найти какой-нибудь из локальных минимумов этой функции с некоторой точностью $\vareps$.
Тогда мы можем действовать по следующему алгоритму:
1. Выбираем начальное решение, радиус окрестности, в которой будет производится поиск нового решения, минимальный радиус, количество итераций, которое алгоритм будет работать без уменьшения радиуса окрестности и улучшения решения и коэффициент, отвечающий за уменьшение радиуса (в нашем случае можно выбрать $x=0,y=0,r=1,r_{min}=10^{-3},baditers=10,\alpha=0.9$).
2. Выбираем новое решение. В нашем случае генерируем случайное направление $\varphi\in[0;2\pi)$ и проходим расстояние $r$ в направлении: $x'=x+r\cos\varphi,y'=y+r\sin\varphi$.
3. Если $F(x',y')\lt F(x,y)$, то «переходим на новое решение» ($x=x',y=y'$) и возвращаемся к шагу 2.
4. Если проработали уже $baditers$ итераций, а решение не улучшилось, то уменьшаем радиус поиска нового решения: $r=\alpha r$.
5. Если $r\lt r_{min}$, то завершаем работу и возвращаем $(x,y)$ в качестве результата.
Этот алгоритм уже будет приемлимо решать большое количество задач. Например, если мы хотим найти какой-нибудь корень уравнения $f(x)=x^3-4x+17\sin x-e^{\frac x2}$, то поиск минимума следует производить по функции $F(x)=|f(x)|$, а на шаге 2 алгоритма выбирать новое решение как $x'=x\pm r$. Разумеется, эту задачу можно решить и без всякого метода псевдоградиентного спуска: сначала можно построить график (или другим шаманством найти отрезок, на котором есть ровно один корень), а затем уточнить этот корень бинарным поиском.
Подытожим: в первом примере множеством решений было множество $\mathbb R^2$ (множество всех пар действительных чисел), во втором -- множество $\mathbb R$. В обоих случаях наши функции были «хорошими» -- они были непрерывными, гладкими и покладистыми. В дальнейшем нам придётся иметь дело с функциями более шероховатым, но такими, которые, как интуитивно кажется, обладают следующим свойством: у каждого решения $m$ из множества $M$ есть окрестность, в пределах которой значения функции меняются несильно. На других функциях ни метод псевдоградиентного спуска, ни метод отжига без дополнительных шаманств работать не смогут.
Настоящий метод градиентного спуска выбирает новое решение в направлении, которое задаётся антиградиентом функции. Что такое антиградиент, я не знаю, но судя по всему, это какая-то математическая прелесть, которая позволяет по решению быстро понимать, в какой стороне от него лежит локальный минимум.
Вам даны пары чисел $(a_i, b_i)$, Вам необходимо построить декартово дерево, такое что $i$-ая вершина имеет ключи $(a_i, b_i)$, вершины с ключом $a_i$ образуют бинарное дерево поиска, а вершины с ключом $b_i$ образуют кучу.
В первой строке записано число $N$ — количество пар. Далее следует $N$ ($1 \le N \le 50\,000$) пар $(a_i, b_i)$. Для всех пар $\lvert a_i\rvert, \lvert b_i \rvert \le 30\,000$. $a_i \ne a_j$ и $b_i \neq b_j$ для всех $i \ne j$.
Если декартово дерево с таким набором ключей построить возможно, выведите в первой строке YES, в противном случае выведите NO. В случае ответа YES, выведите $N$ строк, каждая из которых должна описывать вершину. Описание вершины состоит из трёх чисел: номер предка, номер левого сына и номер правого сына. Если у вершины отсутствует предок или какой-либо из сыновей, то выводите на его месте число 0.
Если подходящих деревьев несколько, выведите любое.
Входные данные | Выходные данные |
7 5 4 2 2 3 9 0 5 1 3 6 6 4 11 | YES 2 3 6 0 5 1 1 0 7 5 0 0 2 4 0 1 0 0 3 0 0 |