Ну, как всегда, первый блин комом :( В задаче F под конец контеста обнаружился бажный тест, который, наверное, порядком попортил нервы Ренату Муллаханову и Арсению Алексееву. Приношу свои извинения – недоглядел.

Задачи, результаты.

Поздравляю победителя Рената Муллаханова, решившего все 7 задач.

Спасибо всем, кто поучаствовал, а также большое спасибо Улану Дегенбаеву, все отлично организовавшему.

Задача A. Google Maps

Пусть мы знаем, что точка лежит строго в квадрате (x1, y1) – (x2, y2). Тогда попробуем разделить этот квадрат на 4 части и посмотреть, в какой из частей лежит наша точка. Если нашлась такая часть, в которой точка лежит строго (не на границе), то меняем x1, y1, x2, y2 на координаты этой части, добавляем к результируещей строке соответствующий символ и повторяем процедуру. Как только мы не сможем этого сделать, значит получили ответ.

Задача B. Раскраска графа

Правильное решение этой задачи – использование леммы Бернсайда. Но, в принципе, не исключается возможность существования хорошего перебора.
Итак, правильное решение:
1. переберем все правильные (т.е. сохраняющие список ребер) перестановки вершин;
2. для каждой перестановки посчитаем количество циклов (Qi);
3. посчитаем количество способов раскрасить i-ю перестановку так, чтобы в каждом цикле все вершины были одного цвета (т.е. K ^ Qi);
4. просуммируем все K ^ Qi и разделим на количество правильных перестановок – полученное число и будет ответом.

Задача C. Трубы

Очевидное решение – динамика по профилю. Для удобства облегчения пересчета лучше использовать изломанный профиль:

Профиль хранится в виде двух чисел: первое – битовая маска, хранящая в i-м бите, есть ли конец трубы на i-й грани профиля (номера граней приведены на рисунке), второе число – количество ячеек во второй строке профиля (от 0 до M-1, где M – ширина сетки).

Переход к следующему профилю осуществляется подстановкой всех вариантов новой ячейки, которых всего от 1 до 4.

Задача D. Точки

Для начала, для каждой точки (Xi, Yi) найдем ближайшего соседа (Xj, Yj) такого, что Xj >= Xi и Yj >= Yi. Заметим, что в этом случае расстояние между точками будет (Xj – Xi) + (Yj – Yi) = (Xj + Yj) – (Xi + Yi).

Теперь отсортируем точки по возрастанию X, а при равных X по возрастанию Y и пойдем по ним справа налево. По мере обработки i-ю точку будем заносить в дерево интервалов с индексом Yi и значением Xi + Yi. Перед занесением i-й точки выберем из дерева интервалов максимум на отрезке [Yi, infinity) - точка, соответствующая этому значению и будет искомым ближайшим соседом.

Теперь для нахождения, возможно, более близких соседей с других сторон, отразим все точки относительно оси OX, затем OY, затем относительно обеих осей (хотя, можно попробовать сделать только одно отражение), каждый раз повторяя вышеприведенную процедуру. При этом важно не забыть про лексикографически минимальный ответ.

Задача E. Многоугольник

Вариант этой задачи с вершинами в целочисленных координатах решается достаточно просто с теоремой Пика. Однако для нецелочисленных координат, мне кажется, такого простого решения нету :) Однако, если посмотреть на необычное ограничение на периметр, все становится понятным! Достаточно пройти по каждой координате X каждого ребра и, используя что-то вроде метода трапеций для нахождения площади многоугольника, все посчитать. Конечно, лучше все делать в целых числах...

Задача F. Подпоследовательность

Здесь нужно сначала научиться динамикой считать количество различных возрастающих подпоследовательностей, а затем, используя полученные знания, стандартным способом (подбирая последовательно элементы) восстановить искомую подпоследовательность.

Задача G. Обои

Самая большая и, наверное, самая непонятная задача :) Если отбросить все лишнее, то задача заключается в определении, какой цвет сделать нижним, чтобы количество докупаемых рулонов было минимальным.

Основная идея: разрежем все оставшиеся кусочки обоев на одноцветные полоски. То есть у нас есть просто Ki полосок цвета i.

Теперь для каждого j-ого снизу на стене цвета посчитаем количество необходимых полосок Cj.

Осталось найти такое l, что max(C[i] – K[l + i]) (считаем, что массив K циклический) минимально. Это можно сделать, заметив, что в массиве C может быть максимум 2 разных значения, сгруппированных одно в начале, а другое в конце. Пройдемся по всем l и, так как соответствующие значения массива C одинаковы, будем просто находить минимумы на соответствующих отрезках массива K, затем считать количество рулонов и улучшать ответ, если надо. Находить минимумы можно за логарифмическое время, используя дерево интервалов, но можно и за константное, используя представление очереди в виде двух стеков (спасибо Петрозаводску :) ).

Автором задачи A является Бахыт Маткаримов, остальные написаны мной.