Рекурсивные конструктивы - Часть 1

В этом видео мы говорим о рекурсивных конструктивах: разбираем общие принципы решения таких задач, приёмы и идеи, которые сильно помогают решать любую задачу и кодить её в 20 строк без багов. Разобранные задачи: 1. “А. Загадка Нефлены“ - поиск k-го символа в строке, которая строится рекурсивно и содержит в себе все предыдущие строки; 2. Поиск k-й лексикографически минимальной перестановки; 3. Поиск k-й лексикографически минимальной подпоследовательности массива; 4. “B. Восторг“ - рекурсивное построение матрицы из чисел для максимизации заданной в условии функции. 00:00:00 Введение 00:01:00 Что такое рекурсивные конструктивы 00:03:00 Пример: “A. Загадка Нефлены“ 00:04:20 Обсуждение задачи 00:06:30 Общий принцип решения рекурсивных конструктивов 00:08:10 Приём 1: переход в 0-индексацию (всегда) 00:10:10 Приём 2: вычитаем из номера размер обработанной группы 00:14:20 Приём 3: обходим переполнения с помощью INF 00:16:15 Решение задачи ещё раз 00:17:00 Вопросы 00:18:00 Задача о k-й лексикографически минимальной перестановке 00:20:35 Решение задачи: находим первый элемент ответа 00:23:20 Рекурсивный переход 00:27:10 Псевдокод решения 00:31:20 Асимптотика решения 00:44:04 Задача с квала ICPC на k-ю лексикографически минимальную подпоследовательность массива 00:51:00 Краткий обзор остальных задач 00:55:10 Задача: “B. Восторг“ 00:59:58 Как решать задачу 01:07:10 Вопросы по задаче 01:10:16 Решение задачи ещё раз 01:15:00 Комбинирование ответов от рекурсивных вызовов 01:20:54 Болтаем и прощаемся