Problems Base course RU

Naive weights

probabilistic hashing load balancing sorting numerical precision

Servers share keys by rendezvous hashing, but they differ in strength. The simple idea is to multiply a key’s weight by the server’s strength: for each key server i gets the number w_i · u_i, where u_i is a random variable uniformly distributed on [0, 1] and independent of the others, and the key goes to the server with the largest number.

What share of the keys does each server get? For each, print the probability that its number turns out the largest. One of the checks is the proxy strengths from the article: 1, 1, 1, 1, 2, 2, 4, 4.

Input

The first line holds the number of servers m (1 ≤ m ≤ 10⁵). The second holds their strengths w₁, …, w_m, integers from 1 to 10⁹.

Output

m numbers: the servers’ shares in the same order. Each number is accepted if it differs from the correct one by at most 10⁻⁶.

In the first example the strengths 1, 2 and 4 are 1/7, 2/7 and 4/7 of the sum, but the shares come out quite different: the weakest server wins only if both the second and the third rolled low, with probability ∫₀¹ (x/2)(x/4) dx = 1/24.

Examples

Example 1

Input

3
1 2 4

Output

0.041666667 0.229166667 0.729166667

Example 2

Input

3
3 3 3

Output

0.333333333 0.333333333 0.333333333

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 9 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Fix server i’s number: w_iu_i = t. With what probability does server j roll less? It is min(1, t/w_j): weak servers (w_j ≤ t) always do, strong ones with probability t/w_j.

2The idea

Server i’s share is the average over t from 0 to w_i of the product of these probabilities:

$$P_i = \frac{1}{w_i}\int_0^{w_i} \prod_{j \ne i} \min\Bigl(1, \frac{t}{w_j}\Bigr)\,dt.$$

Sort the strengths: w₍₁₎ ≤ … ≤ w_(m). Between neighbouring values w_(k) ≤ t ≤ w_(k+1) the factors min(1, ·) equal one for the first k servers and t/w_j for the rest. The integrand is a power of t divided by a product of strengths. Server i itself is in that product: the factor 1/w_i in front of the integral cancels with it, and the piece of the integral on the segment [w_(k), w_(k+1)] does not depend on i at all.

3Walkthrough

Denote by P_k the product of all strengths from the k-th in sorted order on (numbering from zero, w₍₋₁₎ = 0). The k-th piece is

$$S_k = \frac{w_{(k)}^{\,m-k} - w_{(k-1)}^{\,m-k}}{(m-k)\,P_k}.$$

The share of the server standing k-th in order is the sum S₀ + … + S_k: its t runs over all the segments up to its strength. A sort and one pass with a prefix sum, and all the shares are ready. The powers are huge, so everything is computed in logarithms: w_(k)^m−k/P_k = exp((m − k) ln w_(k) − Σ_j≥k ln w_(j)); the exponent is at most zero, so there is no overflow. Between equal strengths the piece is empty, and the shares come out equal.

On the proxies from the article strength 4 gets 43.6% of the keys instead of 25%, and strength 1 gets 0.2% instead of 6.25%. In the ninth test a single strength-4 server against thirty thousand servers of strengths 1–3 takes a quarter of all keys: it wins every time it rolls more than 3/4. That is why weighted rendezvous hashing uses not w · u but −w/ln u: then the shares are exactly proportional to the strengths, as proved in the article.

3+Solution

4Complexity

O(m log m) for the sort, O(m) for the rest. Computing the integral anew for each server gives O(m²), ten billion steps on a hundred thousand servers.

5Common mistakes

Proportional to strength. The most natural guess, and wrong: the first example catches it.
Powers without logarithms. w^m with m = 10⁵ fits in no floating-point number.
Equal strengths. If you assign a share to each sorted position separately without noticing that the piece between equal values is zero, everything works out by itself; but if you skip equal values when counting m − k, the powers shift.

Algorithms behind it

SYS Algorithm Rendezvous hashing Each key goes to the server with the largest hash of the pair “key, server”: even, table-free, and a failure moves only the failed server’s keys. O(N) per key 2 problems TEC Technique Prefix sums The sum of any segment in O(1) after one pass; the two-dimensional version gives the sum of any rectangle of a picture. O(n) to build, O(1) per query 2 problems