-----------------------------> Структуры данных --------- День 01 --------- Дерево отрезков (д.о.) 1. Определение. Применение для функций Sum, Min, Max, Product. 2. Построение по массиву за O(n) 3. Реализация запроса a[i] = x снизу и сверху 4. Реализация запроса Get(i, j) снизу и сверху 5. Реализация запросов a[i..j] += x и a[i..j] = x сверху (запрос Get тоже должен быть сверху) 6. Реализация всего в одном сверху (+=, =, get) *7. Реализация запроса += снизу. 8. Дерево отрезков без сжатия координат O(NlogM, logM). Случаи целых и вещ чисел 9. Фишка реализации снизу: памяти в худшем случае всего 2n (3n и 4n для сверху) Задачи на дерево отрезков 1. Покраска отрезков. Нужно выполнять запросы color[i..j]=c, и в конце для каждого цвета определить, сколько его. Тут же нужно рассказать про то, что при сжатии координат [L..R] = [L..R+1) 2. Числа 0..10^5 операции Add, Del, Min (count[x] хранение позиции min-а или [x, inf] в листьях ) 3. Только Del и Min, числа произвольные. 4. Дан set чисел. Переход к следующему, к i-му (а) Реализуем два запроса Get(i) и GetPos(x) (б) Сперва идем вверх, затем спускаемся вниз 5. Использование дерева отрезков как Binary Search Tree (если ключи от 0 до 10^9 --- use динамическое д.о.) 6. ScanLine + сжатие координат а) Max по вложенности последовательность точек на плоскости б) ... отрезков на прямой (отрезок = точка на плоскости) 7. Дана строка, удаляются по очереди все символы и даны запросы-отрезки, нужно после каждого удаления символа выводить список только что удаленных отрезков. а) Offline - max по времени на отрезке б) Разделяем каждый отрезок на O(logN) вершин дерева отрезков, а свежеудаленные вершин д.о. определяем за O(logN) 8. Изначально d[i]=0 для всех i = 0..10^9. Определим h : d[i]=h[i+1]-h[i], h[0]=0. Теперь есть запросы двух типов: увеличить d[i..j] на x. Найти первое i : h[i] >= q. а) Решение через динамическое д.о. б) Решение с сжатием координат и обычным д.о. Корневая эвристика. 1. Определение. Сравнение с деревом отрезков. 2. Запросы a[i] = x, Get(i, j) 3. Запросы a[i..j] += x, a[i..j] = x 4. Операции Del(i), Insert(i), Invert(l, r) 5. Переменная длина куска [sqrt(N)..2sqrt(N)] --- операции Split и Merge для куска. Задача о поиске K-й порядковой статистики. O(1, n) O(nlogn, logn^3) O(n^2, logn^2) O(n^3, 1) --------- День 02 --------- Дерево Фенвика. 1. Определение. Запросы Add и Get. Доказательство. 2. Зачем нужно: быстро работает, пишется, нет дополнительной памяти (именно поэтому и появилось) 3. Построение по массиву за O(n) с O(1) доп. памяти (2 подзадачи или a[i | (i + 1)] += a[i]) 4. Реализации Add, Get, Build 5. Исполльзование для min-а. Решение за O(logn^2). Решение за O(logn) с помощью двух деревьев. Многомерные деревья Фенвика и дерево отрезков. 1. Многомерное дерево фенвика (2D, 3D) 2. Формула включение-исключение с доказательством. Разбор задачи "prosto". 3. 2D-дерево отрезков для матрицы NxN. Запрос за O(logn^2). 4. 2D-дерево отрезков для N точек. O(nlogn) памяти и времени на предподсчет, запрос за O(logn^2). 5. Проблемы с модификацией на прямоугольнике. Пример, на котором стандартные идеи не работают. 6. Запросы Paint(x1, y1, x2, y2) и Color(x, y) за O(logn^2) 7. Подробная реализация 2D-NlogN дерева отрезков. 8. Динамическое 2D дерево отреков без сжатия координат O(n*logM^2), O(logM^2) --------- День 03 --------- Квадродерево. 1. Определение. Построение расчетверением или раздвоением на каждом уровне. 2. Запрос за O(n). Доказательство временной оценки. Задача Shaping Regions (Последовательные покраски прямоугольников, N штук) 1. Решение для полоски с heap-ом событий 2. Решение для полоски деревом отрезков 3. Решение для полоски покраской с конца системой непересекающихся множеств 4. Решение квадродеревом Декартово дерево (treap, "дуча", "курево") 1. Определение. Binary Search Tree по X, Heap по Y. 2. Доказательство единственности, если все X и Y различны, обоснование того что высота = O(logn). 3. Способы борьбы с одинаковыми X-ми (count, rand & 1) 4. Операции Add, Split 5. Операции Del, Merge 6. Реализация Add через Split & Merge 7. size[v]. Операции GetPos(x), GetX(pos) 8. Операции Min(i..j), Max(i..j), Sum(i..j) 9. Операция Invert(i..j) 10. Динамическая K-я порядковая статистика на отрезке Декартово дерево по неявному ключу 1. Определение. Создание. Hint, что параметр size можно не хранить. 2. Задачи, которые можно решать с помощью treap по неявному ключу. 3. Операции с массивом: Insert, Delete, Split, Merge, Invert(i..j), Sum(i..j), Min(i..j) Хэши 1. Хэштаблицы 2. Полиномиальный хэш 3. Отсутствие коллизий 4. Решение задачи: макс по длине общая подстрока двух строк за O(NlogN) ---------> Контрольные вопросы 1) Что плохого может произойти, если Y будут одинаковы ? 2) Почему нельзя сливать два произвольных декартовых дерева за logN ? -----------------------------> СНМ, LCA, RMQ --------- День 04 --------- СНМ 1. Определение. Задача, которую мы решаем. 2. Наивное решение: храним col[v] 3. Оптимайз #1: храним list_v[col], списки Merge-атся за O(1) 4. Оптимайз #2: когда делаем Join, перекрашиваем меньший по длине список, Итого: на Join в сумме уходит NlogN, Get работает за O(1). Краскал = Sort + E + VlogV (пример: веса от 1 до 1000) 5. Реализация через дерево: сжатие путей и Join меньшего к большему (по высоте или по размеру) 6. Доказательство оценки $O(\log^* n)$ (крутые ребра) Простые решения LCA и RMQ 1. RMQ за (O(nlogn), O(1)) (F[i,k] = Sum[i..i+2^k), [L..R]=[L..L+2^k)+(R-2^k..R]) 2. LCA за (O(nlogn), O(logn)) --- метод двоичных подъемов (поднять до одинак высоты, а потом еще раз поднять) 3. Решение задачи про подвешивание деревьев друг к другу и LCA за O(nlogn) в Offline и Online. 4. LCA за (O(n), O(logn)) --- лево-правый обход дерева + RMQ по временам входа на отрезке (или RMQ+-1 по высоте) 5. Отношение "? a предок b" за (O(n), O(1)) (tIn,tOut)[b] is in (tIn,tOut)[a] (hint про метод подъемов) 6. LCA Offline за O(n) (с СНМ) --------- День 05 --------- Сложные решения LCA и RMQ + алгоритм 4-х русских 1. Сведение RMQ к LCA за O(n) 2. Сведение LCA к RMQ+-1 за O(n) 3. Решение задача RMQ+-1 алгоритмом 4-х русских 4 Решение задача RMQ за (O(n), O(loglogn)) и за (O(nlog*n), O(log*n)) 5. Решение задачи про минимум на движущемся окошке за O(n + m) (Запросы: L++, R++, Min(L, R)) 6. Использование идеи 4-х русских для поиска наибольшей подпосл над алфавитом {a,b} за O(n^2 / logn^2) Функции на путях дерева. 1. Веса не меняются (а) Sum на пути O(n), LCA + O(1) (б) Min на пути O(nlogn), LCA + O(logn) (в) Min на пути offline O(n), LCA + O(logn) 2. Веса меняются (а) Покрытие дерева деревьями отрезков (предподсчет за O(n)) c запросом для пути Min, Max, Sum за O(logn^2) (б) Sum на пути O(n), LCA + RMQ (в) Min на пути, сведение к 2D дереву отрезков *(г) использование offline решения суммы в прямоугольнике для решения (1в) за (O(n), LCA + O(logn)). Решение задачек на предыдущие темы: 1. Сумма всех X : L <= X <= R, Add(x), Del(x) в Offline деревом отрезков 2. В дереве в каждой вершине записано число, сказать для каждого поддерева, сколько различных чисел (а) решение за O(NlogN^2) (сливаем декартовы деревья), за O(NlogN) (сливаем хэш таблицы) (б) решение за O(n) запросов LCA + O(n) DP по поддереву. 3. Дерево отрезков декартовых деревьев для решение задачи о Sum(x[i] : l <= i <= r, L <= x[i] <= R). Минусы по сравнению с 2D деревом отрезков на N точках. -----------------------------> Строки --------- День 06 --------- Суффиксный массив 1. Определение, циклические сдвиги, суффиксы, получение одного из другого и наоборот. 2. Построение за O(n^2) цифровой сортировкой 3. Построение за O(nlogn) *4. Построение LCP за O(nlogn) по ходу с помощью RMQ 5. Построение LCP за O(n) - алгоритм Касаи. 6. Проблемы алгоритма Касаи в случае цикл сдвигов для периодичных строк, 2 метода решения. 7. Сравенение строк на неравенство за O(logn) 8. Построение суфф массива хэшами за O(nlogn^2) Решение задач с помощью суфф массива 1. Поиск подстроки в тексте за O(mlogn) 2. Поиск подстроки в тексте за O(m + logn) 3. Поиск наибольшей общей подстроки k строк (Окошко, которое должно содержать все числа от 1 до k с поиском min-а за O(1)) 4. Число различных подстрок. Суффиксное дерево, сжатое суффиксное дерево 1. Определение, наивное построение за O(n^2). 2. Методы хранение ребер - массив, список, set, hash, бор 3. Чит-метод хранения ребер для несжатого (для каждой вершины храним или 1 ребро, или ссылку на массив) 4. Сжатое суфф дерево. Построение за (T=O(n^2), M=O(n) <-- списками ребер) 5. Построение cуфф дерева по суфф массиву. 6. Построение суфф массива по суфф дереву. Решение задач с помощью суфф. дерева и то, как их можно решать хэшами 1. Количество различных подстрок. (Хэшами адекватно не решается) 2. Общая подстрока (Хэшами за O(nlogn)) 3. Макс подпалиндром. (Хэшами за O(n) <-- без бинпоиска по длине, только Len++) 4. Макс общий подпалиндром (Хэшами за O(nlogn)) --------- День 07 --------- Алгоритм Укконена 1. Реализация за O(n^2) 2. Реализация за O(n) без док-ва 2-х утверждений 3. Док-во, почему работает за O(n) 4. Док-во 2-х утверждений 5. Подробности реализации, проблемы с корнем, проблемы с отложенными записями Prefix функция, автоматы и линейные системы 1. КМП 2. Автоматы, автомат для КМП 3. Задача про мартышек, пишущих войну и мир, формула через Prefix-функцию 4. Решение вероятностной задачи про мартышек Гауссом за O(n^3) 5. Решение вероятностной задачи про мартышек руками за линейное время (с делением) 6. Решение вероятностной задачи про мартышек Методом итераций за O(n*E*logM) Ахо-Корасик 1. Ахо-Корасик 2. Подробности реализации (suf[v], end[v], фиктивный корень, автомат, ) --------- День 08 --------- Суффиксный автомат 1. Алгоритм (раздать распечатки) 2. Предпосылка к построению, одинаковые состояния в несжатом суф дереве. 3. Правые контексты. 4. Суффикс функция, ее смысл. 5. Что происходит при добавлении смивола 'a' в конец. Появление z и z'. 6. Раздвоение врешины, новые ребра, суф ссылки. 7. Линейность времени работы первого while-а (инвариант = Len) 8. Линейность времени работы второго while-а (инвариант = длина пути по суф ссылкам) 9. Построение суф дерева по суф автомату. 10. Построение суф автомата по суф дереву. Дополнение про суф массивы и строки *1. Суффиксный массив за O(n) - алгоритм Кярккайнена-Сандерса 2. Разбиение строки на простые *3. Алгоритм Дюваля = поиск min lex циклического сдвига за O(n) с помощью разбиения на простые. -----------------------------> Потоки --------- День 09 --------- Поток. Основы. 1. Поток, Разрез, Дополняющий путь, Насыщенные и ненасыщенные ребра. 2. Пример потока на примере поиска двух непересекающихся по ребрам путей. 3. F(S, T) <= C(S, T) 4. Теорема Форда-Фалкерсона. max F = min C 5. Алгоритм Форда-Фалкерсона поиска потока и разреза. Работа за O(flow), проблемы с real capacities. 6. Хранение графа списком ребер (e, e^1) 7. Декомпозиция потока (dfs-ом и bfs-ом) (на примере задачи о поиске K путей) 8. Вершинные поток и разрез (раздваивание вершин) 9. Поток с несколькими стоками и истоками (сливание вершин) 10. Поиск разреза мин стоимости Поток. Алгоритмы. 1. Лемма о том, что после bfs-а расстояния до вершин не убывают. 2. Алгоритм Эдмондса-Карпа за O(VE^2) c док-вом. 3. Алгоритм Масштабирования за O(E^2logMax) c док-вом. Можно писать и bfs-ом и dfs-ом. Реализация с k--. 4. Градиентный метод (Binaray Search + dfs) за O(E^2log^2Max) 5. Алгоритм Диницы за O(V^2E) 6. Скрещивание с масштабированием за O(VElogMax) *7. Примеры для масштабирования, масштабирования с проталкиванием max, Эдмондса-Карпа Паросочетания 1. Поиск паросочетаний, мин контр мн-во, макс независимое мн-во 2. Алгоритм Куна (с док-вом через симметрическую разность паросочетаний) 3. Поиск паросочетаний через потоки, алгоритм Хопкрофта-Карпа и его док-во через сим разность. 4. Доминошки и покрытие грида полосками 5. Покрытия графа мин числом цепей (раздвоим вершины) 6. Поиск мин по весу контролирующего мн-ва и макс по весу незвисимого мн-ва. --------- День 10 --------- MinCost-MaxFlow 1. Алгоритм поиска Ford-Belman-ом 2. Теорема об оптимальности полученного результата. Неполиномиальность алгоритма. 3. Решение задачи о поиске min (max) по сум весу ребер паросочетания 4. Использования Дейкстры для поиска пути (потенциалы Джонсона) 5. Использование детского Ford-Belman-а 6. Использование потенциалов Джонсона для поиска пути между всеми парами вершин в произвольном графе за O(VElogV) Венгерка 1. Постановка задачи. Вычетание из строки, столбца. 2. Собственно алгоритм. Наращивание дерева нулевых путей за O(n^2) 3. Интерпретация через Дейкстру. Задачи на потоки (обычные и mincost) и паросочетания 1. Поток с нижними и верхними пропускными способностями на ребрах (через mincost) 2. Восстановление турнирной таблицы по итоговым очкам (не бывает ничей) 3. Удаление графа за min стоимость 4. Покраска грида с дырками полосками (Сакура и статистика, 1548 с тимуса) Потоки и паросочетание - окончание 1. Алгоритм Малхотры-Кумара-Махешвари 2. Построение паросочетания : max вес ребра ---> min за O(VE) (без бинпоиска) 3. Теорема Холла Разбор задач model alliance -----------------------------> Игры --------- День 11 --------- Симметричные игры на графах 1. На ациклических графах (DP за O(E)) 2. На цикличных графах (Ретроанализ за O(E)) 3. В обычной DP и ретроанализе поиск самого быстрого выиграша и самого долгого проигрыша. Функция Гранди 1. Функция Гранди. Определения через mex, (mex = 0) <=> LOSE. 2. Прямая сумма игр, сила xor-а. 3. Док-во того, что mex(A+B)=mex(A)^mex(B) табличкой от Андрея Лопатина. 4. Эквивалентность, 2 определения, любой граф G ~= ниму a* Примеры 1. Шоколадка (решение за O(n^3)) 2. Шоколадка + нельзя делить попалам 3. Ним + кучку можно делить пополам (= то же самое, что и Ним) 4. Ним + кучку можно делить на произвольное число слагаемых 5. Штирлиц, Мюллер и очередь 6. Hacking Bush Теория Смита 1. Алгоритм Смита. 2. Реализация алгоритма за O(VE) 3. Доказательство... --------- День 12 --------- Долги *(г) использование offline решения суммы в прямоугольнике для решения (1в) за (O(n), LCA + O(logn)). *3. Алгоритм Дюваля = поиск min lex циклического сдвига за O(n) с помощью разбиения на простые. * Лекция по оптимизации. * Все фишки рассказанные на этой лекции НЕ имеют смысла, без закрепления на практике. Отсечения в переборе. 1. По глубине (пример с 42-машиной) 2. По ответу (пример с AB-отсечением) 3. Хэширование (работает всегда) 4. Хэширование только нескольких уровней. 5. Идея 4-х русских : предподсчет для нескольких последних. Неасимптотические оптимизации. 1. Умножение матриц, транспонирование матрицы 2. Сжатие памяти до линейной в динамике 3. Восстановление ответа в динамике без хранения ссылок назад (по таблице функции) 4. На примере timus/1029-Ministry сведение (T=n^2, M=n^2) решения к O(T=n^2logn,M=n) решению. 5. Меньше параметров передавать в рекурсию (на примере потока, дерева отрезков, -10%) 6. Сила random_shuffle (Форд-Белман, точки по разные стороны прямой) 7. Оптимизация путем предпроверки за O(1). #8. Сила C++: while (s[i + k] == s[j + k]) k++ --> while (*s1++ == *s2++) k++ #9. Оптимизация путем удаления кода. Оптимизация длины кода. 1. Процедуры (+ гибкость, - длина) 2. Циклы for (- ошибки, - длина) 3. Следите, чтобы длина кода была минимально возможной: меньше случаев, меньше кусков одинакового кода Умножение чисел Карацубой 1. Хранение длинных чисел 2. Выделение памяти "руками" 3. Переносы в конце 4. Короткий код Задача про 2^N + 2^K со сборов. 1. Решение за нужное время 2. Разные предподсчеты 3. Избавление от рекурсии -----------------------------> Долги *7. Реализация запроса += снизу. *4. Построение LCP за O(nlogn) по ходу с помощью RMQ *1. Суффиксный массив за O(n) - алгоритм Кярккайнена-Сандерса *7. Примеры для масштабирования, масштабирования с проталкиванием max, Эдмондса-Карпа -----------------------------> Пока не из плана 2. Теормы Карзанова, первая и вторая. 3. DP по подмн-вам (поиск парсоча в произвольном графе, гамильтонова цикла и т.д.) 4. DP по профилю 5. DP по скошенному профилю +6. Хэширование в переборе и DP по профилю 8. Теорема Дилворта и максимальная антицепь.