Параллель B'

Страница на алгокоде

1. Сортировки

Анализ времени и памяти

• O-нотация light version
• Работа со временем и памятью

Квадратичные сортировки

• Сортировка пузырьком
• Сортировка выбором
• Сортировка вставками

Сортировки за $n\log{n}$

• Сортировка слиянием
• Быстрая сортировка

Другие сортировки

• Сортировка подсчетом

Связанные задачи

• Количество инверсий
• K-я порядковая статистика

2. Поиски за $O(\log(n))$

Бинарный поиск

• Бинарный поиск
• Бинарный поиск с вещественными числами
• Бинарный поиск по ответу
• Бинарный поиск по производной
• Бинарный поиск для нахождения подходящей пары

Тернарный поиск

• Тернарный поиск

3. Графы

• Основные понятия теории графов
• Хранение графа
• Обходы графа и их применения

4. Динамическое программирование

• Основы ДП
• План ДП
• Одномерное ДП
• Двумерное ДП
• Восстановление ответа: через массив динамики и через массив предков.
• Ленивая динамика.
• Рюкзак
• Динамика по префиксу и значению последнего элемента
• НВП
• НОП

5. С++ и базовые структуры данных

Базовые структуры данных

• Vector
• Стек
• Очередь
• Дек
• Куча(Очередь с приоритетами)
• Списки

С++

• Итератор
• Multiset
• Set
• Map
• Ускорение ввода-вывода
• Полезные встроенные функции
• pbds
• Бинпоиски
• Подводные камни
• UB

6. Корневая декомпозиция

• Корневая декомпозиция
• Корневая декомпозиция на массиве
• Корневая на строках
• Корневая в задачах на графы
• Корневая по запросам
• Алгоритм Мо
• Подбор констант

7. Математика

• Базовая математика
• Теория чисел
• Комбинаторика
• Теория вероятностей
• Матрицы

8. Кратчайшие пути

• BFS
• 0-1 BFS
• 1-k BFS
• Алгоритм Форда-Беллмана
• Алгоритм Дейкстры

9. СНМ и остовные деревья

• СНМ

Остовные деревья

• Лемма о безопасном ребре
• Алгоритм Краскала
• Алгоритм Прима

10. LCA

Вспомогательная структура

• Sparse Table

LCA

• LCA
• Эйлеров обход

Методы

• Двоичные подъемы
• Решение с помощью Эйлерова обхода

11. Геометрия, примитивы

• Векторы
• Прямые
• Отрезки
• Окружности

12. Динамическое программирование

Повторение для подзабывших

• Основы ДП
• План ДП
• Одномерное ДП
• Двумерное ДП
• Восстановление ответа: через массив динамики и через массив предков.
• Ленивая динамика.
• Рюкзак
• Динамика по префиксу и значению последнего элемента
• НВП
• НОП

Новое

• Паросочетание
• ДП по поддеревьям
• Маска
• Битовые операции
• ДП по подмножествам
• ДП по профилю
• Перебор всех подмасок данной маски

13. Хеши

• Полиномиальное хеширование строк
• Хеширование множеств (с точностью до перестановки
• Хеширование матриц
• Хеш-таблицы (открытый ключ)
• Хеш-таблицы (цепочки)
• Хеширование корневых деревьев