Разбираем Bauman Code Games X. Часть 1
В этом видео разбираем первые четыре задачи с отборочного этапа Bauman Code Games X. Для них мы последовательно используем разные идеи и техники: — Задача A: строковый конструктив; — Задача B: метод сканирующей прямой; — Задача C: анализ дерева игры, сведение к Ниму и применение теоремы Шпрага—Гранди; — Задача D: рассматриваем произведение по модулю и получаем простой критерий того, когда оно равно нулю. Наш Telegram-канал: https://t.me/mireacoding Тайм-коды: 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 Наглядная иллюстрация: раскладываем кучи по степеням двойки 01:20:51 Сведение задачи к битовым операциям 01:21:09 «Побеждает тот, кто не может сделать ход» — на что это влияет? 01:30:10 Анализ влияния четности/нечетности единиц на исход 01:38:07 Ищем и проверяем контр-тесты 01:39:15 Определение победителя при оптимальной игре 01:45:50 Правильная идея решения 01:47:35 Написание перебора дерева игры для проверки гипотезы 01:59:15 Полное решение задачи 02:02:29 Задача D. Вычисление произведений 02:05:20 Идея с префиксными суммами по модулю 10 02:12:50 Формирование итогового ответа 02:15:10 Общие вопросы и остальные задачи 02:15:10 Советы по тренировкам и правильному нарешиванию задач 02:18:30 Задача E: идея решения через бинпоиск по хешам 02:18:45 Задача F: обсуждение сложности и графов (BFS) 02:28:24 Сравнение с аналогичной задачей с отбора на стажировку в Яндекс 02:34:00 Итоги и завершение разбора
В этом видео разбираем первые четыре задачи с отборочного этапа Bauman Code Games X. Для них мы последовательно используем разные идеи и техники: — Задача A: строковый конструктив; — Задача B: метод сканирующей прямой; — Задача C: анализ дерева игры, сведение к Ниму и применение теоремы Шпрага—Гранди; — Задача D: рассматриваем произведение по модулю и получаем простой критерий того, когда оно равно нулю. Наш Telegram-канал: https://t.me/mireacoding Тайм-коды: 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 Наглядная иллюстрация: раскладываем кучи по степеням двойки 01:20:51 Сведение задачи к битовым операциям 01:21:09 «Побеждает тот, кто не может сделать ход» — на что это влияет? 01:30:10 Анализ влияния четности/нечетности единиц на исход 01:38:07 Ищем и проверяем контр-тесты 01:39:15 Определение победителя при оптимальной игре 01:45:50 Правильная идея решения 01:47:35 Написание перебора дерева игры для проверки гипотезы 01:59:15 Полное решение задачи 02:02:29 Задача D. Вычисление произведений 02:05:20 Идея с префиксными суммами по модулю 10 02:12:50 Формирование итогового ответа 02:15:10 Общие вопросы и остальные задачи 02:15:10 Советы по тренировкам и правильному нарешиванию задач 02:18:30 Задача E: идея решения через бинпоиск по хешам 02:18:45 Задача F: обсуждение сложности и графов (BFS) 02:28:24 Сравнение с аналогичной задачей с отбора на стажировку в Яндекс 02:34:00 Итоги и завершение разбора