Tinkoff Generation

Алгоритмы. Параллель С. План занятий

Занятие 1. Оценка времени работы программы

  1. O-нотация. Математическое определение. Замечание о том, что для конкретных ограничений алгоритм, более быстрый асимптотически, не всегда действительно быстрее.

    • Сколько операций в секунду способен обрабатывать компьютер (порядка \(10^8\)).

  2. Навык по ограничениям в задаче понять, решения каких асимптотик зайдут, а какие нет.

  3. Квадратичные сортировки: пузырьком, выбором, вставками.Сортировка подсчетом.

Занятие 2. Бинарный Поиск #1

  1. Бинарный поиск. Понимание того, что для бинпоиска нужны:

    • Монотонная функция.

    • Инвариант для границ бинпоиска.

  2. Вещественный бинарный поиск. Замечание о том, что лучше всего устанавливать константное число итераций.

  3. Утверждение о том, что непрерывная функция, принимающая в одной точке неположительное значение, а в другой – неотрицательное, имеет точку, в которой принимает нулевое значение. Применение бинпоиска для поиска этой точки.

Занятие 3. Теория чисел

  1. НОД и НОК.

  2. Алгоритм Евклида.

  3. Расширенный алгоритм Евклида.

  4. Нахождение всех делителей числа за \(O(\sqrt n)\).

  5. Факторизация за \(O(\sqrt n)\).

  6. Быстрое возведение в степень.

  7. Решето Эратосфена за \(O(n \log \log n)\).

  8. Применение решета Эратосфена для факторизации чисел за \(O(\log n)\) с предпосчетом за \(O(n)\).

Занятие 4. C++

  1. Ускорение ввода/вывода

  2. cppreference - наше всё

  3. Работа с файлами

  4. Встроенный НОК и НОД

    • min_element, max_element, nth_element

    • merge, sort, stable_sort

    • fill, copy, (C: memset, memcpy)

    • reverse, rotate

    • unique

    • lower_bound, upper_bound, binary_search

    • next_permutation, prev_permutation

    • partial_sum

  5. Компараторы

  6. vector, set, map, priority_queue

Занятие 5. Динамическое программирование #1

  1. Основы ДП. Кузнечик + черепашка (подсчет количества путей, подсчет минимального/максимального пути).

    • Формализуем сказанное: что нужно для ДП?

  2. Какое состояние ДП? Что такое ответ для состояния (целевая функция)?

  3. Какие начальные значения?

  4. Как пересчитывать значения?

  5. Какой должен быть порядок обхода, чтобы все значения, требуемые при пересчете, уже были подсчитаны?

  6. Как получить ответ?

Занятие 6. Динамическое программирование #2

  1. Восстановление ответа: через массив динамики и через массив предков.

  2. Рюкзак. Взвешенный/невзвешенный. Число предметов ограничено/не ограничено.

    • Реализация на двумерном массиве. Реализация на одномерном массиве (храним лишь текущий слой): замечание о том, что решения для ограниченного и неограниченного количеств предметов отличаются направлением цикла for.

  3. Динамика по префиксам. Примеры:

  4. НВП.

  5. Количество строк заданной длины из какого-то ограниченного алфавита, не содержащих другую заданную строку в качестве подпоследовательности.

Занятие 7. Динамическое программирование #3

  1. Рекурсия. Примеры:

  2. Вычисление чисел Фибоначчи с помощью рекурсии.

  3. Вывод перевернутого массива с помощью рекурсии.

  4. Задача о ханойских башнях.

  5. Как устроена рекурсия на компьютере. Что такое стек рекурсии.

  6. Как сделать, чтобы глубокая рекурсия работала у вас? (ulimit -s unlimited на Linux/MacOS, sys.setrecursionlimit для Python).

  7. Как переделать рекурсию на stack.

  8. Ленивая динамика: как удобно писать. Примеры задач, где без неё никак. Провести аналогии с DFS.

  9. Динамика по состоянию последнего элемента: количество последовательностей из \(0\) и \(1\) без двух \(0\) подряд.

Занятие 8. Структуры данных #1

  1. Стек, очередь, дек.

Занятие 9. Графы #1

  1. Неориентированные графы.

    • Основные определения: вершина, ребро, путь, цикл, простой путь, простой цикл.

    • Изображение графов. Примеры.

    • Что можно представлять в виде графов? (Например, отношение дружбы.)

    • Ориентированные графы.

    • Взвешенные графы.

    • Как хранить графы?

  2. Матрица смежности.

  3. Списки смежности.

  4. Деревья. Определение дерева. Эквивалентные определения дерева.

    • Подвешенные деревья.

    • Как реализовывать DFS на деревьях без массива used?

Занятие 10. DFS #1

  1. Базовый DFS. Примеры:

    • Проверка графа на связность.

    • Выделение всех компонент связности.

  2. Проверка на двудольность.

Занятие 11. BFS и алгоритм дейкстры

  1. BFS

  2. 0-1 BFS (BFS = deque)

  3. Алгоритм Дейкстры

  4. Алгоритм Дейкстры с кучей

Занятие 12. Жадные алгоритмы

  1. Разбор первого алгоритма по графам

  2. Жадные алгоритмы

  3. Боль нашей жизни - доказательство жадных алгоритмов

Занятие 13. Коллоквиум

Занятие 14. Интерактивные задачи

  1. Интерактивные задачи. flush.

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

  1. Корневая декомпозиция массива для нахождения функции на отрезке

Занятие 16. Битовые операции

  1. Битовые операции: &, |, ^, ~

  2. Представление чисел в памяти

  3. Перебор всех подмасок данной маски

  4. Оценка \(3^n\) на суммарное количество подмасок для всех масок, меньших \(2^n\)

Занятие 17. Куча

  1. Куча: операции sift_down, sift_up. Как реализовывать priority_queue: извлечение минимума и добавление. Удаление/изменение веса произвольного элемента. Heap sort.

Занятие 18. Кратчайшие пути

  1. Дейкстра: базовая и на сете (prioriry_queue!)

  2. Форд-Беллман

  3. Флойд

  4. Детекция циклов отрицательного веса

Занятие 19. Бинарный поиск #2

  1. Бинарный поиск по ответу. Стандартные задачи с каким-нибудь процессом и просьбой минимизировать что-нибудь. Смежные с другими темами примеры: бинпоиск по ответу в графах.

  2. Представление бинпоиска как поиска по степеням двойки: сначала пробуем установить самый старший бит в 1, и т.д.

  3. Тернарный поиск. Примеры функций, к которым можно применять и к которым нельзя. Замечание о том, что, если функция не меняет своего значение лишь в точках экстремума, к ней все же можно применить тернарный поиск

  4. Бинарный поиск по производной

  5. Тернарный поиск с золотым сечением

Занятие 20. Два указателя

  1. Два указателя. Примеры:

    • lower_bound для двух отсортированных массивов.

    • Поиск подотрезка максимальной длины с количеством различных \(\leq k\)

  2. Поиск подотрезка с максимальной суммой. Два способа:

    • Считаем префиксные суммы и поддерживаем минимальную

    • Делаем cur = max(cur + a[i], a[i])

Занятие 21. Работа с памятью

  1. Как считать, сколько памяти будет использовать программа: что такое бит, (кило/мега/гига)байт, сколько байт обычно занимает каждый из примитивных типов.

  2. Сколько вмещает в себя каждый тип данных, знаковые-беззнаковые типы, про точность вещественных чисел

  3. Merge sort. Реализация красивая с \(O(n \log n)\) доп. памяти. Реализация на подотрезках с \(n\) доп. памяти

  4. Применение merge sort для поиска количества инверсий

Занятие 22. DFS #1

  1. DFS: время входа-выхода и топсорт

  2. DFS: конденсация

Занятие 23. Комбинаторика #1

  1. Правила суммы и произведения

  2. Перестановки. Факториал как количество перестановок длины \(n\)

  3. Треугольник Паскаля

  4. Бином Ньютона

Занятие 24. Комбинаторика #2

  1. Поиск числа сложных комбинаторных объектов через динамику: разные виды ПСП, разные разбиения на слагаемые, разные последовательности со странными свойствами (убывающие, возрастающие)

  2. Генерация всех комбинаторных объектов в лексикографическом порядке: перестановок, сочетаний, размещений (с повторениями и без), ПСП, убывающие-возрастающие последовательности, разбиения на слагаемые (разные виды)

Занятие 25. Работа с случайными данными

  1. Что такое ожидаемое время работы?

  2. Quick sort. Реализация со взятием центрального элемента в качестве: утверждение о том, что легко построить тест, на котором это \(O(n ^ 2)\). Реализация со взятием случайного элемента в качестве опорного: утверждение о том, что ожидаемое время работы составляет \(O(n \log n)\)

  3. ТКак правильно писать рандом

Занятие 26. Геометрия - примитивы

  1. Структура вектор

  2. Скалярное и векторное (псевдоскалярное) произведения

  3. Площадь многоугольника

  4. Расстояние от точки до прямой

  5. Проекция точки на прямую

Занятие 27. Геометрия - прямые

  1. Общее уравнение прямой. Переход от него к двум точкам и наоборот. Вектор нормали

  2. Пересечение прямых

  3. Пересечение прямой и окружности

  4. Пересечение двух окружностей

  5. Поиск касательных к окружности

Занятие 28. Игры

  1. Выигрышные, проигрышные состояния

  2. Ретро-анализ