BSUIR Open 2023 Semifinals: задачи B, D и E - любительский разбор

Решения задач: Тайм-коды: 00:00:00 Задача “D. Differences“ 00:03:00 Решение Динамикой за O(n*k*n): медленное, но гарантированно правильное 00:09:10 Вопросы по медленной динамике 00:11:52 Оптимизируем динамику, раскрывая модуль 00:18:10 Добавляем Дерево Отрезков и сжатие координат 00:23:13 Вопросы по динамике с Деревом Отрезков за O(n*k*log(n)) 00:28:10 Двуслойная динамика: срезаем память до O(n) 00:31:00 Где именно делать запросы к дереву отрезков внутри динамики 00:35:00 Исходный код решения с Деревом Отрезков 00:38:30 Функции std::fill и remax/setmax 00:47:30 Решение за O(n*k) путём выкидывания Дерева Отрезков 00:48:40 Пауза 00:50:05 Почему можно выкинуть Дерево Отрезков 00:52:30 Рассматриваем пример 00:55:00 Смотрим исходный код решения O(n*k) 00:59:59 Разбираем исходный код ещё один раз 01:03:00 Задача “B. Non-sand watches“ 01:03:45 Украли задачу у Бориса Трушина “Когда все углы равны 120 градусов“ 01:04:20 Начинаем решать задачу 01:08:20 Сперва смотрим на формат вывода ответа 01:09:20 Уравнение для нахождения первого момента времени 01:12:32 Уравнение для нахождения второго момента времени 01:15:35 Ещё один случай, когда угол равен p/q 01:23:40 Получили формулу для второго момента времени 01:24:27 Уравнение для нахождения периода 01:27:30 Нашли период и получили общий вид моментов времени 01:28:28 Аккуратно перепроверяем вычисления и формулы 01:31:40 Используем Fractions в Python3 - решение на python 01:32:15 Находим скорости каждой из стрелок 01:34:20 Разбираем решение на Python3 с дробями 01:37:52 Разбираем решение на C со своими дробями 01:47:40 Задача “E. Buying a car“ 01:49:20 Выписываем и упрощаем неравенство 01:53:00 Разбираем исходный код решения на Python3 01:58:10 Можно логарифмы от чисел сравнивать вместо чисел, но это WA по точности