Комбинаторика и интерполяция в задаче «D. Обряды инков», Yandex Cup 2024, Алгоритм, Полуфинал

В этом видео я дорешиваю задачу «D. Обряды инков» из соревнования «Yandex Cup 2024 — Алгоритм — Полуфинал» и подробно объясняю решение: комбинаторику, интерполяцию, многочлены Лагранжа и метод Гаусса решения системы линейных уравнений при нахождении коэффициентов интерполяционного многочлена. Решение задачи, полученное во время видео: Я сдал именно то, что рассказал за первые 20 минут видео, потратив значительную часть времени на поиск багов, написание кода и получение эффективной реализации. После записи видео я ещё немного посидел, подумал и добился 318 мс: Тайм-коды: 00:00:00 Доброе утро 00:00:45 Упрощение задачи 00:07:15 Решение упрощённой задачи 00:13:00 Интерполяция многочленами 00:18:30 Многочлены Лагранжа 00:22:30 Идём писать исходный код 00:25:45 Реализуем модульную арифметику 00:42:30 Реализуем сведение к упрощённой задаче 00:46:30 Ищем ошибку в коде сведения к упрощённой задаче 00:54:50 Реализуем решение упрощённой задачи 01:12:30 Реализуем многочлен Лагранжа 01:21:15 Применяем асимптотические оптимизации 01:23:20 Выкидываем бинарный поиск, заменяя его формулой 01:35:20 Заменяем Лагранжа методом Гаусса 01:49:00 Исправляем ошибки в методе Гаусса 02:01:00 Удаляем лишний код 02:02:35 Пытаемся найти неэффективные места в коде и что-нибудь сделать 02:18:50 Догадался заменить long double на double 02:22:59 Догадался, что отрезок [s, f] довольно быстро уменьшается до одной точки s=f=2 02:36:50 Оптимизирую вычисление значения многочлена в точке 02:41:30 Пробую бесполезные оптимизации 02:47:50 Оптимизация крайних случаев суммы степеней 02:51:30 Полное решение