Overview

This problem asks us to find the average satisfaction score across all simple paths (paths that don’t visit the same vertex twice) from start vertex \(S\) to end vertex \(T\) on a graph. We use bitmask DP to efficiently compute the total score sum across all paths and the number of paths.

Analysis

Naive Approach and Its Issues

The most intuitive method is to enumerate all simple paths from \(S\) to \(T\), compute the score of each path, and take the average. However, in the case of a complete graph with \(N\) vertices, the number of simple paths can be as large as \((N-2)!\) in the worst case, which for \(N = 18\) becomes \(16! \approx 2 \times 10^{13}\), making full enumeration far too slow.

Key Insight: State Compression

What matters for a simple path is “which vertex we are currently at” and “which vertices have already been visited.” By representing the set of visited vertices as a bitmask (an \(N\)-bit integer), the number of states is at most \(2^N \times N\). Even for \(N = 18\), this is about \(2^{18} \times 18 \approx 4.7\) million, which is perfectly manageable.

Technique: Directly Managing the Score Sum

We manage not only the “number of paths” but also the “sum of scores” simultaneously in the DP. When there are \(cnt\) paths reaching a state \((mask, cur)\) with a total score sum of \(scr\), moving to the next vertex \(v\) gives:

• New path count: \(cnt\) paths are carried over as-is
• New score sum: \(scr + cnt \times cost[v]\) (the satisfaction of spot \(v\) is added to each of the \(cnt\) paths)

Algorithm

1. State Definition: \(dp\_count[(mask, cur)]\) = number of paths where the visited set is \(mask\) and the current position is \(cur\). \(dp\_score[(mask, cur)]\) = the sum of scores (cumulative satisfaction so far) across all such paths.

2. Initial State: When \(mask = \{S\}\) (the set with only \(S\)’s bit set) and \(cur = S\): \(dp\_count = 1\), \(dp\_score = c_S\).

3. Transition: Process \(mask\) values in increasing order. From state \((mask, cur)\), transition to each adjacent vertex \(v\) of \(cur\) that is not in \(mask\).

   • \(new\_mask = mask \cup \{v\}\)
   • \(dp\_count[(new\_mask, v)]\) += \(cnt\)
   • \(dp\_score[(new\_mask, v)]\) += \(scr + cnt \times cost[v]\)

4. Termination Condition: A state where \(cur = T\) means the path is complete, so no further transitions are made from it. The path count and score sum upon reaching \(T\) are accumulated.

5. Answer: Total score sum of all collected paths ÷ total number of paths.

Concrete Example

If \(S=1, T=3\) and there are two paths \(1 - 2 - 3\) and \(1 - 3\): - Path \(1 \to 3\): score = \(c_1 + c_3\) - Path \(1 \to 2 \to 3\): score = \(c_1 + c_2 + c_3\) - Average = \(\frac{(c_1 + c_3) + (c_1 + c_2 + c_3)}{2}\)

Complexity

• Time complexity: \(O(2^N \times N^2)\) (for each of the \(2^N \times N\) states, searching adjacent vertices takes at most \(O(N)\))
• Space complexity: \(O(2^N \times N)\) (only reachable states are stored using a dictionary)

Implementation Notes

• Fast enumeration of adjacent vertices using bit operations: Obtain the bitmask of unvisited adjacent vertices with adj[cur] & ~mask, then extract them one by one from the lowest bit using the technique v = (neighbors & -neighbors).bit_length() - 1.

• Stop transitions at \(cur = T\): By not extending paths that have reached the endpoint, we correctly count only simple paths from \(S\) to \(T\).

• Sparse state management using a dictionary: This saves memory and time when many states are unreachable.

• Conversion to 0-indexed: Internally, vertex numbers are converted to \(0, 1, \ldots, N-1\) for convenience of bitmask operations.

  Source Code

import sys
from functools import lru_cache

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    S = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    c = [0] * (N + 1)
    for i in range(1, N + 1):
        c[i] = int(input_data[idx]); idx += 1
    
    # Adjacency as bitmask (0-indexed internally)
    adj = [0] * N
    for j in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        adj[u - 1] |= (1 << (v - 1))
        adj[v - 1] |= (1 << (u - 1))
    
    # Convert S, T to 0-indexed
    S -= 1
    T -= 1
    
    # dp[visited_mask][current_node] = (count_of_paths, sum_of_scores)
    # We use memoization with bitmask DP
    # visited_mask includes all visited nodes including current
    
    # We'll do iterative DP or recursive with lru_cache
    # State: (mask, cur) where mask is the set of visited nodes, cur is current position
    # Transition: move to neighbor not in mask
    
    # If cur == T, we have a complete path (don't extend further)
    
    cost = [0] * N
    for i in range(N):
        cost[i] = c[i + 1]
    
    # dp[mask][cur] = (number_of_paths_from_cur_to_T, total_score_sum_of_remaining_path_including_cur)
    # Actually, let's think forward:
    # Let's accumulate from S.
    # State: (mask, cur) - mask is visited set, cur is where we are
    # For each state, count = number of simple paths from cur to T using only unvisited nodes
    # score_sum = sum of scores of all such paths (where score includes all nodes from S to T)
    
    # Better approach: enumerate paths from S to T
    # dp[mask][cur]: number of paths that visited exactly 'mask' nodes and ended at 'cur'
    #                and the total accumulated score sum across all such paths
    
    # Initialize: mask = {S}, cur = S, count=1, score_sum = cost[S]
    # Transition: from (mask, cur), go to neighbor v not in mask
    #   new_mask = mask | (1 << v)
    #   new_count += count
    #   new_score_sum += score_sum + count * cost[v]  (each of the 'count' paths gains cost[v])
    
    # Answer: sum over all masks where T is in mask, of dp[mask][T].score_sum / dp[mask][T].count total
    # Actually: total_score = sum of score_sum for all (mask, T), total_count = sum of count for all (mask, T)
    # answer = total_score / total_count
    
    # Use dictionary or array. With N<=18, mask up to 2^18 = 262144, nodes up to 18
    # Total states: 2^18 * 18 ~ 4.7M, manageable
    
    size = 1 << N
    # Use arrays: dp_count[mask][cur], dp_score[mask][cur]
    # Too much memory for full array? 262144 * 18 = ~4.7M entries, fine with dicts or arrays
    
    # Let's use dictionaries keyed by (mask, cur) for efficiency since many states are unreachable
    
    dp_count = {}
    dp_score = {}
    
    init_mask = 1 << S
    dp_count[(init_mask, S)] = 1
    dp_score[(init_mask, S)] = cost[S]
    
    total_count = 0
    total_score = 0
    
    # BFS/iteration in order of popcount of mask
    from collections import deque
    queue = deque()
    queue.append((init_mask, S))
    
    # We need to process each state once. Use a set or process by mask order.
    # Better: iterate over masks in order (increasing), then nodes.
    
    # Rebuild with iteration over masks
    for mask in range(size):
        for cur in range(N):
            if (mask, cur) not in dp_count:
                continue
            cnt = dp_count[(mask, cur)]
            scr = dp_score[(mask, cur)]
            
            if cur == T:
                total_count += cnt
                total_score += scr
                continue  # Don't extend past T
            
            neighbors = adj[cur] & ~mask
            while neighbors:
                v = (neighbors & -neighbors).bit_length() - 1
                neighbors &= neighbors - 1
                new_mask = mask | (1 << v)
                key = (new_mask, v)
                if key in dp_count:
                    dp_count[key] += cnt
                    dp_score[key] += scr + cnt * cost[v]
                else:
                    dp_count[key] = cnt
                    dp_score[key] = scr + cnt * cost[v]
    
    print(f"{total_score / total_count:.10f}")

main()

This editorial was generated by claude4.6opus-thinking.