Когда начинать заново
Решатель головоломок — алгоритм Лас-Вегаса: если он остановился, ответ верный, но сколько он проработает, зависит от случайных чисел. Его запустили n раз с независимыми случайными числами и записали, сколько шагов занял каждый прогон; прогоны, которые не закончились за L шагов, оборвали.
Теперь решатель хотят запускать так: если прогон не закончился за t шагов, оборвать его и начать новый, пока какой-нибудь не закончится. Считая, что время прогона распределено так же, как в записанной выборке, выберите t от 1 до L, при котором среднее общее число шагов до ответа наименьшее, и выведите это среднее. Для выборки оно равно
$$\frac{\sum_i \min(T_i,\ t)}{\#\{i : T_i \le t\}},$$где оборванные прогоны считаются длиннее L. Если ни один прогон не закончился, выведите −1.
Вход
В первой строке n и L (1 ≤ n ≤ 200 000, 1 ≤ L ≤ 109). Во второй — n чисел Ti: число шагов прогона от 1 до L или −1, если прогон оборвали.
Выход
Наименьшее среднее число шагов с относительной погрешностью не больше 10−6 или −1.
Примеры
Пример 1
5 100 3 5 -1 4 -1
7.333333
Пример 2
4 100 10 10 10 11
10.250000
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Формула дана, но t — любое число от 1 до L, а L до миллиарда. Как ведёт себя дробь, когда t растёт между двумя соседними значениями из выборки?
2Подсказка 2
Между соседними значениями знаменатель — число прогонов, закончившихся не позже t, — не меняется, а числитель растёт. Значит, кандидаты — только сами длины прогонов. Как посчитать числитель для каждой из них быстро?
3Идея
Почему формула верна, доказано в статье: число прогонов до первого успешного распределено геометрически, и среднее общее время — E[min(T, t)] / P(T ≤ t). На отрезке между соседними длинами vk ≤ t < vk+1 знаменатель постоянен, а числитель растёт на число ещё не закончившихся прогонов за каждый шаг t. Поэтому минимум достигается в левом конце, при t = vk, а значения t меньше самой короткой длины недопустимы: знаменатель ноль.
Отсортируем законченные прогоны. Для t, равного k-й по величине длине (последней из равных ей), числитель — сумма первых k длин плюс t, умноженное на число всех остальных прогонов, включая оборванные: оборванный прогон тоже успел проработать t шагов, прежде чем его остановили. Это и есть ловушка задачи.
4Разбор
Сортировка, проход с префиксной суммой, минимум из дробей. Равные длины нужно обрабатывать вместе: знаменатель — число всех прогонов длины не больше t.
Четвёртый тест — настоящие прогоны решателя судоку из статьи: 300 прогонов, оборванных на 20 000 шагов. Лучшая граница даёт в среднем 5685 шагов на решение — близко к замеру в статье, где при t = 2000 вышло 5635 на другой выборке из 400 прогонов.
4+Решение
5Сложность
O(n log n) на сортировку, остальное — O(n).
6Типичные ошибки
- Оборванные прогоны бесплатны. Если не считать им t шагов, перезапуски кажутся выгоднее, чем есть: на первом примере выходит 4 вместо 7,333.
- Перебор всех t от 1 до L. При L = 109 это слишком долго.
- Равные длины по одной. Если для t = v учесть только часть прогонов длины v, знаменатель будет занижен, а дробь — неверной (седьмой тест).
- 32 бита. В восьмом тесте числитель — около 2·1014.