Overview

This problem involves dividing a small number of computers (\(N \leq 15\)) into groups and minimizing the total number of computers affected by viruses. By precomputing the damage within each group and using Bit DP (Subset DP) to search for the optimal grouping (partition of a set), we can solve this problem.

---

Analysis

1. Independence of Damage Within Groups

Suppose we partition the set of computers into groups \(T_1, T_2, \ldots, T_k\) (which are mutually disjoint and whose union is the entire set). Virus \(j\) with infection target \(S_j\) causes damage only when \(S_j\) is entirely contained within one group \(T_i\) (i.e., \(S_j \subseteq T_i\)).

Therefore, when a group \(T\) is formed, the set of computers damaged within that group is: $\(U(T) = \bigcup_{S_j \subseteq T} S_j\)\( If we define the number of damaged computers in group \)T\( as \)C[T] = |U(T)|\(, then the total number of damaged computers for the entire partition is the sum of damages across all groups: \)\sum C[T_i]$.

2. Efficient Computation of \(C[T]\) (Introduction of SOS DP)

If we naively compute \(C[T]\) for all \(T\) (\(0 \leq T < 2^N\)), the computation cost is \(O(M \cdot 2^N)\) since the number of viruses \(M\) can be up to 500. For \(N=15\), \(2^{15} = 32,768\), so this would still be fast enough, but for a smarter and faster approach, we use SOS DP (Sum Over Subsets DP / Fast Zeta Transform).

For each virus \(j\), we set the initial value as W[S_j] = S_j (represented as a bitmask). Then, by accumulating the “union over subsets” in the style of SOS DP, we can compute the logical OR (union) W[T] of all \(S_j\) satisfying \(S_j \subseteq T\) for all \(T\) in \(O(N 2^N)\) time. \(C[T]\) is the number of set bits (popcount) in W[T].

3. Optimizing the Group Partition (Bit DP)

Let dp[S] be the minimum number of damaged computers when partitioning the set of computers \(S\) into groups. Considering extracting one group \(T\) (\(T \subseteq S\) and \(T \neq \emptyset\)) from set \(S\), the transition formula is: $\(\text{dp}[S] = \min_{T \subseteq S, T \neq \emptyset} (C[T] + \text{dp}[S \setminus T])\)$

If we perform this transition straightforwardly, we enumerate all subsets \(T\) for every \(S\), resulting in \(O(3^N)\) time complexity. Since \(3^{15} \approx 1.43 \times 10^7\), this is well within the time limit.

Furthermore, to eliminate redundancy from the order of group extraction (e.g., splitting into \(\{1, 2\}\) and \(\{3\}\) vs. \(\{3\}\) and \(\{1, 2\}\)), we apply the optimization of “only choosing groups \(T\) that always include the rightmost set bit (LSB) of \(S\)”. This reduces the number of transitions explored by approximately half.

---

Algorithm

Step 1: Convert Virus Information to Bitmasks

Convert the infection target \(S_j\) of each virus \(j\) into a bit array (integer value) mask.

Step 2: Compute \(C[T]\) Using SOS DP

1. Initialize an array W of size \(2^N\) with \(0\).
2. For each virus \(j\)’s mask, set W[mask] |= mask.
3. Using the following loop (SOS DP), compute the union of infection targets for all viruses that are subsets of each mask:

   
   for i in range(N):
      for mask in range(1 << N):
          if (mask >> i) & 1:
              W[mask] |= W[mask ^ (1 << i)]
   

4. For each \(T\), compute C[T] = popcount(W[T]).

Step 3: Search for Minimum Using Bit DP

1. Initialize the dp array with \(0\).
2. Iterate \(S\) from \(1\) to \(2^N - 1\) in ascending order.
3. Obtain the LSB (least significant bit) of \(S\) as lsb = S & -S, and set the remaining set as rem = S ^ lsb.
4. Enumerate subsets T_prime of rem using bit operations, and perform transitions by extracting T = T_prime | lsb as one group. $\(\text{dp}[S] = \min_{T' \subseteq \text{rem}} (C[T' \cup \{\text{lsb}\}] + \text{dp}[\text{rem} \setminus T'])\)$
5. The final answer is dp[(1 << N) - 1].

---

Complexity

• Time Complexity: \(O(M + N 2^N + 3^N)\)

  • Input processing and initialization of viruses: \(O(M)\)
  • Computing W via SOS DP: \(O(N 2^N)\)
  • Transitions via Bit DP: \(O(3^N)\)
  • For \(N = 15, M = 500\), the total number of operations is approximately \(1.5 \times 10^7\), which runs fast enough even in Python.

• Space Complexity: \(O(2^N)\)

  • The sizes of the W, C, and dp tables are all \(2^N\).
  • For \(N = 15\), we only store \(2^{15} = 32,768\) integers, so the memory usage is extremely small at just a few megabytes.

---

Implementation Notes

1. Fast Enumeration of Subsets: When enumerating subsets T_prime of a set rem in descending order, the following bit manipulation technique is used:

   T_prime = rem
   while T_prime > 0:
      # (Processing for T_prime)
      T_prime = (T_prime - 1) & rem
   

   Using this technique, efficient subset enumeration targeting only set bits is possible in \(O(3^N)\).

2. Constant Factor Speedup via Redundancy Elimination: By using lsb to only extract groups that “always include a specific element,” we narrow the transition search space and completely prevent wasteful redundant computations.

   Source Code

import sys

def main():
    # 入力を一度にすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    idx = 2
    masks = []
    for _ in range(M):
        k = int(input_data[idx])
        idx += 1
        mask = 0
        for _ in range(k):
            v = int(input_data[idx]) - 1
            idx += 1
            mask |= (1 << v)
        masks.append(mask)
        
    # SOS DP (Sum Over Subsets) を用いて、各部分集合 T に対して
    # T に完全に含まれるウイルスの感染対象の和集合のマスク W[T] を計算する
    W = [0] * (1 << N)
    for mask in masks:
        W[mask] |= mask
        
    for i in range(N):
        for mask in range(1 << N):
            if (mask >> i) & 1:
                W[mask] |= W[mask ^ (1 << i)]
                
    # popcount テーブルの作成
    popcount = [0] * (1 << N)
    for i in range(1 << N):
        popcount[i] = popcount[i >> 1] + (i & 1)
        
    # 各部分集合 T が1つのグループを形成したときの、そのグループ内での被害台数 C[T]
    C = [popcount[W[i]] for i in range(1 << N)]
    
    # DP[S]: コンピュータの集合 S をいくつかのグループに分けたときの最小被害台数
    dp = [0] * (1 << N)
    for S in range(1, 1 << N):
        # S のうち最も右にある立っているビット (LSB) を取り出す
        # LSB を含むグループ T を選ぶことで、重複を排除し遷移数を約半分にする
        lsb = S & -S
        rem = S ^ lsb
        val = C[lsb] + dp[rem]
        
        # rem の部分集合 T_prime を列挙する
        T_prime = rem
        while T_prime > 0:
            v = C[T_prime | lsb] + dp[rem ^ T_prime]
            if v < val:
                val = v
            T_prime = (T_prime - 1) & rem
        dp[S] = val
        
    print(dp[(1 << N) - 1])

if __name__ == '__main__':
    main()

---

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