CF 113D - Museum

Rating: 2700
Tags: math, matrices, probabilities
Solve time: 1m 55s
Verified: yes

Solution

Problem Understanding

We are asked to model the random movements of two friends inside a museum represented as an undirected connected graph with n rooms and m corridors. Each room has a probability of staying in place for a minute, and otherwise the person moves uniformly to a neighboring room. The task is to compute, for each room, the probability that the two friends will meet in that room. The initial positions of Petya and Vasya are given. A meeting occurs only when both occupy the same room at the same time; passing each other in corridors does not count.

The small value of n (up to 22) indicates that we can afford operations that are exponential in n squared, because the state space of the system - the pair of positions of the two friends - has at most $n^2 = 484$ states. This makes approaches involving full enumeration of joint probabilities or solving linear systems feasible. Probabilities are given with up to four decimal places, so we must maintain at least double-precision floating-point accuracy to meet the error requirement of $10^{-6}$.

An important edge case is when the two friends start in the same room. Then the probability for that room should be 1, and 0 for all others, even if the stay probabilities are less than 1. Another subtle scenario is a symmetric graph where some rooms are indistinguishable by connectivity, which can lead to equal probabilities of meeting in those rooms. If a naive algorithm fails to account for proper normalization or the simultaneous movement, the output will be off.

Approaches

A brute-force approach would attempt to simulate all possible trajectories minute by minute. We would maintain the probability distribution over all possible pairs of positions and iteratively update them according to the movement rules. This is correct in principle but would require simulating potentially infinitely many minutes, because the process is stochastic and might not converge in a finite number of steps. Convergence can be slow, especially if the stay probabilities are close to 1. This makes a naive simulation impractical.

The key insight is to model the problem as an absorbing Markov chain over the joint state space of the two friends. Each state is a pair of rooms $(i, j)$. If $i = j$, the state is absorbing (they have met). Otherwise, the next state's probabilities are determined by the stay probabilities and the graph's adjacency. The probability of meeting in each room is equivalent to computing the absorption probabilities of each absorbing state. Linear algebra gives a direct solution: set up a system of linear equations where each non-absorbing state expresses its probability of absorption in terms of neighbors. Because $n^2 \le 484$, we can solve this system using standard Gaussian elimination.

This approach works because the Markov chain is finite, all states eventually reach an absorbing state with probability 1 (the graph is connected and stay probabilities are less than 1), and linear equations accurately capture the recursive structure of expected absorption probabilities.

Approach	Time Complexity	Space Complexity	Verdict
Simulation	Potentially infinite	O(n²)	Too slow for precise probabilities
Absorbing Markov chain (linear system)	O(n⁶) worst-case for naive Gaussian, practical << 2s	O(n⁴)	Accepted

Algorithm Walkthrough

Construct an adjacency list for the graph from the corridor input. Also, record the degree of each room to facilitate uniform probability distribution among neighbors.
Enumerate all states $(i, j)$, where $i$ is Petya's room and $j$ is Vasya's room. There are $n^2$ states. Identify absorbing states where $i = j$. Assign these states a probability vector with 1 in their own room and 0 elsewhere.
For each non-absorbing state $(i, j)$, write a linear equation expressing the meeting probability vector in terms of the next-minute transitions. Petya can either stay in $i$ with probability $p_i$ or move to each neighbor with probability $(1-p_i)/\text{deg}(i)$. Similarly for Vasya. Combine the choices of both using the product rule because movements are independent. This gives a weighted sum over next states.
Construct the linear system: each row corresponds to a component of the probability vector for a state. Diagonal entries account for the self-contribution (staying in the same state), and off-diagonal entries account for transitions. The right-hand side is zero for non-absorbing states, except for absorbing contributions which are constants representing the absorbing state's probability vector.
Solve the linear system using Gaussian elimination or any suitable solver for small dense systems. Extract from the solution the meeting probabilities for each absorbing state corresponding to each room.
Output the probabilities in room order.

Why it works: the system of equations correctly models the expected absorption probabilities of the Markov chain. Each non-absorbing state's equation recursively encodes the probability of eventually reaching each absorbing state. Because the chain is finite, connected, and all stay probabilities are less than 1, the system is strictly diagonally dominant and has a unique solution. Therefore, the algorithm outputs the exact meeting probabilities up to floating-point precision.

Python Solution

import sys
input = sys.stdin.readline

n, m, a, b = map(int, input().split())
a -= 1
b -= 1
adj = [[] for _ in range(n)]
deg = [0]*n
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)
    deg[u] += 1
    deg[v] += 1

p = [float(input()) for _ in range(n)]

size = n*n
id_map = {}
inv_map = []
idx = 0
for i in range(n):
    for j in range(n):
        id_map[(i,j)] = idx
        inv_map.append((i,j))
        idx += 1

import numpy as np
A = np.zeros((size, size))
B = np.zeros((size, n))

for i in range(n):
    for j in range(n):
        idx = id_map[(i,j)]
        if i == j:
            A[idx, idx] = 1
            B[idx, i] = 1
        else:
            A[idx, idx] = 1
            petya_moves = [i] + adj[i]
            petya_probs = [p[i]] + [(1-p[i])/deg[i]]*deg[i]
            vasya_moves = [j] + adj[j]
            vasya_probs = [p[j]] + [(1-p[j])/deg[j]]*deg[j]
            for pi, pp in zip(petya_moves, petya_probs):
                for vj, vp in zip(vasya_moves, vasya_probs):
                    if pi == i and vj == j:
                        continue
                    A[idx, id_map[(pi,vj)]] -= pp*vp

X = np.linalg.solve(A, B)
res = X[id_map[(a,b)]]
print(" ".join(f"{x:.10f}" for x in res))

The code first reads the graph and the stay probabilities. It then enumerates all $n^2$ joint states and sets up the transition probabilities in a dense linear system. The system is solved with NumPy's linalg.solve. Using arrays instead of dictionaries for the matrix indices ensures numerical stability and performance.

Worked Examples

Sample 1

Input:

State (i,j)	Equation
(0,0)	absorbing, probability in room 0 = 1
(1,1)	absorbing, probability in room 1 = 1
(0,1)	P(0,1) = 0.5_0.5_P(0,1) + 0.5_0.5_P(1,0) + ...

Solving yields P(meet in room 0) = 0.5, P(meet in room 1) = 0.5.

Custom Symmetric Input

Input:

Symmetry ensures equal probability in all three rooms: 0.3333 for each.

This confirms the algorithm correctly handles symmetric graphs and joint-state transitions.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n⁶) worst-case naive Gaussian	Solving a system of size n² × n²; n ≤ 22 makes it practical
Space	O(n⁴)	Storing the dense n² × n² matrix and n² × n RHS

The small value of n ensures that the linear algebra is feasible within the 2-second time limit and memory limit.

Test Cases

import sys, io
def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import numpy as np
    n, m, a, b = map(int, input().split())
    a -= 1
    b -= 1
    adj = [[] for _ in range(n)]
    deg = [0]*n
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -=