Convex hull trick

Чтобы проверить все решения каталога, песочница запускает 1776 тестов — подряд, по одному процессу на тест. Запуск песочницы стоит своё: пустая программа от запроса до ответа идёт 65–150 мс. Можно запускать каждый тест отдельно и платить за запуск 1776 раз, можно один раз запустить всё и ждать первый вердикт до самого конца. Лучшее — делить тесты на пачки: при запуске в 80 мс выгоднее всего 41 запуск, и вердикт в среднем приходит через 44 секунды — против 113 при запуске на каждый тест и 81 при одном запуске на всё. Такое деление ищет динамика, а чтобы она работала не за квадрат, а за линейное время, нужен один геометрический приём.

Чем дешевле запуск, тем больше пачек: при 10 мс их 102, при секунде — 12. Первые пачки большие, последние маленькие: вердикты из конца очереди всё равно ждут всех, кто перед ними, а пачка в начале задерживает всех после себя.

Идея

Пусть T_i — суммарное время первых i тестов, S — цена запуска. Пачка из тестов j + 1 … i длится S + T_i − T_j и задерживает вердикты всех тестов после j — их n − j. Поэтому сумма ожиданий складывается по пачкам, и лучшее деление первых i тестов

best[i] = min_{j < i} ( best[j] + (S + T_i − T_j) · (n − j) ).

Перебор j — это n²/2 шагов. Но для фиксированного j выражение — прямая от x = T_i: наклон n − j, сдвиг best[j] + (S − T_j) · (n − j). Значит, best[i] — это значение нижней огибающей всех прямых j < i в точке T_i.

Если переход динамики — минимум выражений «k_j · x_i + b_j», каждое j — прямая, а нужен минимум прямых в точке. Огибающая — выпуклая ломаная, и прямые, которые на ней нигде не лежат, можно выбросить навсегда. Если наклоны приходят по убыванию, а точки по возрастанию, огибающая держится в деке: каждая прямая один раз входит и один раз выходит.

Посмотрите на деке по шагам. Здесь 13 тестов одной задачи; на каждом шаге в конец дека приходит новая прямая — у неё самый маленький наклон, — а сзади уходят прямые, которые она сделала ненужными. Потом точка запроса сдвигается вправо, и спереди уходят прямые, которые в ней уже не лучшие.

Почему дек верен

Обозначим через x(u, v) абсциссу пересечения прямых u и v.

Каждая прямая добавляется один раз и удаляется не больше одного раза, поэтому вся динамика — O(n). Для пачек тестов это выполняется само: наклон n − j убывает с j, а T_i растёт с i.

Дерево Ли Чао: когда порядка нет

Если наклоны приходят как попало или запросы прыгают, дек не годится. Дерево Ли Чао строится над отрезком возможных x, как дерево отрезков. Каждый узел хранит одну прямую — ту, что ниже в середине его отрезка. Новая прямая сравнивается с хранимой в середине: победитель остаётся, проигравший спускается в одну половину — туда, где он может ещё выиграть. Запрос в точке x идёт от корня к листу и берёт минимум прямых на пути.

Вставка и запрос — O(log C), где C — число возможных x. Дерево хорошо и тогда, когда прямые нельзя упорядочить заранее: например, если они приходят вперемешку с запросами.

Код

Перебор j оставлен в листинге как проверка: на 1776 тестах он ещё быстрый. Дек хранит прямые с номерами j, чтобы восстановить пачки; прямая кладётся до запроса, потому что j = i − 1 — допустимый последний разрез.

Сколько это стоит

Замер — та же задача на очередях длины n: времена тестов каталога повторяются по кругу, запуск 80 мс.

На двух тысячах тестов перебор на Python уже больше чем в сто раз медленнее дека, на Go при шестнадцати тысячах — в тысячу раз; дек обрабатывает миллион тестов на Go за 17 миллисекунд.

Где легко ошибиться

• Переполнение в сравнении. Проверка «лишняя ли прямая» умножает разность сдвигов на разность наклонов. В пачках тестов соседние наклоны отличаются на единицу, и на тестах задачи к статье произведения не больше 2,4 · 10¹². Но если наклоны и точки — числа до 10⁹, произведение выходит за 64 бита, и нужны 128-битные числа или сравнение дробей.
• Равные наклоны. Из двух параллельных прямых лишняя та, что выше; формула с пересечениями на них делит на ноль.
• Порядок шагов. Прямая j = i − 1 должна попасть в дек до запроса i, иначе пачка из одного последнего теста не рассматривается.
• Уход спереди при немонотонных запросах. Если точки запросов не растут, убранная спереди прямая может понадобиться снова. Тогда нужен двоичный поиск по деку или дерево Ли Чао.
• Не та огибающая. Для максимума нужна верхняя огибающая: наклоны и неравенства меняются местами.

Где работает

Пачки с ценой запуска — в расписаниях и при группировке запросов к медленному сервису. Динамика с квадратичной стоимостью перехода: (h_i − h_j)² раскрывается в h_i² − 2h_jh_i + h_j², и это снова прямая от h_i. Без всякой динамики огибающая прямых отвечает, какой из тарифов «плата + цена за единицу» дешевле при данном расходе, и кто впереди в момент t, если каждый движется равномерно. Если же переход не раскладывается в прямые, но у него есть монотонность лучшего j, помогают оптимизации Кнута и «разделяй и властвуй».

История

Задача о делении заданий на пачки с ценой запуска — классика теории расписаний. На Международной олимпиаде по информатике 2002 года её дали школьникам, и с тех пор приём с деком прямых стал олимпиадной классикой. Дерево Ли Чао пришло из олимпиадного программирования и носит имя автора; оно ценно тем, что не требует никакого порядка ни от прямых, ни от запросов.

Задачи

Пачки тестов — ровно задача из статьи, но на сотнях тысяч тестов. И тарифы, которые появляются вперемешку с вопросами «сколько я заплачу при расходе x», — для дерева Ли Чао.