Overview

This problem asks us to find the minimum cost of selecting from \(N\) given security companies such that all \(M\) facilities are guarded by at least one company. This is a type of the well-known “set cover problem,” but since the number of facilities \(M\) is small, we can solve it efficiently using dynamic programming (DP).

Analysis

1. Considering Brute Force

First, let’s consider brute-forcing all possible selections of security companies. Since each company can either be “selected” or “not selected,” the total number of combinations is \(2^N\). In this problem, \(N \leq 50\), so \(2^{50} \approx 1.12 \times 10^{15}\), which is impossible to compute within the time limit.

2. State Compression (Bit Representation)

On the other hand, focusing on the number of facilities \(M\), we notice that \(M \leq 18\), which is very small. The “state” representing which facilities are guarded has only \(2^M = 2^{18} = 262,144\) possibilities. In this way, representing the state of a set as an integer (bitmask) is an effective technique. Specifically, if facility \(j\) is guarded, we set the \(j\)-th bit to \(1\); otherwise, we set it to \(0\). This allows us to represent the guarding status of all facilities as an integer from \(0\) to \(2^M-1\).

3. Applying Dynamic Programming

By maintaining the “current guarding status” as a state and considering how the state transitions when a new security company is added, we can construct the following DP: - dp[mask]: the minimum cost required to guard the set of facilities represented by mask

When contracting a new security company (with coverage c_mask and cost cost), the current state mask transitions to mask | c_mask (bitwise OR).

Algorithm

Bitmask DP

1. Initialization:
   • Prepare an array dp of length \(2^M\) and initialize it with a very large value (infinity).
   • Set dp[0] = 0 (the cost of guarding no facilities is \(0\)).
2. Transitions:
   • For each security company \(i = 1, \dots, N\), perform the following:
   • Iterate over all current states mask (from \(0\) to \(2^M-1\)).
   • If dp[mask] is not infinity, compute the new state new_mask = mask | company_mask[i].
   • Update dp[new_mask] with min(dp[new_mask], dp[mask] + cost[i]).
3. Result:
   • The state where all facilities are guarded is (1 << M) - 1, where all bits are \(1\).
   • If dp[(1 << M) - 1] remains at its initial value, output -1; otherwise, output that value.

Complexity

• Time Complexity: \(O(N \cdot 2^M)\)
  • This is the product of the number of security companies \(N\) and the number of states \(2^M\).
  • \(50 \times 2^{18} \approx 1.3 \times 10^7\), which comfortably fits within the time limit.
• Space Complexity: \(O(2^M)\)
  • The size of the DP table is \(2^M\).

Implementation Notes

• Bit Operations: By representing the ability to guard facility \(j\) as 1 << j and combining the entire coverage of a company using the OR operation (|), transition computations become fast.

• Fast I/O: Since there is a large amount of input data (\(E_{i,j}\)) relative to the values of \(N\) and \(M\), in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar methods.

• Transition Order: When iterating over each security company, care must be taken not to select the same company multiple times. As in this implementation, by updating the entire table for each company, we naturally express the choice of “use each company once or not at all.”

  Source Code

import sys

def solve():
    # 全ての入力を一度に読み込み、空白で分割してリストにする（高速化のため）
    data = sys.stdin.read().split()
    if not data:
        return
    
    # N: 警備会社の数, M: 施設の数
    N = int(data[0])
    M = int(data[1])
    
    # C: 各警備会社の契約費用
    # 2番目のインデックスからN個が費用データ
    costs = [int(x) for x in data[2:N+2]]
    
    # 各警備会社が警備できる施設をビットマスクとして表現する
    # 施設jを警備できる場合、マスクのj番目のビットを1にする
    company_masks = []
    # E_{i,j} のデータはインデックス N+2 から始まる
    idx = N + 2
    for i in range(N):
        mask = 0
        for j in range(M):
            if data[idx] == '1':
                mask |= (1 << j)
            idx += 1
        # どの施設も警備できない会社は選ぶ必要がないため除外（費用は1以上のため）
        if mask > 0:
            company_masks.append((costs[i], mask))
    
    # DPテーブルの初期化
    # dp[mask] は、ビットマスクで表される施設集合を警備するための最小コスト
    # 2^M 通りの状態がある (M <= 18 なので最大 262,144)
    num_masks = 1 << M
    inf = 10**18  # 十分に大きな値
    dp = [inf] * num_masks
    dp[0] = 0  # 最初はどの施設も警備していない状態（コスト0）
    
    # 各警備会社について、DPテーブルを更新していく
    for cost, c_mask in company_masks:
        # 現在のDPテーブルの状態を走査
        for mask in range(num_masks):
            # まだ到達不可能な状態（inf）はスキップ
            if dp[mask] == inf:
                continue
            
            # 新しい状態：現在の施設集合に、この会社の警備範囲を追加（ビットOR演算）
            new_mask = mask | c_mask
            new_cost = dp[mask] + cost
            
            # 新しい状態のコストが現在の記録より安ければ更新
            if dp[new_mask] > new_cost:
                dp[new_mask] = new_cost
                
    # 全ての施設が警備された状態（全てのビットが1のマスク）の最小コストを取得
    ans = dp[num_masks - 1]
    
    # 初期値のまま（inf）であれば、全ての施設を警備する方法が存在しない
    if ans == inf:
        print("-1")
    else:
        print(ans)

if __name__ == '__main__':
    solve()

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