Центроидная декомпозция и модели памяти (18 марта 2025)

  1. Disjoint Sparse Table
    1. База за [nlogn, logn]
    2. Немного битовой магии: улучшаем logn до O(1)

  2. Centroid Decomposition, как обобщение Disjoint Sparse Table
    1. Поиск и существование центроида: dfs + dfs
    2. Min на пути в дереве за [O(nlogn), O(logn)].
    3. Построение и хранение за nlogn. level[], parent[], f[][]; вершины из дерева не удаляем, а помечаем.
    4. Дерево центроидной декомпозиции и LCA в нём. LCA за O(depth).
    5. [skipped] [ушло в практику] и O(loglogn) (т.к. глубина logn)
    6. Код: calcSize, findCenter, buildCentroids, findLCA(a,b)
    7. Итог: получили мощную структуру, которая как минимум умеет считать любую функцию на пути в дереве за [O(nlogn), O(logn)].
− Перерыв −
  1. Крутая жадность с заменами
    1. Задача: даны дедлайны окончания di и времена исполнения ti
    2. Выбрать макс число задач за O(n2). Сортировка по di + динамика minSumT[i,k].
    3. Выбрать макс число задач за O(nlogn). Жадность с заменами: поддерживаем minSumT только для максимально возможного maxK.
    4. Доказательство: на самом деле мы знаем весь слой динамики, ответ для каждого k ≤ maxK : minSumT[i,k] − это первые k в сортировке по ti maxK выбранных.
    5. Применяем доказательство к задаче: спортсмены с силой si, массой mi выстраиваются в башню. Выстроить всех: сортировка по si+mi.

  2. Жадности и приближения
    1. Set Cover ln(n)-OPT.
    2. [skipped] [ушло в практику] взвешенный случай Set Cover
    3. [skipped] [Ушла в практику] Надстрока (жадное решение)
    4. [skipped] [Ушла в практику] Хорновские формулы (определение: не более одного отрицания в каждом дизъюнкте)

  3. Рюкзаки, PTAS-ы для knapsack
    1. Задачи: partition, subsetsum, knapsack, binpacking. Целочисленность, вещественность.
    2. NP-трудоность: сводим решаем partition через любую из subsetsum, knapsack, binpacking
    3. Определяем PTAS и FPTAS (приближение для любого ε)
    4. [skipped] [ушло в практику] PTAS для рюкзака без стоимостей (partition).
    5. Рюкзак со стоимостями (knapsack)
      1. Проблема обычной жадности по wi/pi: никак не приближает
      2. PTAS (1+1/k) приближение (переберём какие k точно возьмём за nk)
      3. FPTAS: динамика maxProfit[i, weight] и minWeight[i, profit]. Берём вторую динамику и делим профиты всех предметов на K.

  4. Жадное решение для partition
    1. Что собственно хочется приближать? |sum(ai)-sum(bi)| плохо, max(sum(ai), sum(bi))
    2. Жадность: sort(wi), класть в меньший из двух
    3. Понимание того, что это 6/5-OPT: n=4 предмета мы всегда решим оптимально, далее разность не более a5 ⇒ ошибка не более a5/2
    4. На самом деле это 7/6-OPT
− Перерыв −