Overview

This is a problem of selecting a combination of \(N\) projects that maximizes profit while avoiding conflicts and staying within budget. Given the constraint \(N \leq 18\), we examine all subsets using bit brute force.

Analysis

Key Insight

• The constraint \(N \leq 18\) is extremely important
• There are only \(2^N = 2^{18} = 262144\) possible selections
• This is small enough to allow exhaustive search

Why Bit Brute Force?

For each project, there are two choices: “select” or “don’t select”, so the selection state can be represented as an \(N\)-bit integer.

For example, when \(N = 4\): - 0101 (= 5) → Select projects 1 and 3 - 1110 (= 14) → Select projects 2, 3, and 4

Checking Conflict Relations

Managing conflict relations with bitmasks is efficient.

Example: If project 0 conflicts with project 2, and project 0 conflicts with project 3: - conflict[0] = 1100 (= 12) → Projects conflicting with 0 are 2 and 3

For a selected project \(i\), if mask & conflict[i] is non-zero, then a project conflicting with \(i\) is also selected, making it invalid.

Algorithm

1. Read Input: Read the cost and profit of each project, and the conflict relations

2. Convert Conflicts to Bitmasks: For each project \(i\), store the set of conflicting projects in conflict[i] as a bitmask

3. Enumerate All Subsets: For each integer mask from \(0\) to \(2^N - 1\):

   • The positions where bits are set in mask represent selected projects
   • Check if there are no conflicts among selected projects
   • Check if total cost is within budget \(K\)
   • If both conditions are satisfied, calculate total profit and update the maximum

4. Output Result: Output the maximum profit

mask = 0110 (Select projects 1, 2)
↓
For project 1: Check mask & conflict[1]
For project 2: Check mask & conflict[2]
↓
No conflicts & within budget → Calculate profit

Complexity

• Time Complexity: \(O(2^N \cdot N)\)
  • For each of \(2^N\) subsets, check \(N\) projects
  • When \(N = 18\), approximately \(262144 \times 18 \approx 4.7 \times 10^6\) operations
• Space Complexity: \(O(N)\)
  • Size of the array conflict storing conflict relations

Implementation Notes

1. Converting to 0-indexed: In the input, project numbers start from 1, so after reading \(U, V\), subtract 1 to make them 0-indexed

2. Basic Bit Operations:

   • mask & (1 << i): Check if the \(i\)-th bit of mask is set
   • conflict[U] |= (1 << V): Set the \(V\)-th bit of conflict[U]

3. Early Termination: When a conflict is found, break out of the loop to avoid unnecessary computation

4. Initial Value: Since selecting nothing (mask = 0) is also a valid choice, initializing max_profit to 0 is fine

Source Code

def solve():
    N, M, K = map(int, input().split())
    
    projects = []
    for i in range(N):
        C, P = map(int, input().split())
        projects.append((C, P))
    
    # Manage conflict relations with bitmasks
    conflict = [0] * N
    for j in range(M):
        U, V = map(int, input().split())
        U -= 1  # 0-indexed
        V -= 1
        conflict[U] |= (1 << V)
        conflict[V] |= (1 << U)
    
    max_profit = 0
    
    # Enumerate all subsets (2^N possibilities)
    for mask in range(1 << N):
        # Check if this subset satisfies conflict relations
        valid = True
        total_cost = 0
        total_profit = 0
        
        for i in range(N):
            if mask & (1 << i):
                # Project i is selected
                # Check if any project conflicting with i is also selected
                if mask & conflict[i]:
                    valid = False
                    break
                total_cost += projects[i][0]
                total_profit += projects[i][1]
        
        if valid and total_cost <= K:
            max_profit = max(max_profit, total_profit)
    
    print(max_profit)

solve()

---

This editorial was generated by claude4.5opus.