Problems Base course RU

A lazy tourist

randomized graph simulation geodata maps and navigation

A lazy tourist strolls around a city’s crossings. Once a minute the tourist picks at random one of the streets leaving the current crossing, all equally likely. If the street leads to a crossing no higher than the current one, the tourist takes it. If it is higher by Δ metres, the tourist takes it with probability e^−Δ/T, and otherwise stays put and picks again a minute later. This is annealing at a constant temperature T, where the energy is the height above sea level and a move is going along a street.

The tourist strolls for ever. What share of the minutes is spent at each crossing?

Input

The first line holds the numbers n, m and T: crossings, streets and the temperature in metres (2 ≤ n ≤ 50,000, 1 ≤ m ≤ 100,000, 1 ≤ T ≤ 10⁶). The second holds the crossings’ heights h₁, …, h_n, integers from 0 to 10⁶ metres. Then m lines of two numbers a b: a street between crossings a and b, walkable in both directions. No street connects a crossing to itself, there are no two streets between the same pair of crossings, and every crossing can be reached from every other.

Output

n numbers separated by spaces or newlines: the share of time the tourist spends at crossings 1, …, n. The answer is accepted if each number differs from the exact one by at most 10⁻⁶.

Examples

Example 1

Input

3 2 1
700 700 700
1 2
2 3

Output

0.2500000000
0.5000000000
0.2500000000

Example 2

Input

Output

0.6858226237
0.1682000290
0.0841000145
0.0618773327

Limits

Time · Python: 6000 ms
Time · Go: 2000 ms
Memory: 256 MB
Judging: 10 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

Start with the first example. All three crossings are at the same height, so the tourist takes whichever street is chosen. Why does the middle crossing get half the time and not a third? Count how many times in a long stroll the tourist arrives at the middle crossing and how many times at the end ones.

2Hint 2

Suppose the share of crossing v is proportional to deg(v)·e^−h(v)/T, where deg(v) is its number of streets, and check: does as much probability flow along each street per minute one way as the other?

3The idea

Let π(v) = deg(v)·e^−h(v)/T / Z. Take a street between u and v. From u the tourist chooses it with probability 1/deg(u) and takes it with probability min(1, e^{−(h(v) − h(u))/T}). The probability flow along the street from u to v:

π(u) · (1/deg(u)) · min(1, e^{−(h(v) − h(u))/T}) = min(e^−h(u)/T, e^−h(v)/T) / Z.

The degree cancelled, and the expression is symmetric: the reverse flow is the same. So π is stationary, just as in the proof of the theorem on the Boltzmann distribution in the article, only there all states had the same number of neighbours, and the factor deg(v) was common. The graph is connected, so the stationary distribution is unique, and the share of time at each crossing over an infinitely long stroll equals it (this is the ergodic theorem for Markov chains; it holds even when the walk goes in a cycle, as in the first example, where the tourist alternates between the middle crossing and the end ones).

The lesson for annealing: if states have different numbers of neighbours, the walk at a constant temperature prefers states with more neighbours. To restore the pure Boltzmann distribution, a move from u to v is accepted with probability min(1, deg(u)/deg(v)·e^{−(h(v) − h(u))/T}): this is the Hastings correction (1970).

4Walkthrough

Compute the degrees, subtract the smallest height from all heights, take the weights deg(v)·e^{−(h(v) − h_min)/T} and divide by their sum. Subtracting the minimum is essential: in the third test the height difference is a million metres with T = 1, and without the subtraction all the weights become zero.

In the second example the low crossing has three streets and weight 3, the two at height 2 have weights 2e⁻¹ and e⁻¹, the highest one 2e⁻²; the sum is 4.374, and the low crossing gets 0.686 of the time. Without the degree correction it would be 0.534.

4+Solution

5Complexity

O(n + m): one pass over the streets to count the degrees and one over the crossings.

6Common mistakes

Pure Boltzmann e^−h/T. Correct only when all crossings have the same number of streets. On the very first example it gives a third each instead of ¼, ½, ¼.
The exponential without subtracting the minimum. e^−10⁶ in floating point is zero, and so is the sum of the weights.
Simulating the stroll. Shares computed from a random stroll converge as 1/√(the number of steps): an accuracy of 10⁻⁶ needs trillions of steps. And at a low temperature the stroll also gets stuck in lowlands for a long time: the same thing as the trap in the article.
The power method, multiplying the distribution by the transition matrix until it stops changing. On the cold tests it converges slowly for the same reason; the formula is more accurate and faster.

Algorithms behind it

RND Algorithm Simulated annealing Local search that accepts worsening moves with probability e^(−Δ/T) and gradually cools down. O(S · c) 2 problems RND Technique Random walks A random step at every crossing: √t, the time to a goal, “who gets there first”, and 2-SAT by a random walk. O(1) per step 2 problems