Правильные скобочные последовательности. Лекция
В этой лекции по спортивному программированию подробно разбираем правильные скобочные последовательности: даём определение ПСП, обсуждаем алгоритм проверки и его реализацию на C++, рассматриваем лексикографически минимальную и максимальную ПСП, а также решаем задачи на следующую ПСП, генерацию всех ПСП, нахождение k-й ПСП и номера заданной последовательности. Далее переходим к более глубоким идеям: рассматриваем графическое представление ПСП как путей Дика, считаем количество всех правильных скобочных последовательностей, доказываем формулу чисел Каталана через отражение плохих путей и показываем два динамических подхода — одномерную и двумерную динамику по длине и балансу. В конце разбираем, как использовать таблицу динамики для поиска k-й ПСП и номера последовательности, а также обсуждаем задачу на количество ПСП, содержащих данную строку как подстроку, и задачу на конкатенацию скобочных последовательностей в одну ПСП. Материалы: https://github.com/dmkz/competitive-programming/tree/master/mirea/cources/middle/2026/brackets Тайм-коды: 00:00:00 Введение 00:02:10 Определение ПСП 00:06:40 Алгоритм проверки ПСП 00:14:30 Реализация алгоритма проверки ПСП 00:17:45 Обзор задач на алгоритм проверки ПСП 00:22:50 Лексикографически наименьшая и наибольшая ПСП 00:25:05 Задача о лексикографически следующей ПСП 00:32:00 Рекурсивная генерация всех ПСП 00:33:50 Реализация алгоритма генерации на C++ 00:41:30 Нахождение k-й ПСП в лексикографическом порядке 00:43:30 Нахождение номера для заданной ПСП 00:44:30 Графическое представление всех ПСП 00:50:35 Количество всех ПСП 00:53:00 Доказательство чисел Каталана 01:01:05 Второй способ: одномерная динамика по длине 01:04:15 Третий способ: двумерная динамика по длине и балансу 01:07:00 Использование таблицы динамического программирования для поиска k-й ПСП и нахождения номера для заданной ПСП 01:10:40 Пример задачи на ПСП и динамику 01:19:30 Конкатенация пар скобочных подпоследовательностей в одну ПСП
В этой лекции по спортивному программированию подробно разбираем правильные скобочные последовательности: даём определение ПСП, обсуждаем алгоритм проверки и его реализацию на C++, рассматриваем лексикографически минимальную и максимальную ПСП, а также решаем задачи на следующую ПСП, генерацию всех ПСП, нахождение k-й ПСП и номера заданной последовательности. Далее переходим к более глубоким идеям: рассматриваем графическое представление ПСП как путей Дика, считаем количество всех правильных скобочных последовательностей, доказываем формулу чисел Каталана через отражение плохих путей и показываем два динамических подхода — одномерную и двумерную динамику по длине и балансу. В конце разбираем, как использовать таблицу динамики для поиска k-й ПСП и номера последовательности, а также обсуждаем задачу на количество ПСП, содержащих данную строку как подстроку, и задачу на конкатенацию скобочных последовательностей в одну ПСП. Материалы: https://github.com/dmkz/competitive-programming/tree/master/mirea/cources/middle/2026/brackets Тайм-коды: 00:00:00 Введение 00:02:10 Определение ПСП 00:06:40 Алгоритм проверки ПСП 00:14:30 Реализация алгоритма проверки ПСП 00:17:45 Обзор задач на алгоритм проверки ПСП 00:22:50 Лексикографически наименьшая и наибольшая ПСП 00:25:05 Задача о лексикографически следующей ПСП 00:32:00 Рекурсивная генерация всех ПСП 00:33:50 Реализация алгоритма генерации на C++ 00:41:30 Нахождение k-й ПСП в лексикографическом порядке 00:43:30 Нахождение номера для заданной ПСП 00:44:30 Графическое представление всех ПСП 00:50:35 Количество всех ПСП 00:53:00 Доказательство чисел Каталана 01:01:05 Второй способ: одномерная динамика по длине 01:04:15 Третий способ: двумерная динамика по длине и балансу 01:07:00 Использование таблицы динамического программирования для поиска k-й ПСП и нахождения номера для заданной ПСП 01:10:40 Пример задачи на ПСП и динамику 01:19:30 Конкатенация пар скобочных подпоследовательностей в одну ПСП