Задача I. Игрушки.

В задаче необходимо вывести все возможные разбиения заданного множества на подмножества в порядке, напоминающем код Грея. Перейдем к заданию разбиений с помощью так называемых ограниченно растущих строк. Строка a₁a₂a_n называется ограниченно растущей, если a₁ = 0 и a_j + 1 ≤ 1 + max(a₁, ..., a_j) для 1 ≤ j < n. Ограниченно растущая строка для разбиения строится так: a_i = a_j тогда и только тогда, когда элементы i и j принадлежат одному подмножеству в этом разбиении. Например, ограниченно растущая строка для разбиения {1,3},{2},{4} есть 0102.

Теперь научимся перебирать все ограниченно растущие строки, каждый раз изменяя одно значение в текущей строке для перехода к следующей. Очевидно, что применительно к разбиениям это будет означать именно то, что требуется в задаче. Достаточно простой способ построения такого списка ограниченно растущих строк называется схемой Эрлиха. Пусть имеется список ограниченно растущих строк s₁, s₂, ..., s_k длины n - 1, удовлетворяющий требуемому порядку. Получим из него список для n. Пусть s_i = a₁a₂... a_n - 1, а m = 1 + max(a₁, ..., a_n - 1). Тогда, если i нечетно, то будем поочередно приписывать к строке s_i цифры 0, m, m - 1, ..., 1, иначе будем приписывать цифры 1, ..., m - 1, m, 0. В результате каждого приписывания мы получаем очередную строку длины n. Таким образом, начиная со списка 0 для n = 1 мы последовательно получим списки 00, 01 для n = 2 и 000, 001, 011, 012, 010 для n = 3. Схема Эрлиха описана в 3 выпуске 4 тома труда Кнута "Искусство программирования" на страницах 83-84.

Задача G. Тир.

Будем решать немного другую задачу: для каждой мишени определим, какой выстрел ее поражает. Для этого упорядочим все мишени по возрастанию координаты z и будем перебирать их в этом порядке. Мишень обрабатывается следующим образом. Рассмотрим все выстрелы, которые потенциально могут в нее попасть. Очевидно, что это такие выстрелы, координаты которых попадают в прямоугольную область, которая является проекцией мишени на плоскость стрельбы. Среди таких выстрелов мишень поразит тот выстрел, который произошел раньше остальных. После того, как мы нашли этот выстрел, мы исключим его из дальнейшего рассмотрения, и будем дальше перебирать мишени. Легко видеть, что будет выполняться такой инвариант: на момент обработки очередной мишени все выстрелы, которые были направлены в нее, но не долетели по причине попадания в другие мишени, будут уже обработаны.

Теперь о том, как эффективно реализовать описанный алгоритм. Будем хранить выстрелы в некоторой структуре данных. Легко выделить 2 вида запросов к этой структуре:

В качестве такой структуры можно использовать двумерное дерево отрезков с функцией минимума. Не буду вдаваться в то, что представляет из себя эта структура. Некоторую сложность представляет организация удаления элемента. Но ситуация облегчается тем, что присутствуют только лишь операции удаления, а добавлений нет. Поэтому на каждом уровне дерева можно заранее предподсчитать, какой элемент станет следующим минимумом при удалении данного. Общая асимптотика авторского решения составляет O((N + M)log²N.

Задача F. BerPaint.

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

Очевидно, что любая область, которая может быть окрашена в результате заливки, соответствует некоторой компоненте связности построенного графа. Поэтому задачу можно решать так. Для каждой вершины будем хранить ее цвет. При обработке операции заливки мы находим все вершины такие, что соответствующие им объекты содержат точку заливки. При этом, если вершине соответствует область, то точка должна находиться строго внутри области. Если вершине соответствует фиктивному отрезку, то точка должна принадлежать этому отрезку, но не совпадать ни с одним из его концов. В случае нефиктивного отрезка точка должна просто принадлежать ему. Из всех найденных вершин запустим обход графа, который обойдет все вершины, достижимые из данной и имеющие с ней одинаковый цвет, и окрасит их в цвет заливки. После проведения всех заливок нужно просто для каждого цвета, в который окрашена хотя бы одна вершина, просуммировать площадь объектов, соответствующих вершинам, окрашенным в этот цвет.

Основную сложность в задаче представляет разбиение на области. В авторском решении это делается методом вертикальной декомпозиции. Разобьем сначала прямоугольник на вертикальные полосы, такие, что строго внутри каждой полосы не находится никакая из концевых точек отрезков или точка пересечения каких-то отрезков. Затем каждую из этих полос разобъем на трапеции отрезками, которые пересекают эту полосу. Добавим нобходимые для отделения трапеций друг от друга фиктивные вертикальные отрезки и построим граф. Не исключаю, что подобный граф областей и отрезков может быть построен и более простым способом.