Наивные веса
Серверы делят ключи по рандеву-хешированию, но у них разная мощность. Простая мысль — умножить вес ключа на мощность сервера: для каждого ключа сервер i получает число wi · ui, где ui — случайная величина, равномерно распределённая на [0, 1] и независимая от остальных, и ключ достаётся серверу с наибольшим числом.
Какую долю ключей получит каждый сервер? Выведите для каждого вероятность того, что его число окажется наибольшим. Одна из проверок — мощности прокси из статьи: 1, 1, 1, 1, 2, 2, 4, 4.
Вход
В первой строке — число серверов m (1 ≤ m ≤ 105). Во второй — их мощности w1, …, wm, целые от 1 до 109.
Выход
m чисел — доли серверов в том же порядке. Каждое число засчитывается, если отличается от верного не больше чем на 10−6.
В первом примере мощности 1, 2 и 4 составляют 1/7, 2/7 и 4/7 суммы, но доли выходят совсем другие: самый слабый сервер побеждает, только если и второй, и третий выбросили мало, — вероятность ∫₀¹ (x/2)(x/4) dx = 1/24.
Примеры
Пример 1
3 1 2 4
0.041666667 0.229166667 0.729166667
Пример 2
3 3 3 3
0.333333333 0.333333333 0.333333333
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Зафиксируйте число сервера i: wiui = t. С какой вероятностью сервер j выбросит меньше? Это min(1, t/wj): у слабых серверов (wj ≤ t) — всегда, у сильных — с вероятностью t/wj.
2Идея
Доля сервера i — среднее по t от 0 до wi произведения этих вероятностей:
$$P_i = \frac{1}{w_i}\int_0^{w_i} \prod_{j \ne i} \min\Bigl(1, \frac{t}{w_j}\Bigr)\,dt.$$Отсортируйте мощности: w(1) ≤ … ≤ w(m). Между соседними значениями w(k) ≤ t ≤ w(k+1) множители min(1, ·) равны единице для первых k серверов и t/wj для остальных. Подынтегральное выражение — степень t, делённая на произведение мощностей. Сервер i сам в этом произведении: множитель 1/wi перед интегралом сокращается с ним, и кусок интеграла на отрезке [w(k), w(k+1)] вообще не зависит от i.
3Разбор
Обозначим через Pk произведение всех мощностей начиная с k-й по порядку (нумерация с нуля, w(−1) = 0). Кусок k:
$$S_k = \frac{w_{(k)}^{\,m-k} - w_{(k-1)}^{\,m-k}}{(m-k)\,P_k}.$$Доля сервера, стоящего k-м по порядку, — сумма S0 + … + Sk: его t пробегает все отрезки до его мощности. Сортировка и один проход с префиксной суммой — и все доли готовы. Степени огромны, поэтому всё считается в логарифмах: w(k)m−k/Pk = exp((m − k) ln w(k) − Σj≥k ln w(j)) — показатель не больше нуля, переполнения нет. У равных мощностей кусок между ними пустой, и доли выходят равными.
На прокси из статьи мощность 4 получает 43,6 % ключей вместо 25 %, а мощность 1 — 0,2 % вместо 6,25 %. В девятом тесте один сервер мощности 4 против тридцати тысяч серверов мощностей 1–3 забирает четверть всех ключей: он побеждает каждый раз, когда выбросил больше 3/4. Поэтому взвешенное рандеву-хеширование берёт не w · u, а −w/ln u, — тогда доли точно пропорциональны мощностям, как доказано в статье.
3+Решение
4Сложность
O(m log m) на сортировку, O(m) на остальное. Если считать интеграл заново для каждого сервера, выйдет O(m²) — десять миллиардов шагов на ста тысячах серверов.
5Типичные ошибки
- Пропорционально мощности. Самая естественная догадка, и неверная: первый пример это ловит.
- Степени без логарифмов. wm при m = 105 не помещается ни в одно число с плавающей точкой.
- Равные мощности. Если присвоить долю каждой позиции сортировки отдельно и не заметить, что кусок между равными значениями нулевой, всё сходится само; но если пропускать равные значения при подсчёте m − k, степени сдвинутся.
Алгоритмы задачи
O(N) на ключ
2 задачи
TEC
Приём
Префиксные суммы
Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки.
O(n) на построение, O(1) на запрос
2 задачи