Задача "Древние династии"
Идея задачи --- Глеб Евстропов
Подготовка тестов --- Глеб Евстропов, Михаил Пядёркин
Разбор задачи --- Михаил Пядёркин

1. Формальная постановка задачи.
На прямой отмечено $n$ различных точек. Необходимо покрасить их в два цвета (белый и черный) так, 
чтобы для каждой точки ближайшая точка того же цвета находилась на расстоянии в пределах от $l_i$ до $r_i$.
При этом, требуется минимизировать количество пар соседних точек одного цвета.

[Картинка 1, файл dynpic1.png]

2. Решение простой подзадачи, перебор (20 баллов)
Воспользуемся методом полного перебора. Рассмотрим все допустимые раскраски точек (всего $2^n$ вариантов),
каждую проверим, является ли она допустимой (т.е. удовлетворяет условию задачи), а после этого среди
допустимых выберем ту, в которой достигается минимум искомой величины.

3. Квадратичное решение с квадратичной памятью, динамическое программирование (40 баллов)
Заметим, что для того, чтобы понять, в какой цвет можно красить очередную точку, необходимо лишь знать, где
находится последняя точка того же цвета. Пусть $ans_{i,j}$ обозначает минимальное количество пар соседних точек одного 
цвета в корректной раскраске отрезка $[1,max(i,j)]$, где $i$ --- номер последней белой точки, а $j$ --- последняя точка, 
окрашенная в черный цвет.
		
[Картинка 3, файл dynpic3.png]

Для подсчета динамики будем перебирать, в какой цвет будет окрашена очередная точка с номером $max(i, j) + 1$.
Допустим, мы хотим покрасить её в черный цвет. Тогда необходимо проверить, что $x_{max(i, j) + 1} - x_j$ 
лежит в пределах $[l_1,r_1]$, после этого попробовать обновить ответ для состояния $ans_{i,max(i, j) + 1}$.
В таком динамическом программировании мы имеем $O(n^2)$ состояний, $O(n^2)$ переходов, $O(n^2)$ памяти.

4. Квадратичное решение с линейной памятью, динамическое программирование (60 баллов)

Состоянием будет последний момент смены цвета. Для вычисления ответа будем перебирать, где произошла
последняя смена цвета до этого состояния, после этого проверим, что этот отрезок действительно можно
покрасить (между соседними точками отрезка допустимые для данного цвета расстояния), и что расстояние до предыдущей точки
также является допустимым.

[Картинка 2, файл dynpic2.png]

Такое динамическое программирование имеет $O(n)$ состояний, $O(n^2)$ переходов, каждый переход за выполняется за $O(n)$, $O(n)$ памяти.
Итоговое время работы $O(n^3)$, такое решение набирает 20 баллов.
Однако, если перебирать переходы справа налево, то можно проверять отрезок на корректность по ходу,
и таким образом получить решение на 60 баллов.

5. Решение за O(n log n), использование струтур данных (80 баллов)

Инвертируем задачу: решим задачу максимизации количества пар соседних точек разного цвета (так как общее число соседних точек
фиксировано, то эти задачи эквивалентны).
Заметим также, что множество допустимых переходов представляет собой непрерывный отрезок, на этом отрезке нам
требуется находить максимум. Это можно делать с использованием дерева интервалов за $\log n$ на один переход, 
итоговое время работы $O(n \log n)$ и 80 баллов.

6. Линейное решение, использование метода двух указателей (100 баллов)

Решающим соображением при оптимизации предыдущего решения является то, что границы 
допустимого отрезка при перемещении к следующему состоянию двигаются только вправо.
Таким образом, их можно сдвигать с помощью стандартного метода двух указателей, суммарно при этом затратив $O(n)$ времени.
Для отрезка, концы которого двигаются только вправо (<<окно>>), мы можем решать задачу о поиске максимума за $O(n)$ в сумме.

Более подробно, для поддержания максимума в окне мы воспользуемся структурой данных \texttt{deque}, в которым будем
держать текущих кандидатов на максимум. При движении правой границы вправо будем выбрасывать элементы с конца дека, пока
они меньше нашего элемента. При движении левой границы просто выбросим элемент из начала дека (если он до этого выброшен не был).
Решение с использованием этой структуры данных получает заслуженные 100 баллов.
