Разбираем Bauman Code Games X. Часть 1

В этом видео разбираем первые четыре задачи с отборочного этапа Bauman Code Games X. Для них мы последовательно используем разные идеи и техники: — Задача A: строковый конструктив; — Задача B: метод сканирующей прямой; — Задача C: анализ дерева игры, сведение к Ниму и применение теоремы Шпрага—Гранди; — Задача D: рассматриваем произведение по модулю и получаем простой критерий того, когда оно равно нулю. Тайм-коды: 00:00:00 Задача A. Малый набор 00:00:45 Разбор крайних случаев 00:01:20 Основная идея 00:04:20 Доказательство идеи 00:05:55 Способы решения задачи 00:11:10 Задача B. Больше нулей! 00:11:20 Разбор условия и допустимых операций 00:12:06 Основная идея: экстремумы и порядок обхода 00:14:15 Доказательство: почему выгодно идти от меньших к большим 00:17:46 Подробно про утверждения, на которых основано решение 00:20:52 Подходы к реализации решения 00:28:10 Оценка на то, какие элементы можно удалить 00:29:30 Используем метод сканирующей прямой (открытые отрезки) 00:36:00 Использование сета (set/multiset) для хранения состояний 00:39:39 Реализация на C++ 00:47:00 Упрощаем реализацию 00:54:54 Обсуждение альтернативного способа на С++ 01:00:10 Задача C. Информатика для самых маленьких 01:00:25 Правила классической Игры Ним (кучи камней) 01:03:06 Базовая логика «душения» противника и копирования ходов 01:04:15 Разбор базовых случаев с выигрышными и проигрышными состояниями 01:09:00 Зависимость выигрыша от кратности и XOR-суммы 01:15:35 Наглядная иллюстрация: раскладываем...