Краткий обзор задач Универсиады Алтая 2008
Еще один контест, на котором удалось продемонстрировать тупость упорство: одна задача с 23-й попытки, другая с 17-й 
Задача A. Сарафан для призрака датского короля
В задаче может быть 2 случая:
- обе точки на одной прямой;
- точки на разных прямых.
Первый случай тривиален, во втором надо найти точку пересечения этих прямых (если они пересекаются) и вывести суммарное расстояние от исходных точек до нее.
Для работы с прямыми удобно представить прямые в параметрических уравнениях, а находить точки пересечения можно, пересекая проекции прямых на плоскости координат, приводя таким образом задачу к двумерному виду.
Задача B. Лаэрт в затруднении
Условие сводится к нахождению максимального паросочетания в дереве. Задачу можно решить жадно или, для уверенности , динамикой. Для каждой вершины подвешенного дерева будем хранить два значения: величину максимального паросочетания в поддереве этой вершины и величину максимального паросочетания в поддереве вершины, если сама вершина участвовать в паросочетании не может.
Задача C. Загадка Горацио
Классическая задача о нахождении лексикографически минимального циклического сдвига. Для решения можно использовать алгоритмы разложения строки на простые подстроки (алгоритмы Дюваля, Линдона) или суффиксное дерево / автомат.
Задача D. Два могильщика
Скорее всего какой-то перебор, возможно с отсечениями .
Задача E. Полоний и его коллекция
Решение от одного из авторов:
«научимся для тождественной перестановки длины 6 получать все 5 перестановок, где обменяны 2 соседних элемента, поиском в ширину…»
Дальнейшие слова, думаю, излишни
Задача F. Часы для Офелии
Главное в задаче – понять, что хоть часы и электронные, но повадки механических сохранили (все-таки средние века ). То есть при переводе минутной стрелки вперед с 59 на 00, часовая стрелка перейдет на 1 час вперед. Аналогично при переводе назад. Далее все элементарно – либо рассмотреть возможные случаи, либо сделать поиск в ширину.
Задача H. Быть или не быть?
Достаточно как-нибудь заполнить левый верхний квадрат K x K, а дальше надо его «раскопировать».
