Блог пользователя Nerevar

Автор Nerevar, 13 лет назад, По-русски

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

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

Теперь научимся перебирать все ограниченно растущие строки, каждый раз изменяя одно значение в текущей строке для перехода к следующей. Очевидно, что применительно к разбиениям это будет означать именно то, что требуется в задаче. Достаточно простой способ построения такого списка ограниченно растущих строк называется схемой Эрлиха. Пусть имеется список ограниченно растущих строк s1, s2, ..., sk длины n - 1, удовлетворяющий требуемому порядку. Получим из него список для n. Пусть si = a1a2... an - 1, а m = 1 + max(a1, ..., an - 1). Тогда, если i нечетно, то будем поочередно приписывать к строке si цифры 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 вида запросов к этой структуре:

1) найти элемент с наименьшим значением среди всех, попадающих в заданную прямоугольную область.
2) удалить заданный элемент.

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


Задача F. BerPaint.

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

1) Ребро между двумя нефиктивными отрезками проводится, если они имеют общую концевую точку.
2) Ребро между областью и отрезком (неважно, фиктивный он или нет) проводится, если они имеют более одной общей точки (т.е. отрезок является частью границы области).

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

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

  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Как реализовать двумерное дерево? Разве оно не потребует порядка n^2 памяти? При данных ограничениях, кажется, это слишком много =\
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если его акуратно реализовывать то оно потребует nlogn памяти. Подробнее рекомендую посмотреть решения или почитать литературу.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Here's my solution to I, maybe it'll be useful for someone.
First note that Gray code is 'circular': the last element differs from the first one in one digit. So, we can start enumerating subsets from any position in Gray code.
Now we'll enumerate partitions recursively. Fix the minimal element x and iterate over the (Gray code of the) subset of elements which are in the same subset with x. If M is the subset of all other elements, call our procedure recursively for M. We'll obtain a 'good' sequence of partitions. Unfortunately, if M1 and M2 are two consequent values of M, the sequences of partitions for them could not 'glue together': the last partition obtained from M1 can be very different from the first partition obtained from M2. But we can always apply a circular shift to the second sequence so that it glued together with the first one. I don't know what's the complexity of this but it passed the tests.