Разбор задач

Разбор задач контеста на динамическое программирование по профилю и подмножествам, московские осенние учебно-тренировочные сборы по информатике, 4 ноября 2007 года.

   

Подробное описание решения первых двух задач можно прочитать в статье «Динамическое программирование по профилю». Саму статью можно найти в книжке «Московские сборы по информатике, Весна-2006», ее pdf и html версии прикреплены к данному модулю в качестве теоретических материалов.

Прежде чем рассказывать решения остальных задач, обсудим термин «динамика по подмножествам».  Пусть имеется множество Pn первых n натуральных чисел.  Тогда количество всевозможных его подмножеств равно 2n. Более того, каждое множество можно хранить в памяти компьютера как последовательность из n битов. Единичка на i-й позиции (i = 0, 1, ..., n – 1, то есть нумерация битов происходит с нуля) будет означать наличие элемента (i + 1) в подмножестве. Таким образом, если ограничения на какой-либо параметр в задаче достаточно маленькие, то стоит задуматься на предмет существования решения,  работающего с подмножествами фиксированного множества.

Задача C.          В  этой задаче надо было найти количество различных путевых меток в орграфе G. Ключевым моментом здесь является тот факт, что количество вершин не превышает  10.

Для удобства рассмотрим вспомогательный массив edge[p][c], где 0 ≤ p < 2n означает некоторое подмножество вершин графа, c  – символ от “a” до “z”. Положим edge[p][c] по определению равным подмножеству всех вершин G, в которые можно попасть из какой-либо вершины множества  p по ребру, помеченному символом c. Таким образом, 0 ≤ edge[p][c] < 2n.

Переходим непосредственно к решению задачи. Зафиксируем множество вершин p и число L. По определению, a[p][L] равно количеству различных путевых строк S (путевых меток) длины L, удовлетворяющих двум свойствам:

1)     для любой вершины J из множества p найдется путь с путевой меткой  S, заканчивающийся в  J.

2)     для любой вершины K не из множества p не существует пути с путевой меткой S, заканчивающегося в K.

В  частности, у всех путей из первого свойства длина равна L.

Очевидно, что a[2n - 1][0] = 1 и a[p][0] = 0 для всех 0 ≤ p < 2n – 1, так как среди нулевых строк имеется только пустая. Научимся по a[p][L - 1] вычислять a[p][L].

Как получается любая строка S, посчитанная в a[p][L]? Удалим из нее последний символ: S[1..L – 1] = T, и рассмотрим максимальное множество q вершин, в каждой из которых заканчивается путь с такой путевой меткой. Тогда строка T посчитана в a[q][L  1] и больше нигде по построению. Таким образом,

Задача С. Формула

 

При реализации разумнее всего проводить вычисления «впрямую», то есть

for c := 'a' to 'z' do begin
    for q := 0 to (1 shl n) - 1 do begin
        a[edge[q][c]][L] := a[edge[q][c]][L] + a[q][L - 1];
    end;
end;

 

В заключение докажем корректность работы алгоритма индукцией по L. Нетрудно видеть, что при L = 0 все условия (свойства 1, 2) выполнены. Докажем, что если a[q][L – 1] удовлетворяет определению, то по приведенным выше формулам a[p][L] также вычисляется верно.

Возьмем строку S длины L, удовлетворяющую свойствам 1 и 2, пусть ее последний символ равен c. Пусть q  – максимальное множество вершин J, таких, что существует путь с путевой меткой T, заканчивающийся в J, и из J существует ребро в любую вершин множества p, помеченное символом c. Оно не пусто, так как любая предпоследняя вершина любого пути из свойства 1 входит в q. Поэтому строка T посчитана в a[q][L – 1], причем edge[q][c] = p. По формуле, строка S посчитана в a[p][L] хотя бы один раз.

     Если какая-то строка S была посчитана дважды в a[p][L], то найдутся q1q2, такие, что S[1..L – 1] = T посчитана в a[q1][L – 1] и a[q2][L – 1]. Но множества q1 и q2 максимальные по свойству 2, поэтому обязаны совпадать.

      Замечу, что a[p][L] зависит только от a[q][L – 1], поэтому можно сэкономить память и хранить значения только для L – 1.

     Так как надо найти остаток ответа при делении на 106, то все вычисления следует производить по модулю миллион.

Задача D.          В этой задаче требовалось вычислить минимальное количество прямоугольников, которыми можно замостить доску с вырезанными клетками.

       Задача D. Рис. 1Базовой линией номер j назовем границу между столбцами j и j + 1 (столбцы нумеруются с  1 до M, базовыми линиями номер 0 и M назовем левую и правую границы таблицы). Рассмотрим какое-либо замощение прямоугольниками. Нас интересуют прямоугольники, лежащие (хотя бы частично) в j-м столбце. Профиль  – число то 0 до 2N - 1  – должен содержать информацию, по которой можно сказать, лежат ли две данные клетки  j-го столбца в одном прямоугольнике замощения  (будем тогда говорить, что эти клетки инцидентны) или в разных (не инцидентны).

     Например, единичка в k-м бите (они нумеруются с нуля: 0 ≤ k < N) профиля означает последнюю клетку текущего прямоугольника.  В этом случае алгоритм выявления всех квадратиков j-го столбца, инцидентных квадратику с номером (k + 1), выглядит следующим образом:

1.      Если этот квадратик (k + 1, j) вырезан их таблицы, то ответ ясен. Иначе:

2.      Пока текущий бит равен нулю, двигаемся вниз. В итоге мы обязательно наткнемся на конец прямоугольника

 

 

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

 

 

     Например, на рисунке k = 1, мы двигаемся до клетки номер 3 (потому что бит номер 2 равен 1), далее поднимаемся вверх и останавливаемся, достигнув самого верха. В итоге получили, что квадратики 1, 2 и 3 в четвертом столбце инцидентны.

     Пусть теперь a[p][j], где 0 ≤ p < 2N и 1 ≤ jM, по определению равно минимальному количеству прямоугольников, которым можно замостить первые j столбцов, притом разбиение j-го столбца соответствует профилю p. Тогда ответом на задачу будет минимум по допустимым для последнего столбца профилям p среди чисел a[p][M]. Под допустимыми имеются в виду профили существующих разбиений. К примеру, бит, соответствующий вырезанной клетке, не должен быть единицей.

     Положим a[p][1] = (количество единичек в двоичной записи p) для всех допустимых p для первого столбца, и научимся по a[q][j – 1] вычислять a[p][j], для всех p и q.

Задача D. рис. 2    Зафиксируем p. Минимальное разбиение, очевидно, можно найти, перебрав всевозможные профили q предыдущего столбца j – 1, и выбрав минимум из суммы a[q][j – 1] и «стоимости перехода», то есть минимального количества прямоугольников, которые надо будет добавить в разбиение для соответствия j-го столбца профилю p. Обсудим, как его вычислять.

     Если q = p, то эта стоимость не всегда равна нулю. Необходимо помнить о вырезанных клетках. Естественно, наилучший случай  – это когда прямоугольник из (j – 1)-го столбца можно продолжить на j-й. Итак, общий метод таков:

1.      Вычисляем «координаты» прямоугольников для q и p, то есть, закрашиваем в разные цвета инцидентные клетки в (j – 1)-м и j-м столбцах

2.      Если клетки одного цвета в (j – 1)-м столбце лежат в точности напротив клеток одного цвета в j-м столбце, то соответствующий прямоугольник можно продолжить

 

 

3.      Полагаем «стоимость перехода» равной количеству несовпавших цветов в j-м столбце.

 

 

     Например, на рисунке клетки с цветом 2 в обоих столбцах совпадают, поэтому «стоимость инцидентности» равна 2 (добавились прямоугольники, соответствующие номерам 1 и 3 в j-м столбце, а 2 продолжается из предыдущего и будет уже посчитан в a[q][j – 1]).

     Теперь ясно, почему мы не вычисляли, как водится, стоимость перехода d[q][p] заранее. Ведь из-за вырезанных клеток она зависит не только от профилей, но и от номера столбца.

Задача E.         В этой задаче надо было найти кратчайший путь в прямоугольной таблице, охватывающий ровно J клеток, помеченных символом “I”. Решение представляет собой красивую «смесь» поиска кратчайших путей и ДП по профилю. Условимся, что клетки таблицы занумерованы с нуля, клетка (0, 0) находится в верхнем левом углу.

     Для начала вспомним, что интересующих Васю арбузов K не более 10. Занумеруем их числами от 0 до K – 1. Для решения задачи нам будет важно быстро узнавать номера арбузов, растущих в клетках (0, y), (1, y), …, (x, y). Итак, пусть j-й бит (0 ≤ j < K) числа prof[x][y] равен 1, если в столбце номер y арбуз номер j находится не ниже строки x.

     Теперь занумеруем числами от 0 до N горизонтальные дорожки грядки, числами от 0 до M  – вертикальные, парами (x, y)  – точки на пересечении x-й горизонтальной и y-й вертикальной дорожек. Любой путь Васи однозначно задается последовательностью координат точек. Аналогично клеткам, (0, 0) находится в верхнем левом углу.

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

     Далее опишем граф, на котором будет поиск кратчайших путей. Вершинами в нем будут тройки (x, y, p), где 0 ≤ x < N, 0 ≤ y < M  – координаты точки, 0 ≤ p < 2K  – некоторое множество (битовая маска) арбузов. Смысл (определение) числа a[x][y][p] (длины «кратчайшего пути», которую мы будем искать) заключается в следующем. Пусть, блуждая по огороду, мы попали, наконец, в точку (x, y). Теперь пойдем от нее сначала вертикально вверх до точки (0, y), а потом  – горизонтально влево до (0, 0). В итоге цикл может получиться с самопересечениями, но в свете сделанного наблюдения это не страшно. Внутри окажутся арбузы из множества p и никакие другие (можно считать это определением p). Положим L равным длине этого цикла минус (x + y), то есть без учета двух последних его частей. Число a[x][y][p]  – это минимум среди всех таких L. То есть, минимум берется по всем путям от (0, 0) до (x, y), соответствующим p.

     Теперь ясно, что длина кратчайшего пути Васи при обходе ровно J арбузов, равна минимуму по p среди чисел a[0][0][p], где p содержит ровно J допустимых арбузов и не содержит запрещенных.

     Ребрами в этом графе будут переходы из (x, y, p) в соседние вершины (x ± 1, y ± 1, q), где q строго зависит от p, x и y (определение ниже). Таким образом, ребер не более чем в 4 раза больше вершин. Наиболее разумный подход к поиску кратчайших путей  – это модификация поиска в ширину, при которой каждая вершина будет обработана не более четырех раз.

     Опишем алгоритм в деталях. Пусть в нашем распоряжении имеется изначально пустая очередь Q, в которой будут храниться вершины графа.

1.      Добавим в Q тройку (0, 0, 0). Положим a[x][y][p] = ∞ для всех (x, y, p), a[0][0][0] = 0.

2.      Извлечем очередную вершину (x, y, p) из начала Q.

 

3.      Будем пытаться сделать ход в доступных четырех направлениях (следя за тем, чтобы не выйти за границы), корректно меняя при этом множество p. Нетрудно видеть, что при движении вертикально не происходит ничего, ведь в определении a[x][y][p] мы все равно сначала дойдем до (0, y). Поэтому достаточно сравнить a[x ± 1][y][p] с a[x][y][p] + 1, в случае «больше» обновить значение a[x ± 1][y][p] и добавить в конец очереди соответствующую вершину.

 

     Пусть теперь мы двигаемся горизонтально, пересекая столбец номер C = min(y, y ± 1). Второе, красивое наблюдение: в этом случае q = p XOR prof[x][C], где XOR  – побитовое сложение по модулю 2. Действительно, рассмотрим J-й арбуз, находящийся в клетке (a, C). Пусть R  – количество пересечений нашего пути и столбца C, которые произошли не выше дорожки номер a + 1. Если это число четно, то путь уходит влево от этого столбца и не захватывает клетку (a, C), ведь он без самопересечений. Аналогично, если R нечетно, то путь уходит вправо и (a, C) попадает внутрь. По свойствам операции XOR и построению prof[x][C], бит номер J в q совпадает по четности c R, то есть, равен R mod 2.

 

     Осталось проделать действия как в случае вертикального перемещения: сравнить a[x][y ± 1][q] и a[x][y][p] + 1; в случае «больше» обновить a[x][y ± 1][q] и добавить соответствующую вершину в очередь.

 

     В заключение обсудим время работы алгоритма. Каждая тройка обрабатывается не более четырех раз, обработка происходит за O(1), получаем асимптотику O(M*N*2K).

Василевский Борис, vasilevskiy.boris@gmail.com