- Ya 2.0
- Линейный поиск
- Множества
- Сортировка подсчетом
- Словари
- Префиксные суммы
- Два указателя
- Бинарный поиск
- Сортировка событий to-do
- Деревья
- Ya 3.0
- ITMO Academy codeforces
Пусть дан массив из N элементов таких, что их разброс невелик. Обычная сортировка займет ~O(NLogN)
Однако, если разброс элементов небольшой, проще сосчитать кол-во каждого элемента, а затем восстановить массив
Подсчет чего-либо на отрезке, быстрый ответ на запрос операции на отрезке
Много задач, формата 2 массива, станцуйте с бубном и т.д. Обычно 2 указателя там очевидны
Должно выполнять 2 свойвства
- если отрезок [L,R] хороший, то любой вложенный в него отрезок также хороший
- если отрезок [L,R] хороший, то любой отрезок, который его содержит также хороший
- Мы должны уметь пересчитывать функцию (проверять хороший отрезок или плохой), при смещении левой или правой границы вправо.
Пример кода:
L = 0
for R = 0..n-1
add(a[R])
while not good():
remove(a[L])
L++Если при пересчете функции нам требуется иметь доступ не только к крайним элементам: например мы считаем разброс между min и max элементом в окне, удаление/прибавление элемента не ограничивается просмотром крайних.
В таком случае, можно сделать очередь на 2-ух стеках, в правом-левом стеке хранить необходимые значения (например хранить в стеке будет храниться максимум, тогда при удалении/добавлении элемента, пересчет функии будет ~O(1))
Абстрактная схема такой очереди:
Главный тригер к бинарке - монотонная функция 2 видов. Делеие на хорошую и плохую часть, с помощью бинарки удобно искать этот разрыв за ~O(LogN)
Структура бинпоиска не меняется, в общем виде это:
L := 0 // Левая граница
// крутые математики, сразу могут определить при каком R функция будет true, но д - думать, д - дебил, делаем так
R := 1
for !good(R, ...) {
R *= 2
}
for R != L + 1 {
MID := (L + R) / 2
if good(MID) {
R = MID
} else {
L = MID
}
}
func good(X int, ...) bool {
res := // проверяем, удовлетворению условию при X
return res
}Так же бинарка, однако достаточную близость L и R обрабатываем 2 способами:
// 1 eps - точность
eps := 1e-6
for (R - L > eps)
// 2 через итерации
for (i := 0; i != 100; i++)
// 100 итераций - 2^100, вообщем ответ получим с максимальной точностью, у нас на итерации ~60-той, уже будут соседние числа в float64Задачи двух видов:
Внешняя функцию, например min(...) можно заменить на ограничение сверху, а это ограничение подбирать бинаркой, получим
Само выражение
Пускай у нас есть какое-то множество, нам нужно выбрать подмножество, обладающее какими-то свойствами, и в этом подмножестве нужно максимизировать/минимизировать среднее арифметическое элементов.
Делаем прием из прошлого блока, подбираем ограничение функции и преобразовываем:
Далее применим префиксные суммы:
TO-DO Поиск K элемента https://codeforces.com/edu/course/2/lesson/6/5
TO-DO
Задача на правильную скобочную последовательность с различными скобками (например ([)] - не получится обработать префиксной суммой). При добавлении новой скобки, нам не требуется пробегаться по всем скобкам в массиве, мы можем обработывать лишь скобки на вершине стека, каждая скобка будет обработа лишь 1 раз
Задача на преобразование в постфиксную запись, опять тот же подход.
Иными словами, признаком стека может являться некая вложенность, или возможность поэтапно обрабатывать данные. Строго признака нет, от задаче к задаче.
Задача о поиске ближайшего меньшего справа
Храним в стеке значения элементов массива. Тогда, обработаем число x:
- Поочередно рассматриваем элементы на вершине стека, если
stack.top()> x, выбрасываем из стека - Если
stack.top()< x, то дальнейшее рассмотрение не имеет смысла, ведь такой элемент, был бы уже обработан заранее.
Помимо стандарной реализации очереди через буферы и бакеты, имеет место быть реализация, через кольцевой буфер:
Структура, позволяющая получить min/max элемента за ~O(LogN)
- add(x) - Добавить элемент
- pop() - удалить min/max
Каждый ребенок меньше/больше его родителя. Куча заполняется по слоям, из-за этого её хранение в массиве компактно и удобно.
Добавление в кучу - элемент добавляется в конец очереди и просеивается вверх.
Удаление элемента - Элемент в вершине кучи заменяется последним элементом кучи, после чего идет просеивание вниз.
Просеивание вниз - элемент в узле меняется с меньшим/большим из детей.
Если при замене элемента, удалить последний, после просеивания, можно свести все узлы к ситуации: 0 или 2 детей. (свап с неудленным элементом в любом случае не требуется)
Синхронизированная куча - Можно хранить hashMap, {значение:индекс в массиве кучи}, таким образом, изменять элемент в куче и просеивать его. TO-DO
Задача LRU Кеш: Хранить в кеше
- Словарь - хранимые в кеши элементы
- Очередь с приоритетами - хранит приоритеты элементов, позволяет выкидывать самые старые элементы
Задача о медиане в окне: Есть массив из n элементов, нужно найти медиану. Например: {1, 9, 9321} - медиана 9.
Поддерживаем 2 кучи, на максимум и на минимум. Ответом будет - минимальный элемент в 2-ой куче.
Пирамидальная сортировка: Мы берем
При рекрсивных вычислениях, мы повторно запускаем рекурсию от ранее вычисленных значениях.
Пример на числах фибоначи:
Рекурсия с мемоизацией: Убираем рекурсию в пользу цикла.
Классические задачи одномерного ДП: максимизировать, минимизировать, посчитать кол-во вариаций. Разбиваем задачи на более маленькие, рассматриваем все варианты.
TO-DO задача в конце на представление числа
Одномерное ДП, но сводящееся к таблице. Типовые задачи на поле: дойти от первой клетки до последний макс/мин при этом параметр.
Аналог писать ифы для сдвига по нескольким направлениям - писать подобные массивы
var dx = []int{1, 0, 0, -1}
var dy = []int{0, 1, -1, 0}
i, j = i + dx[k], j + dy[k]Задача про черепашку без долгов: 2 параметра - минимальные долги, максимальная прибль. В данном случае минимальные долги, можно подобрать бинарным поиском, если хватит x монет на старте, то x+1 тоже хватит.
Задача о наибольшей общец подпоследовательноти: Формируем таблицу первое/второе слово, dp[i][j] = НОП далее придерживаемся правил:
- X == Y - dp[i][j]++, очевидно мы берем 2 новые буквы в ответ
- X != Y - dp[i][j] = max(dp[i-1][j], dp[i][j-1]) - в этих строках/столбцах мы уже рассмотрели всевозможные комбинации новых букв. Обе в ответ мы не берем
Задача о редакционном расстоянии левенштайна: Есть 2 слова, операции вставки, изменения, удаления. За наименьшее количество операций преобразовать слово A -> B. Строим таблицу, сверху/сбоку слова A/B. Если буквы совпадают +0, если отличаются то минимум от +1 с трех сторон. В dp[i][j] храним минимум изменений.
Задача о обедах и купонах: Массив цен на N дней вперед. При покупке на более 100р, получаем купон на бесплатный обед. Посчитать минимальные затраты. Таблица дни/купоны.
Задача про правильную скобочную последовательность: Удалить минимальное количество скобок, что бы последовательность стала правильной.
Последовательность формируется как S =
Тогда, при несоответствующих скобках: [...), рассматриваем варинт с [..](..), просто перебирая границу i: [L, i][i+1, R]. Остается 1 неучтенный случай, когда ((...)). Тут следует искать вложенность, в итоге:
if s[L] соответствует s[R] {
dp[L][R] = dp[L+1][R-1]
}
for i = L+1; i <= R-1; i++ {
dp[L][R] = min(dp[L][R], dp[L][i] + dp[i+1][R])
}
сложность ~O(N^3)
Задача про упаковку символов dp[i][j] = кол-во символов в которые можно упаковать + всегда при [L,R] надо проверить на разбитие на делители, мало ли можно свернуть TO-DO.
Обход в глубину нужен для понимания структуры графа!
Представление графов в виде: * таблица смежности * список ребер * списки смежности
Приоритет за списокои смежности.
При обходе в глубину путь обхода в любой момент времени - линия. Пример обхода в глубину:
func dfs(g [][]int, visited []bool, now int) {
visited[now] = true
for v := range g[now] {
if !visited[v] {
dfs(g, visited, v)
}
}
}Задача поиска циклов: В графе есть цикл, если мы повторно вышли к вершине, находящийся в активном пути dfs.
- Белый - непосещенные вершины
- Серый - активная вершине, присутствующая в стеке dfs
- Черный - обработанная вершина.
Если вершина черная - мы уже обработали всех её детей.
Задача поиска компонент связанности: После dfs получаем компоненту связанности.
Задача о двудольном графе: раскраска в 2 цвета, делаем обычный обход поочередно крася вершины в 2 цвета. Если мы полностью обошли граф, и не встретили соседних вершин с одинаковыми цветами - граф двудольный.
Топологическая сортировка: после выхода из вершины - мы обработали всех её детей, а значит и её саму. Добавляем в отсортированный массив.
Реализация через дек:
while (!q.empty()) {
int layer = q.size();
for (int i = 0; i != layer; i++) {
int vertex = q.front();
for (auto x : graph[vertex]) {
if (!visited[x]) {
q.push_back(x);
}
}
}
}Реализация через массив. Индекс в массиве - шаг bfs.
Путь bfs восстанавливается по дополнительному массиву предков
Задача о ребрах и вершинах на кратчайших путях: При обходе
Граф состояний: TO-DO.
Кратчайший путь в 0-1 графе:
- Дек: при 0-ребре добавляем вершину в начало дека.
- Массив: TO-DO
Кратчайший путь в 0-k графе: TO-DO реализация на массиве сведется к дейкстре.
Задача о поиске подстроки в строке решается 2 основными способами:
- Предпроцессинг образа (Z-func, префиксные функции)
- Предпроцессинг текста (суффиксное дерево, массив, автомат)
Z-функцие строки s называется массив соответствующей длины, где z[i] = длина наибольшего префикса строки s и её суффикса s[i..n]. Обычно полагают z[0]=0
Задача о поиске вхождений: есть строка p, t. Нужно найти все вхождения p в t:
- строим строку
p + $ + t - считаем Z-функцию полученной строки
-
z[i] = p
$\Longleftrightarrow$ p = t[i .. i + (len(p) - 1)]
Задача периода строки: если z[i] + i == n && len(z) % i == 0.
Задача о строке с одной ошибкой: 2 прохода в стороны z-funcом, ищем нужные индексы с 2-ух сторон.
Задача о кол-ве уникальных подстрок:
Идем справо-налево добавляя по одной букве. При добавлении новой буквы, новые отрезки будут префиксами различной длинны. Считаем Z-func от нашей текущей строки. Тогда
Z-algo, за
Делаем 2 индекса l, r. Бежим по строке с 1-ой (z[0] = 0) позиции. l и r будут обозначать совпадение префикса и подстроки с i-ого индекса так, что r - максимально.
Далее рассматриваем 2 случая:
-
i < r: Отрезок [l, r] совпадает с префиксом, соответственно s[i.. r] == s[i-l..r-l]. Тогда можем воспользоваться ранее вычисленной z-func:
z[i] = min(r-i+1, z[i-l]). При z[i-l] >= r-i+1 , мы не знаем что находится за границей r, в этом случае нам надо идти вручную поэлементно и проверять. -
i > r: Идем вручную и проверяем, потом обновим r.
Эти 2 случая можно склеить в один, получим подобное:
Здесь l, r - ПОЛУИНТЕРВАЛ!
var l, r int
for i := 1; i != len(z); i++ {
if i < r {
z[i] = min(r-i, z[i-l])
}
for z[i] + i < len(z) && s[i + z[i]] == s[z[i]] {
z[i]++
}
if r < i + z[i] {
r = i + z[i]
l = i
}
}
Базово - представляем из себя дерево, позволяющее выполнять следующие операции за
- set(i, v) - присвоить элемету i значение v
- calc(l, r) - посчитать операцию calc на отрезке Операция обязанна быть ассоциативной
Очень похоже на префиксные суммы, но с возможностью пересчета за логарифм
set(i, v) - изменяется элемент массив (до которого дошли рекурсией), и по цепочке вверх идет пересчет элементов, за счет ассоциативности функции
calc(l, r) - посчитаить функцию от отрезка [L, R]. Каждый элемент в дереве - является результатом функции от подотрезка всего массива, выглядит это все следующим образом:
Соответственно, если
Пример:
void set(int i, int v, int x, int lx, int rx) {
// i, v - параметры фукнции
// x, lx, rx - номер, левая-правая граница узла в дереве(идем рекурсивно)
if (rx == lx + 1) {
// случай когда дошли до последнего слоя, дальше углубляться нет смысла
// С учетом set'а, в данном блоке мы окажемся, если нашли искомый элемент - можем менять его и выходить из рекурсии
array[x] = v; // тут важно понимать, array - массив всех узлов, последним слоем которого является сам массив, над которым идет надстройка
// lx, rx - индексы за что отвечает узел в массиве значений. x - индекс узла!, это разные вещи!
// например первый элемент в последнем слое будет иметь: lx = 0; rx = 1(полуинтервал), x = 7.
return;
}
// 2*x+1 - левый ребенок, 2*x+2 - правый.
mid = (lx + rx)/2;
if (i < lx) {
set(i, v, 2*x+1, lx, mid);
} else {
set(i, v, 2*x+2, mid, rx);
}
// изменив элемент в дереве, мы пересчитываем все что выше него!
array[x] = op_calc(array[2*x+1], array[2*x+2]); // op_calc - сама ассоциативная функция от 2-ух элементов
return;
}
Type calc(int l, int r, int x, int lx, int rx) {
// l, r - полуинтервал
if (rx <= l || lx >= r) { // полностью промахнулись
return NEUTRAL
}
if (lx >= l && rx <= r) { // полностью попали
return array[x]
}
int mid = (lx + rx)/2;
Type left = calc(l, r, 2*x+1, lx, mid);
Type right = calc(l, r, 2*x+2, mid, rx);
return op_calc(left, right);
}Инициализация дерева:
clacc segtree {
public:
segtree(int n, vector<Type>& origin) {
init(n);
build(0, 0, size, origin);
}
calc(int l, int r) {...} // публичные методы calc && set
set(int i, int v) {...}
private:
vector<Type> array; // все узлы дерева
int size; // размер основания дерева
// основание дерева всегда степерь 2-ки, так тупо удобнее, дерево похоже на бинарное
void init(int n) { // n - размер искходного массива
size = 1;
while (size < n) {
size *= 2;
}
array.assign(2*size-1, START_ELEMENT); // 2*size-1 - количество узлов в дереве
}
void build(int x, int lx, int rx, vector<Type>& origin) { // origin - массив входных данных
// ну тут просто dfs
if (rx == lx + 1) {
if (lx < origin.size()) {
// основание дерева - степень 2-ки, значит у нас будут *неиспользованые* элементы, lx - индекс в массиве, надо проверить что мы не в таких элементах
array[x] = origin[lx];
return;
}
}
int mid = (lx + rx)/2;
build(2*x+1, lx, mid, origin);
build(2*x+2, mid, rx, origin);
array[x] = op_calc(array[2*x+1], array[2*x+2])
}
calc(int l, int r, int x, int lx, int rx) {...}
set...
};Примеры задач:
Любая, где мы можем считать функцию ассоциативно, проще - зная значения на 2-ух отрезков, можем пересчитать её на общем
Задача о отрезке с максимальной суммой: У нас есть 2 отрезка, что в них нужно хранить, что бы при объединении, можно было пересчитать максимальную сумму?
- сегмент с максимальной суммой, тогда при объединении
maxSeg = max(Seg1, Seg2) - preff, suff - храня просто сегменты, мы не учитываем отрезке, получаемые непосредственно в процессе объединения. Тогда:
maxSeg = max(Seg1, Seg2, suff1 + preff2)
Как пересчитывать preff и suff? preff = max(preff1, sum1 + preff2), с suff - аналогично
K - единица. Просто дерево с операциями
- set(i, v) -
$v \in {0, 1}$ - find(k) - найти индекс k-ой единицы
Абстрактно - есть массив плохих/хороших элементов, можем менять плохо на хороший и обратно. Найти индекс k-го хорошоге элемента, используется часто
Первый больше X, Просто дерево на максимум
Инверсии, Вложенные/Пересекающиеся отрезки - codeforces
Алгоритм манакера. Дерево палиндромов за ~O(N) 5 leetcode