// O(M * N * 2^N) // Not deeply checked/tested yet. // Same as raphael_v1, but no division in the DP for efficiency. #include #include #include #include #include #include #include #include #include // #include using namespace std; using LineCounts = vector>; using Memo = vector>; LineCounts precompute(const vector &lines, int N) { // Vector indexed by a bitset with the k bits at the positions // corresponding to the stations that have a constraint. There are 2^N // such indexes. // Map indexed by a bitset with 0 or 1 at the i-th position (for all // i's where the vector index bitset has a 1), whether the line must // through the i-th station. We only fill values for bitsets with at // least one line. There are at most M such values. // Total size is therefore at most M * 2^N. LineCounts line_counts(1ULL << N); assert(!lines.empty()); assert(N <= 64); for (const uint64_t &line : lines) { for (uint64_t mask = 0; mask < (1ULL << N); ++mask) { ++line_counts[mask][line & mask]; } } return line_counts; } int get_line_count(uint64_t constraint_locations, uint64_t constraints, const LineCounts &line_counts) { const auto &with_locations = line_counts[constraint_locations]; auto it = with_locations.find(constraints); return it == with_locations.end() ? 0 : it->second; } // This is similar to dp_v1 in raphael_v1.cpp, except that it returns the // minimum number of questions that needs to be asked given the // contraints, multiplied by the number of lines matching the // constraints. // This effectively removes all denominators in the computations which // become the minimum over all i's (where the i-th bit of // constraint_locations is 0) of: // // card({line | line matches 'contraints_locations' and // 'constraints'}) + card({line | line does not pass through station i // and matches 'contraints_locations' and 'constraints'}) * // dp_no_div(updated state where we asked for station i and the line // to guess does not pass through it) + card({line | line does pass // through station i and matches 'contraints_locations' and // 'constraints'}) * dp_v1(updated state where we asked for station i // and the line to guess does pass through it). // // One just needs to divide the final result by M to get the minimum // number of questions to ask. double dp_no_div(uint64_t constraint_locations, uint64_t constraints, int N, const LineCounts &line_counts, Memo &memo) { const int cur_line_count = get_line_count(constraint_locations, constraints, line_counts); if (cur_line_count <= 1) return 0; // Can decide without any additional question. auto &memo_with_locations = memo[constraint_locations]; auto it = memo_with_locations.find(constraints); if (it != memo_with_locations.end()) return it->second; double res = numeric_limits::max(); for (int i = 0; i < N; ++i) { if ((constraint_locations >> i) & 1) { // There is already a constraint for station i. continue; } const uint64_t new_constraint_locations = constraint_locations | (1ULL << i); // Ask question about station i. res = min(res, cur_line_count + // Line passes through station i. dp_no_div(new_constraint_locations, constraints | (1ULL << i), N, line_counts, memo) + // Line does not pass through station i. dp_no_div(new_constraint_locations, constraints, N, line_counts, memo)); } // cout << bitset<10>(constraint_locations) << " " << // bitset<10>(constraint_locations) << " " << res << endl; return (memo_with_locations[constraints] = res); } int main() { while (cin.peek() == '#' || cin.peek() == '/') { string s; getline(cin, s); } int N; cin >> N; assert(N <= 64); // For bit masks to fit in an uint64_t. int M; cin >> M; vector lines; for (int i = 0; i < M; ++i) { uint64_t line = 0; int num_stations; cin >> num_stations; for (int j = 0; j < num_stations; ++j) { int station; cin >> station; assert(station >= 0); assert(station < N); uint64_t station_mask = 1ULL << station; // Duplicate station. assert((line & station_mask) == 0); line |= station_mask; } lines.push_back(line); } double t = time(nullptr); LineCounts line_counts = precompute(lines, N); // cout << "precompute time: " << time(nullptr) - t << endl; t = time(nullptr); Memo memo; memo.resize(1ULL << N); double res = dp_no_div(0, 0, N, line_counts, memo) / M; // cout << "DP time: " << time(nullptr) - t << endl; if (res > 2 * N) { cout << "not possible" << endl; } else { cout << std::setprecision(15) << res << endl; } }