Solution Explanation

We are given $m$ metro lines and $n$ stations. Each line is represented by a subset of stations. Player $B$ can ask questions of the form: "Does the hidden line stop at station $s$?" The answer is always yes or no.

The goal is to minimize the expected number of questions needed to determine the hidden line. If two lines have identical sets of stations, they can never be distinguished, and the answer is not possible.

—

Key Idea

Let $S$ be the set of candidate lines that could still be the hidden line.

1. If |S| = 1, no questions are needed: [ dp(S) = 0 ]

2. Otherwise, for each station $s$, we can ask a question. This partitions $S$ into two subsets: [ S_yes = {lines in S that stop at s},  S_no = {lines in S that do not stop at s} ]

3. If both S_{\text{yes}} and S_{\text{no}} are non-empty, the expected number of questions for asking station $s$ is: [ dp_s(S) = 1 + |S_yes||S| dp(S_yes) + |S_no||S| dp(S_no) ]

4. The optimal expected number of questions for state $S$ is: [ dp(S) = _s {0,1,...,n-1} dp_s(S) ]

5. If no station splits $S$, then all lines in $S$ are identical and the answer is not possible.

—

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> line_masks;
map<vector<int>, double> memo;

double dp(vector<int> &lines) {
    if (lines.size() == 1) return 0.0;
    sort(lines.begin(), lines.end());
    if (memo.count(lines)) return memo[lines];

    double res = 1e9;
    bool can_split = false;

    for (int s = 0; s < n; s++) {
        vector<int> yes, no;
        for (int mask : lines) {
            if (mask & (1 << s)) yes.push_back(mask);
            else no.push_back(mask);
        }
        if (!yes.empty() && !no.empty()) {
            can_split = true;
            double val = 1.0 + (yes.size() * dp(yes) + no.size() * dp(no)) / lines.size();
            res = min(res, val);
        }
    }

    if (!can_split) return -1.0; // impossible to distinguish

    memo[lines] = res;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    line_masks.resize(m);
    map<int,int> count_mask;
    for (int i = 0; i < m; i++) {
        int p; cin >> p;
        int mask = 0;
        for (int j = 0; j < p; j++) {
            int s; cin >> s;
            mask |= (1 << s);
        }
        if (count_mask[mask]++) {
            cout << "not possible\n";
            return 0;
        }
        line_masks[i] = mask;
    }

    double ans = dp(line_masks);
    if (ans < 0) cout << "not possible\n";
    else cout << fixed << setprecision(10) << ans << "\n";

    return 0;
}

—

Complexity

1. Each state corresponds to a set of remaining lines and is evaluated only once due to memoization.

2. Each state considers at most n \le 18 stations for splitting.

3. For m \le 50, the total number of states is small enough to compute efficiently.

—

Summary

1. Convert each line to an $n$-bit mask representing the stations it stops at.

2. Check for duplicate lines. If any exist, output not possible.

3. Use memoized DP on remaining subsets of lines to compute the minimal expected number of questions.

4. Output the result with precision at least 10^{-4}.