Overview

This problem involves dividing \(N\) computers into several groups (subnetworks) and minimizing the “total number of affected computers” that results when a virus’s infection targets are entirely contained within the same group.

Since the number of computers \(N\) is at most \(15\), which is very small, we can efficiently solve this within the time limit by combining dynamic programming using bitmasks (Bitmask DP) with Sum Over Subsets DP (SOS DP), which quickly aggregates information over subsets.

---

Analysis

1. State Representation (Bitmask)

Since the number of computers \(N\) is at most \(15\), we can represent “sets of computers” — such as which computers belong to which group or which computers are affected — as integers (bitmasks) from \(0\) to \(2^N - 1\). For example, with \(N=4\), the set of computers \(\{1, 3\}\) is represented as 0101 in binary (which is \(5\) in decimal).

2. Computing Damage Within a Single Group

Consider a set of computers \(G\) (as a bitmask) forming “one group,” and determine which computers in that group are affected.

Let \(S_j\) be the set of infection targets for virus \(j\). The condition for virus \(j\) to spread within group \(G\) is that \(S_j\) is a subset of \(G\) (\(S_j \subseteq G\)). Therefore, the set of affected computers \(U[G]\) within group \(G\) can be expressed as:

\[U[G] = \bigcup_{S_j \subseteq G} S_j\]

If we naively compute this for all \(G\) (\(0 \le G < 2^N\)), it requires \(O(M \cdot 2^N)\) time since we scan \(M\) viruses for each group. With \(N=15, M=500\), this is \(500 \times 32768 \approx 1.6 \times 10^7\) operations, which would fit within the time limit on its own. However, for a more elegant and faster approach, we use Sum Over Subsets DP (SOS DP).

3. Optimizing the Group Partition (Bitmask DP)

Let \(dp[S]\) be the minimum number of affected computers when the set of computers \(S\) is optimally divided into groups.

When partitioning set \(S\), we fix one group as \(T\) (\(T\) is a non-empty subset of \(S\), \(T \subseteq S\)). Assuming the remaining set \(S \setminus T\) is already optimally partitioned, the following recurrence (DP transition) holds:

\[dp[S] = \min_{T \subseteq S, T \neq \emptyset} \left( dp[S \setminus T] + \text{cost}[T] \right)\]

Here, \(\text{cost}[T]\) is the number of affected computers within group \(T\) (the number of set bits in \(U[T]\)). By performing this transition for all \(S\), we can obtain the final answer \(dp[2^N - 1]\) (the minimum number of affected computers when all computers are optimally grouped).

---

Algorithm

The program operates in the following 4 steps.

Step 1: Initialization of Virus Information

Convert each virus \(j\)’s infection targets \(S_j\) into a bitmask. Prepare an array U (of size \(2^N\), initialized to \(0\)), and for each virus, take the logical OR so that U[S_j] = S_j.

Step 2: Propagation of Affected Sets via SOS DP

To compute the logical OR of all \(S_j\) where \(S_j \subseteq G\), we perform the Sum Over Subsets transformation. After this, for every mask, the union of infection targets of all viruses whose target sets are subsets of mask is stored in U[mask].

for (int i = 0; i < N; ++i) {
    for (int mask = 0; mask < (1 << N); ++mask) {
        if ((mask >> i) & 1) {
            U[mask] |= U[mask ^ (1 << i)];
        }
    }
}

Step 3: Precomputation of Damage Count for Each Group

For each mask, compute the number of affected computers cost[mask]. This equals the number of set bits (popcount) in U[mask].

\[\text{cost}[\text{mask}] = \text{popcount}(U[\text{mask}])\]

Step 4: Bitmask DP with Subset Enumeration

Prepare a DP table dp (of size \(2^N\), initialized to a sufficiently large value, with dp[0] = 0). For each mask, efficiently enumerate its subsets sub and perform the DP transitions.

---

Complexity

Time Complexity

• Step 1 (Reading virus data): \(O(M + \sum k_j)\)
• Step 2 (SOS DP): \(O(N \cdot 2^N)\)
• Step 3 (Popcount computation): \(O(2^N)\)
• Step 4 (Subset enumeration DP): The computational cost of enumerating all subsets \(T\) of set \(S\) is, by the binomial theorem, \(\sum_{i=0}^{N} \binom{N}{i} 2^i = (1 + 2)^N = 3^N\).

Therefore, the overall time complexity is \(O(M + N \cdot 2^N + 3^N)\). When \(N = 15\), \(3^{15} \approx 1.4 \times 10^7\), which runs sufficiently fast within the execution time limit (typically 2.0 seconds), finishing in just a few milliseconds.

Space Complexity

• The arrays U, cost, and dp all have size \(2^N\). Therefore, the space complexity is \(O(2^N)\). When \(N = 15\), only \(2^{15} = 32768\) int-type variables (approximately 128 KB) are used, making it very safe with respect to the memory limit.

---

Implementation Notes

1. Fast Subset Enumeration

We use a well-known technique to enumerate all non-empty subsets sub of a bitmask mask in descending order, considering only positions where bits are set.

for (int sub = (mask - 1) & mask; sub > 0; sub = (sub - 1) & mask) {
    // sub iterates over subsets of mask (excluding mask itself and the empty set)
}

By using this technique, we skip unnecessary states (states where bits not in mask are set), and complete all transitions in exactly \(O(3^N)\).

2. Fast Popcount

By using std::popcount from the <bit> header introduced in C++20, the CPU’s dedicated instruction (POPCNT) is invoked, allowing bit counting in \(O(1)\).

Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <bit>

using namespace std;

int main() {
    // Optimize input/output operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<int> U(1 << N, 0);
    for (int j = 0; j < M; ++j) {
        int k;
        cin >> k;
        int mask = 0;
        for (int i = 0; i < k; ++i) {
            int s;
            cin >> s;
            --s; // Convert to 0-indexed
            mask |= (1 << s);
        }
        U[mask] |= mask;
    }

    // SOS (Sum Over Subsets) DP to propagate virus masks to their supersets
    for (int i = 0; i < N; ++i) {
        for (int mask = 0; mask < (1 << N); ++mask) {
            if ((mask >> i) & 1) {
                U[mask] |= U[mask ^ (1 << i)];
            }
        }
    }

    // Precompute the cost (number of infected computers) for each subset
    vector<int> cost(1 << N);
    for (int mask = 0; mask < (1 << N); ++mask) {
        cost[mask] = std::popcount(static_cast<unsigned int>(U[mask]));
    }

    // DP to find the minimum infected computers by partitioning the network
    vector<int> dp(1 << N, 1e9);
    dp[0] = 0;
    for (int mask = 1; mask < (1 << N); ++mask) {
        dp[mask] = cost[mask];
        // Iterate through all non-empty submasks of 'mask'
        for (int sub = (mask - 1) & mask; sub > 0; sub = (sub - 1) & mask) {
            dp[mask] = min(dp[mask], dp[mask ^ sub] + cost[sub]);
        }
    }

    cout << dp[(1 << N) - 1] << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.