CS
Задачник Базовый курс EN

Задача

Лучший из двух

балансировка случайность очередь симуляция в проде

Балансировщик раздаёт запросы k серверам. Для каждого запроса он спрашивает двух случайных серверов, сколько у них незаконченных заданий, и отдаёт запрос тому, у кого их меньше; при равенстве — первому из двух. Каждый сервер выполняет задания по очереди, в порядке поступления: задание, пришедшее в момент t и требующее s мкс, начинается, когда сервер закончит предыдущие, но не раньше t. Задание незакончено в момент t, если оно закончится строго позже t.

Посчитайте сумму и максимум времён ответа: от прихода запроса до конца его выполнения. Среди тестов — очередь из статьи: десять серверов отдают файлы сайта настоящих размеров.

Вход

В первой строке — число серверов k и число запросов n (1 ≤ k ≤ 105, 1 ≤ n ≤ 105). Дальше n строк «t s a b»: момент прихода, длительность в микросекундах и два предложенных сервера (1 ≤ a, b ≤ k, могут совпасть). Моменты не убывают; 0 ≤ t ≤ 1012, 1 ≤ s ≤ 106.

Выход

Два числа: сумма времён ответа и наибольшее из них.

Во втором примере задание на сервере 1 заканчивается ровно в момент 10, когда приходит четвёртый запрос: в этот момент оно уже не считается.

Примеры

Пример 1

Вход
3 5
0 5 1 2
1 5 1 2
2 5 1 2
8 5 3 1
12 1 1 3
Выход
24 8

Пример 2

Вход
2 5
0 10 1 2
0 10 1 2
0 10 2 1
10 3 1 2
20 1 2 2
Выход
44 20

Ограничения

Время · Python
4000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
6 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Сколько незаконченных заданий у сервера в момент t? Это те его задания, которые закончатся позже t. Как узнать это число, не пересчитывая всё?

2Идея

Сервер работает по очереди, поэтому моменты окончания его заданий растут в том порядке, в каком задания пришли. Держим для каждого сервера очередь этих моментов. Когда приходит запрос, выбрасываем из очередей двух кандидатов всё, что закончилось к моменту t, — с головы, пока голова не больше t. Остаток очереди и есть число незаконченных. Каждое задание выбрасывается не больше одного раза, поэтому вся чистка стоит O(n), а не O(n·k): очереди остальных серверов никто не трогает, пока о них не спросят.

3Разбор

Момент окончания нового задания — max(когда сервер освободится, t) + s; он же — новый конец очереди сервера. Время ответа — разность с t. Суммы большие: до 105 запросов, а ответы на длинных очередях доходят до долей секунды, — в Go нужен int64, что и даёт обычный int.

Третий тест — та же очередь, что в статье, где правило двух вдвое сокращает среднее время ответа по сравнению с одним случайным сервером. Но правило работает, только если спрашивать о настоящем: сколько незаконченных заданий сейчас.

3+Решение
4Сложность

O(n + k): каждое задание один раз попадает в очередь и один раз из неё уходит.

5Типичные ошибки
  • Сколько выдано, а не сколько не закончено. Счётчик выданных заданий растёт всегда; сервер, взявший много коротких заданий давно, сейчас свободен, а взявший один огромный файл — занят. Так ошибаются уже первые примеры.
  • Чистить все очереди. Ответ тот же, но на ста тысячах серверов это сто тысяч шагов на каждый запрос.
  • Граница. Задание, которое закончилось ровно в момент прихода, уже не мешает.

Алгоритмы задачи

SYS Алгоритм Два случайных выбора Спросить двух случайных и выбрать менее занятого: самая полная корзина — ln ln n вместо ln n / ln ln n. O(d) на решение: узнать нагрузку d серверов 2 задачи DS Структура данных Стек и очередь Стек: последним пришёл — первым ушёл. Очередь: первым пришёл — первым ушёл. Каждая операция — O(1). O(1) на push и pop, enqueue и dequeue 2 задачи
Каталог алгоритмов