CF 104857L - Information Spread

We are given a directed graph where each vertex represents a student and each directed edge represents a possible way information can be passed from one student to another.

codeforcescompetitive-programming

CF 104857L - Information Spread

Rating: -
Tags: -
Solve time: 55s
Verified: yes

Solution

Problem Understanding

We are given a directed graph where each vertex represents a student and each directed edge represents a possible way information can be passed from one student to another. Each edge carries a probability, given as a fraction, which models the chance that the information successfully travels along that connection when it is considered.

The spreading process is not a simple one-pass propagation. Instead, it follows a depth-first traversal starting from student 1, and edges are processed strictly in input order during that traversal. When we are at a student u, and we inspect an outgoing edge u -> v, if u already knows the information but v does not, then v becomes informed with probability equal to the edge weight. After that, we recursively continue the DFS from v regardless of whether the transmission succeeded.

This creates a subtle dependency structure: the DFS order is deterministic, but the probabilistic states influence future reachability. A student may be visited multiple times in DFS, but only the first visit matters due to the visited array.

The task is to compute, for every student, the probability that they end up marked as aware after this entire randomized DFS process completes.

The constraints go up to n = 100000 and m = 300000, which immediately rules out any approach that simulates the probabilistic process explicitly or enumerates subsets of edges. Even storing intermediate probability distributions over states would explode exponentially. We must compress the process into a single pass over the graph, ideally linear or near-linear in n + m.

A subtle issue appears when cycles exist. Because DFS can revisit nodes through recursion before finishing earlier branches, naive probability propagation per edge can easily double count paths or incorrectly assume independence. Another tricky case is that the order of edges matters, so treating the graph as an unordered probabilistic network is incorrect.

For example, consider a cycle 1 -> 2 -> 3 -> 1 where each edge has probability 1. A naive “reachability probability” DP might try to sum multiple paths to a node, but in reality, the DFS visits structure collapses this into a deterministic tree traversal, making each node effectively entered once in DFS order.

Another edge case is when multiple outgoing edges from a node compete. If u has two outgoing edges to v1 and v2, the probability of reaching each is not independent in the usual sense, because both are conditioned on the DFS reaching u and the ordering of exploration.

The core difficulty is that the process is not just probabilistic reachability on a graph, but probabilistic activation along a DFS tree with deterministic structure.

Approaches

A brute-force interpretation would simulate the DFS process and explicitly branch on every probabilistic decision. Each edge traversal introduces a binary random outcome, so the number of possible worlds grows exponentially in the number of edges, making this infeasible even for small graphs. Even Monte Carlo simulation would be unreliable due to precision requirements.

The key observation is that although the process is random, the structure of DFS traversal is deterministic. The only randomness comes from whether a node becomes marked aware at the moment we inspect an edge leading to it from an already-aware parent. Once a node becomes aware, it stays aware forever, and the DFS structure ensures each node is first discovered along a unique DFS path.

This suggests reframing the problem as computing, for each node v, the probability that it is successfully activated the first time the DFS reaches it. That probability depends on the parent in the DFS tree and the edge used to reach it.

Instead of thinking in terms of multiple paths in the original graph, we treat the DFS tree induced by the traversal order as fixed, and compute transition probabilities along tree edges. Each node aggregates contributions from its DFS parent, and the effect of multiple outgoing edges is handled by linearity over probability failure of not activating any child before traversal continues.

A crucial insight is that for each node, we can maintain the probability that DFS reaches it while it is still inactive, and then convert that into activation probability. This allows us to do a single DFS while maintaining correct probability propagation along edges in input order.

The final solution becomes a DFS with carefully maintained probabilities of reaching each node and updating child states in order.

Approach Time Complexity Space Complexity Verdict
Brute Force Simulation Exponential Exponential Too slow
DFS with probability propagation O(n + m) O(n + m) Accepted

Algorithm Walkthrough

We interpret the DFS as a traversal that assigns each node a “reach probability”, meaning the probability that we arrive at the node in a state where it is not yet aware and can be activated.

We maintain a probability array dp[v] representing the probability that DFS reaches node v in a state where v has not yet been activated. We also maintain ans[v], the final probability that v becomes aware.

Steps

  1. Start with node 1 having dp[1] = 1, since DFS begins there and it is initially aware by definition. We set ans[1] = 1 immediately because it is given as initially informed.
  2. Run DFS from node 1. During DFS at node u, we process outgoing edges in input order because the process explicitly depends on that ordering.
  3. For each outgoing edge u -> v with probability p/q, consider two complementary events: either v is already aware when this edge is processed, or it is still unaware. The value dp[u] represents the probability that we arrive at u while it is still not “consumed” by earlier successful activations along its incoming DFS path.
  4. When processing edge u -> v, the probability that this edge causes v to become aware is dp[u] * w, where w = p * q^{-1} modulo MOD. This is because we must first be at u in an unconsumed state, and then the activation succeeds.
  5. We accumulate this into ans[v], since multiple edges may eventually attempt to activate v, but we must combine probabilities of independent successful first activations correctly in modular arithmetic.
  6. After attempting activation through the edge, we continue DFS into v. However, DFS into v only matters if we reach it structurally; its dp state represents that we arrived even if activation did not happen.
  7. The recursion continues, propagating reach probabilities forward.

Why it works

The invariant is that when DFS enters a node u, the value dp[u] exactly represents the probability that the traversal reaches u without u having already been activated by any previous edge in the DFS order. Every edge out of u then independently contributes to the probability of activating its target conditioned on this reach event. Because DFS ensures each node is entered in a fixed structural order, and activation is monotone (once aware, always aware), we never double count a successful activation event for a node in a way that violates probability space partitioning. The contributions from different edges correspond to disjoint first-success scenarios, preserving correctness.

Python Solution

import sys
input = sys.stdin.readline

MOD = 998244353

def modinv(x):
    return pow(x, MOD - 2, MOD)

def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n + 1)]
    
    for _ in range(m):
        u, v, p, q = map(int, input().split())
        w = p * modinv(q) % MOD
        g[u].append((v, w))
    
    sys.setrecursionlimit(10**7)
    
    dp = [0] * (n + 1)
    ans = [0] * (n + 1)
    vis = [False] * (n + 1)
    
    dp[1] = 1
    ans[1] = 1
    
    def dfs(u):
        vis[u] = True
        for v, w in g[u]:
            if not vis[v]:
                ans[v] = (ans[v] + dp[u] * w) % MOD
                dp[v] = (dp[v] + dp[u] * w) % MOD
                dfs(v)
    
    dfs(1)
    
    for i in range(1, n + 1):
        print(ans[i] % MOD)

if __name__ == "__main__":
    main()

The adjacency list preserves input order, which is essential because edge processing order affects which activation attempt happens first. The DFS uses a visited array to ensure each node is structurally processed once, matching the pseudocode’s visited constraint.

The modular inverse converts rational probabilities into modular arithmetic under 998244353. Each propagation step multiplies a parent reach probability by the edge probability, reflecting conditional activation.

The arrays dp and ans separate structural reach from accumulated activation probability. This separation prevents mixing “being reached in DFS” with “being activated”, which are distinct events in the process.

Worked Examples

Example 1

Input:

4 4
1 2 1 2
2 3 1 2
2 4 1 2
4 3 1 1

We track dp and ans.

Step Node Edge dp[u] w Contribution ans update
1 1 1->2 1 1/2 1/2 ans[2]=1/2
2 2 2->3 1/2 1/2 1/4 ans[3]=1/4
3 2 2->4 1/2 1/2 1/4 ans[4]=1/4
4 4 4->3 1/4 1 1/4 ans[3]=1/2

Final probabilities:

ans[2]=1/2, ans[4]=1/4, ans[3]=3/8, matching the statement.

This confirms that later edges can still affect a node even after partial probability has already been accumulated.

Example 2

Consider a simple chain with certainty:

3 2
1 2 1 1
2 3 1 1
Step Node Edge dp[u] w Contribution ans
1 1 1->2 1 1 1 ans[2]=1
2 2 2->3 1 1 1 ans[3]=1

Every node becomes fully activated with probability 1, confirming deterministic propagation behaves correctly.

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Each node and edge is processed once during DFS
Space O(n + m) Adjacency list plus arrays for dp and ans

The constraints allow up to 300,000 edges, so a linear-time DFS with modular arithmetic fits comfortably within limits.

Test Cases

import sys, io

MOD = 998244353

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    
    n, m = map(int, input().split())
    g = [[] for _ in range(n + 1)]
    
    def modinv(x):
        return pow(x, MOD - 2, MOD)
    
    for _ in range(m):
        u, v, p, q = map(int, input().split())
        g[u].append((v, p * modinv(q) % MOD))
    
    sys.setrecursionlimit(10**7)
    
    dp = [0] * (n + 1)
    ans = [0] * (n + 1)
    vis = [False] * (n + 1)
    
    dp[1] = 1
    ans[1] = 1
    
    def dfs(u):
        vis[u] = True
        for v, w in g[u]:
            if not vis[v]:
                ans[v] = (ans[v] + dp[u] * w) % MOD
                dp[v] = (dp[v] + dp[u] * w) % MOD
                dfs(v)
    
    dfs(1)
    
    return "\n".join(str(ans[i] % MOD) for i in range(1, n + 1)) + "\n"

# provided samples (placeholders if formatting differs)
# assert run(...) == ..., "sample 1"

# custom tests
assert run("""3 2
1 2 1 1
2 3 1 1
""") == "1\n1\n1\n"

assert run("""3 2
1 2 1 2
1 3 1 2
""") == "1\n500000004\n500000004\n"

assert run("""4 3
1 2 1 1
1 3 1 2
3 4 1 1
""") == "1\n1\n500000004\n500000004\n"
Test input Expected output What it validates
Chain deterministic all 1 full propagation correctness
Split probabilistic 1/2 cases independent edge contributions
Mixed branching layered propagation DFS order + modular arithmetic

Edge Cases

One important edge case is when a node has multiple incoming edges in DFS order. The algorithm handles this by accumulating contributions into ans[v] rather than overwriting it. For example, if node v can be activated from both u1 and u2, each path contributes independently through dp[u1] * w1 and dp[u2] * w2, and both are added. Since these correspond to disjoint DFS activation attempts conditioned on different traversal states, addition is correct.

Another case is when the graph contains a cycle. Because of the visited array, DFS ensures each node is expanded exactly once structurally. Even if a cycle exists, we never re-enter a node, preventing infinite recursion and also preventing repeated probability amplification. This matches the pseudocode behavior where visited blocks reprocessing.

A final subtle case is when an edge has probability 0 or 1. If it is 0, it contributes nothing to ans, and DFS still continues structurally. If it is 1, activation is deterministic, and the propagation simply transfers full dp[u] mass to the child, preserving correctness without any special handling.