Games

1. Симметричные игры на графах
1. На ациклических графах (DP за O(E))
2. На цикличных графах (Ретроанализ за O(E))
3. В обычной DP и ретроанализе поиск самого быстрого выиграша и самого долгого проигрыша.
2. Функция Гранди
1. Смысл: игр много. Если игра всего одна, мы ее полностью исследовали за O(E) в предыдущем пункте.
2. Функция Гранди. Определения через mex, (mex = 0) <=> LOSE.
3. Реализация за O(E).
4. Прямая сумма игр, сила xor-а.
5. Док-во того, что mex(A+B)=mex(A)^mex(B) табличкой 2ⁿ x 2ⁿ.
3. Примеры
1. Шоколадка (решение за O(n³)) [есть 2D грид, один из кусочков можно поделить на 2 по любому из измерений]
2. Решение за O(1) (четные = выигрышные, остальные = проигрышные), или так: в конце все кусочки будут 1x1 => знаем, сколько всего ходов.
3. Шоколадка + нельзя делить попалам
4. Ним + кучку можно делить пополам (= то же самое, что и Ним)
5. Ним + кучку можно делить на произвольное число слагаемых
6. Штирлиц, Мюллер и очередь
7. Hacking Bush
4. Теория Смита
1. Алгоритм Смита.
2. Реализация алгоритма за O(VE), O(E^3/2)
3. Непомеченные вершины = A^inf, где A - множество конечных вершин-детей
4. По состоянию понимаем, Draw OR Lose OR Win. A^inf - Win, если в A есть 0, иначе Draw
5. Учимся XOR-ить 2 состояния (числа XOR-ятся также как в случае Гранди, inf + inf = Empty^inf, A^inf + a = (A XOR a)^inf)
5. Эквивалентность и док-во Смита
1. Определение, любой ацикличный граф G ~= ниму a*
2. Док-во эквивалентности игр для ацикличных графов (Гранди)
3. Док-во эквивалентности игр для цикличных графов (Смит)
4. Суть док-ва - у нас есть "лишние" ходы (ребра). Лишние - не позволяющие первому игроку выиграть (или свести в ничью).

Переборные стратегии

1. Полный перебор.
1. Рекурсия.
2. Мир глобален, не копируется, после отката из рекурсии возвращается в старое состояние.
3. Пример на задачки "найдем число путей на клетчатой плоскости".
4. Предподсчет.
2. Метод Ветвей и Границ (на примере задачи timus : 1152)
1. Отсечение по времени.
2. Memorization (хэширование, динамика) - IMPORTANT
3. Отсечение по ответу - IMPORTANT
4. Жадность, сортировка ребер
5. Выбор первых k ребер.
6. Iterative Increasing of k
7. Iterative Deepening
8. Нерекурсивная реализация bfs-ом. Очередь с ограничением по длине.
3. Локальные оптимизации (введение, на примере Коммивояжера)
1. Разворот двух пересекающихся отрезков.
2. Случайные изменения
3. Попытка переставить 5 подряд идущих вершин оптимальным способом.
4. while (exists) do
5. Начальное приближение дает хорошая жадность (Nearest).
4. Отжиг (введение)
1. На примере задачи веревкой длины P ограничить максимальное число точек на плоскости.
2. Функция, которую мы оптимизируем f(state)
3. Пытаемся сделать переход, меняем состояние. Вероятность изменения = exp{-t} (можно вносить заведомо "хорошие" изменения)
4. Пытаемся взять или не взять новое состояние. Если f улучшилась, берем, если ухудшилась, то берем с вероятностью = exp{-t}.
5. Отличия от Локальных Оптимизаций: иногда функция ухудшается
5. Генетические алгоритмы (введение)
1. Есть поколение состояний. Мы умеем модифицировать одну особь (состояние) отжигом.
2. Можно параллельно улучшать (модифицировать) все особи и оставлять сколько то лучших.
3. Добавим скрещивание (создание новой особи из старых двух)
4. Оставим часть прежнего поколения.
5. Добавим вероятность того, что плохое состояние тоже выживет.
6. Увидим связь с bfs-ом в Методе Ветвей и Границ.