Корневые эвристики - Course 4

Module 1: Trie

БОР

Module 2: Sparse Table

Разреженная таблица

Module 3: Segment Tree

Дерево отрезков
Максимальная сумма подотрезка на заданном отрезке

Module 4: Segment Tree Lazy propagation

Segment Tree с Lazy Propagation

Module 5: More on trees

Euler порядок посещений вершин
DP на дереве (Tree DP)

Module 6: Binary jumping

Двоичные подъёмы (прыжки)
Наименьший общий предок

Module 7: Cyclic Games

Игры на циклических графах

Module 8: Divide & Conquer

Разделяй и властвуй

Module 9: SQRT Techniques

SQRT Декомпозиция
Корневые эвристики
Алгоритм Мо

Главная Курсы Ресурсы Задачи Национальная олимпиада Соревнования Таблица лидеров

...

Главная/Courses/Course 4/Module 9: SQRT Techniques/Корневые эвристики

Корневые эвристики

Корневые эвристики

Корневые эвристики — это обобщённое название методов и структур данных, которые опираются на факт:

если разделить множество из $n$ элементов на блоки по $\sqrt{n}$ элементов, то блоков будет не больше $\sqrt{n}$ .

Up next

Алгоритм Мо

Алгоритм Мо

Ключевая идея:
«маленьких объектов много, но они маленькие; больших объектов мало»

Деление на тяжёлые и лёгкие объекты

Классический пример — факторизация за корень.

Если $d \ge \sqrt{n}$ — «большой» делитель числа $n$ , то ему соответствует «маленький» делитель:

$\frac{n}{d} \le \sqrt{n}.$

То есть больших делителей мало, потому что каждому большому соответствует малый.

Такая логика часто переносится на другие объекты: строки, вершины графа, типы запросов, веса предметов и т.д.

Длинные и короткие строки

Задача

Нужно онлайн поддерживать множество строк и обрабатывать операции:

Добавить строку в множество
Удалить строку из множества
Для заданной строки посчитать, сколько раз она встречается как подстрока среди всех строк множества

Идея

Разделим строки на:

короткие: $|s| < L$
длинные: $|s| \ge L$

Здесь $L$ выбирается как $\sqrt{S}$ , где $S$ — суммарная длина всех строк.

Тогда длинных строк мало: не больше $\frac{S}{L} = O(\sqrt{S})$ .

Как отвечать на запросы

Для добавления/удаления:
- перебираем все короткие подстроки строки
- считаем их хеши и обновляем хеш-таблицу (счётчик)
Запрос типа 3:
- если строка короткая — просто смотрим её хеш в таблице
- если строка длинная — можем позволить себе проверить её по всем строкам множества (потому что длинных запросов будет мало)

Треугольники в графе

Задача

Дан граф из $n$ вершин и $m \approx n$ рёбер. Нужно посчитать количество циклов длины 3 (треугольников).

Определение тяжёлой вершины

Вершина тяжёлая, если её степень больше $\frac{S}{L} = O(\sqrt{S})$ , иначе лёгкая.

Тяжёлых вершин мало: их не больше $O(\sqrt{n})$ .

Оценка количества треугольников

Разбираем по числу тяжёлых вершин в треугольнике:

Нет тяжёлых вершин
В треугольнике есть ребро $(a,b)$ , третья вершина $c$ лежит в пересечении/объединении соседей.
Так как степени маленькие, получаем ограничение порядка $m \approx n$ .
Одна тяжёлая
Аналогично: есть «лёгкое» ребро → оценка тоже $O(m\sqrt{n})$ .
Две тяжёлые
Фиксируем ребро $(a,c)$ , способов $O(m)$ .
Тяжёлых вершин всего $O(\sqrt{n})$ → снова .
Три тяжёлые
Тяжёлых вершин мало, перебор также укладывается.

Итого треугольников «не так много»: порядка $O(m\sqrt{n})$ .

Простое решение (идея)

Отсортируем вершины по (степень, номер).
Дальше перебираем пути вида $v \to u \to w$ в правильном порядке и проверяем наличие ребра $v \to w$ .

Рюкзак за $O(S\sqrt{S})$ и быстрее

Условие

Есть $n$ предметов с весами $w_1, \dots, w_n$ , причём:

$\sum w_i = S.$

Стандартная динамика работает за $O(S \cdot n)$ .

Замечание: различных весов мало

Если есть $k$ различных положительных весов с суммой $S$ , то:

$S \ge 1 + 2 + \dots + k = \frac{k(k+1)}{2}$

откуда:

$k \le O(\sqrt{S}).$

То есть различных весов не больше $O(\sqrt{S})$ .

Сжатие кратностей (разложение по степеням двойки)

Если вес $x$ встречается $k$ раз, разложим $k$ в суммы степеней двойки и заменим эти $k$ предметов на предметы весов:

$x,\ 2x,\ 4x,\ \dots$

Так сохраняются все суммы вида $q \cdot x$ для $q \le k$ .

После такого преобразования число предметов становится порядка $O(число\_весов \cdot \log S)$ , а дальше запускаем стандартную динамику.

Примечание: решение рюкзака можно сильно ускорить с помощью bitset.

)

O(m\sqrt{n})

long long count_triangles(int n, vector<vector<int>> &g) {
    vector<int> deg(n);
    for (int v = 0; v < n; v++) deg[v] = (int)g[v].size();

    auto better = [&](int a, int b) {
        if (deg[a] != deg[b]) return deg[a] < deg[b];
        return a < b;
    };

    // sort vertices by (degree, id)
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), better);

    // sort adjacency lists in the same order
    for (int v = 0; v < n; v++) {
        sort(g[v].begin(), g[v].end(), better);
    }

    vector<int> cnt(n, 0);
    long long ans = 0;

    for (int v : order) {
        // mark all "forward" neighbors of v
        for (int u : g[v]) {
            if (!better(v, u)) break;
            cnt[u] = 1;
        }

        // count triangles v - u - w where v<u<w in this order
        for (int u : g[v]) {
            if (!better(v, u)) break;
            for (int w : g[u]) {
                if (!better(u, w)) break;
                ans += cnt[w];
            }
        }

        // unmark
        for (int u : g[v]) {
            if (!better(v, u)) break;
            cnt[u] = 0;
        }
    }

    return ans;
}