algorithms

Road Map (алгоритмы для проработки)

Solving Map

Алгоритмы

Теория чисел

• Бинарное возведение в степень
• Примитивы
• MODINT
• Длинная арифметика, вариант 2
• Решето Эратосфена | с линейным временем
• Диофантовы уравнения с двумя неизвестными
• Код Грея
• Алгоритм BPSW - проверка числа на простоту
• Факторизация числа
• Делители числа + факторизация
• Вычисление факториала по модулю
• Нахождение степени делителя факториала
• Медиана онлайн
• Перебор всех подмасок данной маски

Вычислительная геометрия

• База по вычислительной геометрии

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

• Теория и примеры
• Динамика по профилю. Задача "Паркет"
• Динамика на деревьях: Нахождение размеров поддеревьев (снизу вверх), Нахождение глубин вершин (сверху вниз)

Графовые алгоритмы

• Общие понятия
• Обход в ширину (не рекурсивный)
• Поиск компонент связности
• Поиск мостов (offline)
• Алгоритм Дейкстры
• Топологическая сортировка графа, алгоритм Кана (минимальная лексикографическая сортировка)
• Алгоритм Флойда - Уоршелла (нахождения кратчайших путей между всеми парами вершин)
• Алгоритм Форда-Беллмана
• Минимальный остов Алгоритм Крускала, Алгоритм Прима, Алгоритм Крускала с DSU
• ms-sr | ms-ss | sr-ms | ss-ms
• Поиск истоков и стоков
• Транзитивное замыкание
• read_ss | read_ss_from_ms
• Поиск циклов отрицательного веса

компоненты связности

• Поиск компонент сильной связности, построение конденсации графа за O(N+M)

потоки

• Нахождение максимального потока. Алгоритм Диница
• Нахождение максимального потока.
• Поток минимальной стоимости (min-cost-flow)

наименьший общий предок (LCA)

• Наименьший общий предок. Алгоритм Тарьяна (офлайн режим)

Строковые алгоритмы

• Z функция
• Префикс-функция
• Нахождение всех подпалиндромов. Алгоритм Манакера
• Редакционное растояние. Алгоритмы: Левенштейна, Хэмминга, Дамеруа-Левенштейна, Джаро-Винклера
• Декомпозиция Линдона. Алгоритм Дюваля. Нахождение наименьшего циклического сдвига

Алгоритмы на последовательностях

• Нахождение наидлиннейшей возрастающей подпоследовательности
• K-ая порядковая статистика

Структуры

• Дерево отрезков
• Дерево Фенвика
• DSU Система непересекающихся множеств
• Нахождение минимума в стеке и в очереди за O(1)
• Sqrt-декомпозиция
• Sparse Table
• Декартово дерево (treap), Декартово дерево по неявному ключу
• 2-SAT

Сортировка

• Общие понятия
• Сортировка выбором
• Сортировка слиянием, подсчет инверсий
• Сортировка пузырьком

Комбинаторика

• Размещения, перестановки, сочетания
• Правильные скобочные последовательности

Шахматы

• pq-конь

Битовые операции

• Битовые операции
• Динамика по битовым маскам

Другие техники

• Meet-in-the-middle
• Полезные функции GCC

Прочее

• RobotPath
• Спираль
• Задача Иосифа
• Мажорирующий элемент
• SuperMemo
• Быстрый ввод/вывод

Эвристические алгоритмы

• Алгоритм отжига

Языки программирования

• C++
• • Базовые типы данных
• • Структуры данных
• • Массивы
• • Vector

C++

• Новый возможности в С++17
• Константы
• Умные указатели

C++ STL

• Контейнеры STL
  • Vector
  • Вставляем в map эффективно и по условию (try_emplace)
  • Семантика подсказок для вставки элементов std::map::insert
  • Эффективно изменяем ключи элементов std::map extract
  • Применяем контейнер std::unordered_map для пользовательских типов
  • Отсеиваем повторяющиеся слова в пользовательском вводе (set)
  • Подсчитываем частоту встречаемости слов map
  • Подсчет предложений и вывод в порядке длины, multimap
  • Список дел с приоритетом
• Итераторы
  • Создание итерабельного диапазона данных
  • Совместимость собственного итерабельного диапазона данных с STL
  • Заполнения обобщенных структур данных
  • Числа Фибоначчи с итераторами
  • Перебор в обратную сторону с применением обратных адаптеров

Прочее

• TCP vs UDP