# Скотт Ву: «Разбор задач с Google Kickstart 2020»

Источник: https://www.youtube.com/watch?v=AP74zQ0ZmRM
Канал: Scott Wu
Опубликовано: 20.04.2020

---

## Путь к вершине: Разбор финала Google Kickstart 2020 от Скотта Ву
[[JUMP:00:00]]

Google Kickstart — это ежемесячные соревнования по программированию, привлекающие тысячи участников по всему миру. В этом видео Скотт Ву (Scott Wu) проводит подробный разбор своего участия в раунде B 2020 года, демонстрируя процесс мышления и решения четырёх алгоритмических задач, каждая из которых требует глубокого понимания структур данных и математических подходов.

### 🛠 Задача 1: Прогулка на велосипеде (Bike Tour)
[[JUMP:00:38]]

Первая задача оказалась классическим упражнением на реализацию алгоритма. Участникам предоставляется список высот холмов, и требуется подсчитать количество «пиков».

* **Определение:** Холм считается пиком, если его высота строго больше высоты соседей слева и справа.
* **Реализация:** По условию задачи, крайние холмы не могут быть пиками, поэтому цикл перебора элементов строится от 1 до $n-1$.
* **Итог:** Задача решается простым линейным проходом по массиву и проверкой условий для каждого элемента.

### 🚌 Задача 2: Маршруты автобусов (Bus Routes)
[[JUMP:1:20]]

Во второй задаче необходимо рассчитать самое позднее время отправления, чтобы успеть на серию автобусов и добраться до конечной остановки в течение $D$ дней.

* **Подход:** Скотт Ву предлагает использовать **бинарный поиск** для нахождения ответа.
* **Проверка:** Для заданного времени $K$ алгоритм последовательно проверяет, успевает ли пассажир на каждый следующий автобус.
* **Нюансы:** Автор отмечает, что существуют альтернативные подходы, не требующие бинарного поиска, однако именно этот метод кажется ему наиболее интуитивным для проверки возможности выполнения условий.

### 🤖 Задача 3: Робот-декодер (Robot Path Decoding)
[[JUMP:3:20]]

Третья задача значительно сложнее предыдущих из-за использования вложенных команд. Робот выполняет команды перемещения (N, S, E, W), а также специальные циклы с множителями, которые могут быть вложены друг в друга.

* **Почему брутфорс не работает:** Прямое выполнение каждой команды для больших вложенных циклов может привести к экспоненциальному числу операций, что недопустимо по времени выполнения.
* **Рекурсия и DP:** Скотт Ву использует **динамическое программирование (DP)** и рекурсивную функцию `figure`. Она вычисляет смещение по осям X и Y для каждой подстроки, что позволяет «схлопывать» повторяющиеся действия.
* **Сложности отладки:** В процессе написания кода автор столкнулся с ошибками индексации и путаницей в осях координат (North/South), которые удалось исправить через пошаговую отладку.

### 🎯 Задача 4: Вероятности на сетке (Robot Path)
[[JUMP:12:18]]

Самая сложная задача раунда представляет собой движение по прямоугольной сетке $W \times H$ из точки $(1, 1)$ в точку $(W, H)$. В сетке вырезан прямоугольный «провал», в который нельзя попадать.

* **Масштаб проблемы:** Поскольку размеры сетки достигают 100 000, общее число клеток составляет до 10 миллиардов, что исключает полное переборное DP.
* **Математический аппарат:** Автор применяет методы комбинаторики, используя функцию сочетаний ($n$ из $k$) для расчёта вероятностей.
* **Работа с логарифмами:** Из-за того, что числа (факториалы) становятся колоссальными, Скотт Ву переходит к работе с **логарифмами** значений, что позволяет избежать переполнения типов данных и упрощает вычисления.
* **Геометрия путей:** Задача сводится к поиску вероятности обхода прямоугольника сверху-справа или снизу-слева, учитывая особые условия движения у границ сетки.