Игры на графах и битовое сжатие (5 мая)

  1. Чуть-чуть битового сжатия
    1. Хранение множеств: сортированный массив, битсет
    2. unisgned long long = 64 бита = битсет из 64 элементов
    3. Операции с множествами: O(n+m), O(C/w) (C − диапазон чисел, w − машинное слово)
    4. bitset<C> − внутри содержит массив длины C/w+1, позволяет писать "битовое сжатие"
    5. Задача: умножение булевых матриц за O(n3/w)
  2. Игры на ацикличных графах
    1. Определение игры. Выигрышная, проигрышная позиция
    2. Динамика
    3. функция Гранди (формальное определение, подсчёт динамикой)
    4. mex за O(deg), функция Гранди за O(E)
    5. G[v] == 0 ⇔ LOSE[v]
  3. Теорема Гранди
    1. Определение: прямая сумма игр
    2. Формулировка: G[v,u] = G[v] xor G[u]
    3. Игра Ним. Функция Гранди для Нима. Доказательство для Нима из двух кучек.
    4. Доказательство для произвольных двух игр.
    5. Доказательство для произвольных k игр.
  4. Ретроанализ
    1. Наивный алгоритм (начальное состояние: какие-то вершины проигрышные, какие-то выигрышные)
    2. Реализация за O(E)
    3. Длина игры
  5. Игра на супер большом дереве
    1. Формулировка задачи, откуда берутся такие деревья
    2. Подсчёт результата игры динамикой за O(2n)
    3. Отсечение рандомом, оценка времени работы T(n) = 2T(n-2) + 0.5T(n-1) ≤ 1.687n