Путь к вершине: Разбор финала Google Kickstart 2020 от Скотта Ву 0:00
Google Kickstart — это ежемесячные соревнования по программированию, привлекающие тысячи участников по всему миру. В этом видео Скотт Ву (Scott Wu) проводит подробный разбор своего участия в раунде B 2020 года, демонстрируя процесс мышления и решения четырёх алгоритмических задач, каждая из которых требует глубокого понимания структур данных и математических подходов.
🛠 Задача 1: Прогулка на велосипеде (Bike Tour) 0:38
Первая задача оказалась классическим упражнением на реализацию алгоритма. Участникам предоставляется список высот холмов, и требуется подсчитать количество «пиков».
- Определение: Холм считается пиком, если его высота строго больше высоты соседей слева и справа.
- Реализация: По условию задачи, крайние холмы не могут быть пиками, поэтому цикл перебора элементов строится от 1 до $n-1$.
- Итог: Задача решается простым линейным проходом по массиву и проверкой условий для каждого элемента.
🚌 Задача 2: Маршруты автобусов (Bus Routes) 1:20
Во второй задаче необходимо рассчитать самое позднее время отправления, чтобы успеть на серию автобусов и добраться до конечной остановки в течение $D$ дней.
- Подход: Скотт Ву предлагает использовать бинарный поиск для нахождения ответа.
- Проверка: Для заданного времени $K$ алгоритм последовательно проверяет, успевает ли пассажир на каждый следующий автобус.
- Нюансы: Автор отмечает, что существуют альтернативные подходы, не требующие бинарного поиска, однако именно этот метод кажется ему наиболее интуитивным для проверки возможности выполнения условий.
🤖 Задача 3: Робот-декодер (Robot Path Decoding) 3:20
Третья задача значительно сложнее предыдущих из-за использования вложенных команд. Робот выполняет команды перемещения (N, S, E, W), а также специальные циклы с множителями, которые могут быть вложены друг в друга.
- Почему брутфорс не работает: Прямое выполнение каждой команды для больших вложенных циклов может привести к экспоненциальному числу операций, что недопустимо по времени выполнения.
- Рекурсия и DP: Скотт Ву использует динамическое программирование (DP) и рекурсивную функцию
figure. Она вычисляет смещение по осям X и Y для каждой подстроки, что позволяет «схлопывать» повторяющиеся действия. - Сложности отладки: В процессе написания кода автор столкнулся с ошибками индексации и путаницей в осях координат (North/South), которые удалось исправить через пошаговую отладку.
🎯 Задача 4: Вероятности на сетке (Robot Path) 12:18
Самая сложная задача раунда представляет собой движение по прямоугольной сетке $W \times H$ из точки $(1, 1)$ в точку $(W, H)$. В сетке вырезан прямоугольный «провал», в который нельзя попадать.
- Масштаб проблемы: Поскольку размеры сетки достигают 100 000, общее число клеток составляет до 10 миллиардов, что исключает полное переборное DP.
- Математический аппарат: Автор применяет методы комбинаторики, используя функцию сочетаний ($n$ из $k$) для расчёта вероятностей.
- Работа с логарифмами: Из-за того, что числа (факториалы) становятся колоссальными, Скотт Ву переходит к работе с логарифмами значений, что позволяет избежать переполнения типов данных и упрощает вычисления.
- Геометрия путей: Задача сводится к поиску вероятности обхода прямоугольника сверху-справа или снизу-слева, учитывая особые условия движения у границ сетки.
