Meet-in-the-middle

Рассмотрим какую-нибудь задачу на перебор подмножеств, которую мы умеем решать за $O(2^n \cdot poly(n))$, где $poly(n)$ — какой-то полином от размера задачи $n$. Метод meet-in-the-middle (дословно, «встреча в середине») позволяет соптимизировать перебор до $O(2^{n/2} \cdot poly(n))$ в большом классе таких задач.

В качестве конкретного примера, рассмотрим задачу о рюкзаке — нужно выбрать подмножество $a_i$ с суммарным весом $w$:

bool find_subset(int *a, int n, int w)
    for (int mask = 0; mask < (1 << n); mask++) {
        int s = 0;
        for (int i = 0; i < n; i++)
            if (mask >> i & 1)
                s += a[i];
        if (s == w)
            return true;
    }
    return false;
}

Здесь мы перебираем все подмножества и каждое проверяем за $O(n)$, что дает асимптотику $O(2^n \cdot n)$.

В теории можно избавиться от проверки за $O(n)$, если перебирать маску рекурсивно и поддерживать текущую сумму на префиксе, возможно добавляя во время спуска только один элемент. Однако мы погонимся за более мощной оптимизацией.

#Решение

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

Сначала посчитаем суммы для всех подмножеств среди первых $l = \lfloor \frac{n}{2} \rfloor$ элементов и положим в хеш-таблицу:

unordered_set<int> t;

int l = n / 2;

for (int mask = 0; mask < (1 << l); mask++) {
    int s = 0;
    for (int i = 0; i < n; i++)
        if (mask >> i & 1)
            s += a[i];
    t.insert(s);
}

Затем переберем все суммы среди оставшихся $r = n - l = \lceil \frac{n}{2} \rceil$ элементов и для каждой попытаемся найти подходящую половину (с суммой $s_l = w - s_r$) через предподсчитанную хеш-таблицу:

int r = n - l;

for (int mask = 0; mask < (1 << r); mask++) {
    int s = 0;
    for (int i = 0; i < r; i++)
        if (mask >> i & 1)
            s += a[l + i];
    if (t.count(w - s))
        return true;
}

Обе фазы (а значит и сам алгоритм) работают за $O(2^{n/2} \cdot n)$: мы перебираем $2^{n/2}$ подмножеств и для каждого за $O(n)$ считаем сумму и делаем запрос добавления / проверки наличия в хеш-таблицу за $O(1)$.

Заметим, что оба перебора всё ещё можно так же соптимизировать в $O(n)$ раз через трюк с рекурсией.

#Другие примеры

Задача. Найти количество чисел до $10^{14}$ с суммой цифр $s$.

Разделим число на левую часть (старшие 7 разрядов) и правую (младшие 7 разрядов). Для всех чисел левой части предподсчитаем, сколько из них имеют сумму $s$ и запишем это в массив предподсчёта (его размер будет $7 \times 9 + 1 = 64$). Затем переберем правую часть, и тогда для «левой» суммы $s$ нам нужно найти количество правых частей с суммой $(w - s)$, для чего мы просто за $O(1)$ обращаемся к предподсчитанному массиву.

На больших ограничениях эта задача решается через динамику по цифрам.

Задача. Дан граф из $n$ вершин. Нужно найти количество клик — подграфов, в котором все вершины связаны со всеми.

Сначала научимся решать задачу полным перебором. Пусть у нас есть матрица смежности графа. Как быстро проверить, что подмножество вершин $m$ является кликой?

За $O(n^2)$ можно пройтись по всем парам включенных вершин и для каждой проверить, есть ли единичка в матрице смежности. Проверку можно соптимизировать до $O(n)$, посчитав маску $m’$, равную побитовому «И» строчек матрицы смежности, соответствующих вершинам $m$. Теперь, если $m$ является подмножеством $m’$, то есть

то подграф $m$ является кликой: для всех его вершин есть ребро из всех других.

Воспользуемся этим трюком для слияния ответов в meet-in-the-middle. Разделим граф на две части, найдем для левой все клики и пометим их маски единицами в специальном массиве is_clique[mask] размера $2^{n/2}$.

Теперь будем перебирать подграфы второй половины, и для каждой клики нам нужно найти количество клик левой половины, являющихся подграфами пересечения списков смежности для правой половины ($m’$ из проверки выше).

Чтобы сделать это быстро, предподсчитаем поверх массива is_clique динамику «как много подмасок данной маски являются кликами». Эту динамику можно посчитать за $O(2^{n/2})$, если для каждой маски $m$ рассмотреть два варианта — когда первая вершина $v$ включена в клику и когда не включена:

Итоговая асимптотика алгоритма будет $O(2^{n/2} \cdot n)$.

Задача. Неявно задан очень большой невзвешенный граф, в котором у каждой вершины не более $k$ переходов. Требуется найти расстояние от $s$ до $t$, если известно, что оно не превышает $n$.

Запустим обход в ширину одновременно из обеих вершин, записывая рядом с вершинами расстояния от $s$ или $t$ найденные соответствующим обходом. Когда обход с одной стороны зайдет в вершину, посещенную другим обходом, то восстанавливаем путь размера $(d_s + d_t)$ и завершаемся.

Так как расстояние не превосходит $n$, то алгоритм гарантированно завершится за $O(\frac{n}{2})$ «волн». Так как каждая вершина связана с не более $k$ другими, и в «родителя» алгоритм не заходит, на следующей волне будет не более чем в $(k-1)$ раз больше вершин, чем на предыдущей.

Значит суммарно будет посещено $O((k-1)^{n/2})$ вершин, чему и будет равна асимптотика алгоритма.