Overview

This problem asks us to select some companies from \(N\) security companies to guard all \(M\) facilities at minimum cost. This is a classic Weighted Set Cover problem, and we solve it using bitmask DP by leveraging the constraint \(M \leq 18\).

Analysis

Naive Approach

There are \(2^N - 1\) possible combinations of selecting some companies from \(N\). Since \(N \leq 50\), this gives \(2^{50} \approx 10^{15}\) combinations, making brute-force enumeration completely infeasible.

Key Observation: The Number of Facilities is Small

Focus on \(M \leq 18\). The state “which facilities are already guarded” can be represented with 1 bit per facility, yielding only \(2^M \leq 2^{18} = 262144\) possible states.

For example, when \(M = 3\), the guarding status of facilities can be represented as bitmasks: - 000 (= 0): No facility is guarded - 101 (= 5): Facilities 1 and 3 are guarded - 111 (= 7): All facilities are guarded (goal)

Solution Strategy

The set of facilities that each security company \(i\) can guard is also represented as a bitmask \(\text{cover}[i]\). When company \(i\) is selected, the current guarding status \(\text{mask}\) is updated to \(\text{mask} \mid \text{cover}[i]\).

This has the same structure as the 0-1 Knapsack Problem. We choose to “use or not use” each company, and we want to reach the state where all facilities are covered at minimum cost.

Algorithm

We use bitmask DP.

1. State definition: \(dp[\text{mask}]\) = the minimum cost required to have exactly the facility set \(\text{mask}\) guarded
2. Initial values: \(dp[0] = 0\) (the state where nothing is guarded costs 0), all others are \(\infty\)
3. Transition: Process security companies \(i = 1, 2, \ldots, N\) in order, and for each state \(\text{mask}\): $\(dp[\text{mask} \mid \text{cover}[i]] = \min(dp[\text{mask} \mid \text{cover}[i]],\; dp[\text{mask}] + C_i)\)$
4. Answer: \(dp[(1 \ll M) - 1]\) (the state where all facilities are guarded). If it remains \(\infty\), output \(-1\).

To ensure each company is selected at most once, we iterate over mask in descending order, just like in the 0-1 Knapsack. This prevents the same company from being applied multiple times.

Concrete Example

For \(N=3, M=3\), costs \(C = [5, 3, 4]\), and guarding ranges 110, 011, 100: - Company 1: \(\text{cover}[1] = 011_2 = 3\) (guards facilities 1, 2) - Company 2: \(\text{cover}[2] = 110_2 = 6\) (guards facilities 2, 3) - Selecting companies 1 and 2 gives \(3 \mid 6 = 7 = 111_2\) (all facilities covered), cost \(5 + 3 = 8\)

Complexity

• Time complexity: \(O(N \cdot 2^M)\)
  • With \(N \leq 50\) and \(2^M \leq 2^{18} = 262144\), this results in approximately \(1.3 \times 10^7\) operations, which is sufficiently fast
• Space complexity: \(O(2^M)\)
  • The size of the DP table

Implementation Notes

• When converting each security company’s guardable facilities to a bitmask, if the \(j\)-th facility can be guarded, set mask |= (1 << j)

• To prevent using the same company more than once, loop over mask in descending order (from large to small), just like in the 0-1 Knapsack. If you iterate in ascending order, the effect of the same company may be applied multiple times

• Since costs can be up to \(10^9\) and selecting \(N\) companies can total up to \(5 \times 10^{10}\), using float('inf') or 64-bit integers handles this without issues

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    C = []
    for i in range(N):
        C.append(int(input_data[idx])); idx += 1
    
    cover = []
    for i in range(N):
        mask = 0
        for j in range(M):
            e = int(input_data[idx]); idx += 1
            if e == 1:
                mask |= (1 << j)
        cover.append(mask)
    
    full = (1 << M) - 1
    INF = float('inf')
    
    # dp[mask] = minimum cost to cover the set of facilities represented by mask
    dp = [INF] * (full + 1)
    dp[0] = 0
    
    for i in range(N):
        # Iterate in reverse to avoid using same company twice? 
        # No, since each company is considered once and we can either take it or not,
        # but we need to iterate properly. Actually, since we just OR masks,
        # we can iterate forward through companies and for each, update all masks.
        # But we need to be careful: standard set cover DP.
        # We process each company and for each existing state, try adding it.
        for mask in range(full, -1, -1):
            if dp[mask] < INF:
                new_mask = mask | cover[i]
                if dp[new_mask] > dp[mask] + C[i]:
                    dp[new_mask] = dp[mask] + C[i]
    
    if dp[full] == INF:
        print(-1)
    else:
        print(dp[full])

main()

---

This editorial was generated by claude4.6opus-thinking.