Параллель B'

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

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

Видео по теме

• Лекция про ДП от Саши Гришутина
• Динамическое программирование от Павла Маврина
• НОП
• НВП
• Рюкзак

5. Линейные алгоритмы

Видео

лекция 2021-2022

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

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

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

С++

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

3. Графы и стресс-тестирование

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

Видео по теме

• Лекция от 2021 года
• Важное о графах
• DFS

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

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

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

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

• Тернарный поиск
• Вложенные тернарные поиски

Видео по теме

• Лекция от 2021 года
• Бинарный поиск
• Вещественный бинарный поиск
• Тернарный поиск

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

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

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

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

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

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

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

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

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

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

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

Видео по теме

• Лекция 2021 года