Про графы [см. 2012-02-09]

1. Сила dfs-а
1. Ориентация графа (запустить один dfs)
2. Мосты (min время входа)
3. Точки сочленения (min время входа)
2. Эйлеров путь и цикл
1. Признак эйлеровости
2. Путь = цикл - ребро
3. Будем идти из вершины v вперед, пока можем. Что получится?
4. Поиск цикла dfs-ом со стэком
3. Циклы
1. Минимальной длины за O(E*bfs), за O(V*bfs), граф не взвешенный (в неорграфе, в орграфе).
2. Минимальной длины,за O(E*Dijkstra), за O(V*Dijkstra) граф взвешенный
3. Отрицательный с помощью FB (см. восстановление пути)
4. Отрицательный с помощью Floyd (см. восстановление пути)
5. Цикл минимального среднего веса за O(VElog) (с бинпоиском)
6. Цикл минимального среднего веса за O(VE) (без док-ва)

Про игры [см. 2012-02-16]

1. Функция Гранди
1. Пример про Ним
2. Пример про Скамейки и Рассадку
3. Смысл: игр много. Если игра всего одна, мы ее полностью исследовали за O(E) в предыдущем пункте.
4. Функция Гранди. Определения через mex, (mex = 0) <=> LOSE.
5. Реализация за O(E).
6. Прямая сумма игр, сила xor-а.
7. Док-во того, что mex(A+B)=mex(A)^mex(B) табличкой 2ⁿ x 2ⁿ.

Задачи (примеры) к играм

1. Ним, но можно брать только a₁, a₂, ..., a_k
2. Ним + кучку можно делить пополам
3. Ним + можно делить на произвольное число слагаемых
4. Штирлиц, Мюллер и очередь
5. Поедание 3D шоколадки (есть всегда меньшую половину)
6. Поедание 3D шоколадки (можно есть любую половину) [решение за O(1)]
7. Hacking-Bush

Перебор

1. Полный перебор.
1. Рекурсия.
2. Предподсчет (на примре задачи "количество графов без мостов из N вершин").
2. Отсечения в переборе.
1. Отсечение по времени.
2. Memorization (хэширование, динамика) - IMPORTANT
3. Отсечение по ответу - IMPORTANT