Overview

This problem asks us to find an order to demolish \(N\) given buildings such that the total cost is minimized. Since the number of buildings \(N\) is at most \(19\) (which is very small), we can efficiently find the optimal solution within the time limit using dynamic programming with bitmask (bitDP), where the subset of demolished buildings is represented as a bitmask.

Analysis

1. Naive Approach and Its Limitations

If we naively search all possible demolition orders (permutations), there are \(N!\) combinations. When \(N = 19\), \(19! \approx 1.2 \times 10^{17}\), which is far too slow to run within the time limit.

2. Reduction to bitDP

Let us consider the cost of demolishing a certain building \(u\). The cost incurred when demolishing building \(u\) is the sum of: - The initial demolition cost \(C_u\) of building \(u\) - The sum of the additional costs \(W_{i,u}\) added to building \(u\) from all already demolished buildings \(i\)

The key point is that which buildings have not yet been demolished has absolutely no effect on the cost of demolishing building \(u\). What affects the cost is only the set of which buildings have already been demolished.

Therefore, we can use dynamic programming (DP) with the following state definition: - \(dp[S] :=\) the minimum cost paid so far when the set of already demolished buildings is \(S\)

3. Optimizing Transitions

Let building \(u \in S\) be the last building demolished. The state immediately prior to this is \(S \setminus \{u\}\) (the set \(S\) excluding \(u\)). The transition equation is as follows:

\[dp[S] = \min_{u \in S} \left( dp[S \setminus \{u\}] + C_u + \sum_{i \in S \setminus \{u\}} W_{i,u} \right)\]

If we compute this transition naively, for each state \(S\) (\(2^N\) states) and each last demolished building \(u\) (at most \(N\) choices), we need an \(O(N)\) loop to compute \(\sum W_{i,u}\). This results in a total time complexity of \(O(N^2 2^N)\). When \(N = 19\), \(N^2 2^N \approx 1.9 \times 10^8\), which might not run within the time limit in Python.

To speed this up, we can precompute the “sum of costs from the buildings in set \(S\) to building \(u\)” to reduce the transition time to \(O(1)\). - \(f[u][S] := \sum_{i \in S} W_{i,u}\)

By focusing on a single element \(v \in S\), we can compute \(f[u][S]\) incrementally in \(O(1)\) time (using push/pull DP) as follows: - \(f[u][S] = f[u][S \setminus \{v\}] + W_{v,u}\)

This allows us to perform the precomputation in \(O(N 2^N)\) and the main DP transitions in \(O(N 2^N)\), achieving a significant speedup overall.

Algorithm

Step 1: Precomputing the Cost Table

For all buildings \(u \in \{0, \dots, N-1\}\) and all sets \(S \in \{0, \dots, 2^N-1\}\), we compute \(f[u][S] = \sum_{i \in S} W_{i,u}\).

Letting \(v\) be the building corresponding to the rightmost set bit (LSB: Least Significant Bit) in set \(S\), we can compute this cumulatively as: f[u][S] = f[u][S ^ (1 << v)] + W[v][u]

Step 2: Executing the bitDP

1. Initialize an array dp of size \(2^N\) with a sufficiently large value (INF).
2. Set the base case dp[0] = 0 (the cost is 0 when no buildings have been demolished yet).
3. Loop \(S\) from \(1\) to \(2^N - 1\).
4. Iterate through the set bits in \(S\) (which represent candidates for the last demolished building \(u\)) and perform the following transitions:
   • prev_S = S ^ (1 << u)
   • dp[S] = min(dp[S], dp[prev_S] + C[u] + f[u][prev_S])
5. The final answer will be dp[(1 << N) - 1], which represents the state where all buildings have been demolished.

Complexity

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

  • In the precomputation, we perform \(2^N\) transitions for each \(u\) (\(N\) choices).
  • In the main DP, for each state \(S\) (\(2^N\) states), we perform transitions for each of its set bits (on average \(N/2\), at most \(N\)).
  • When \(N = 19\), this requires about \(19 \times 2^{19} \approx 10^7\) basic operations, which runs very fast (around 0.5 seconds) even in Python.

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

  • The precomputation table f has a size of \(N \times 2^N\), and the DP table dp has a size of \(2^N\).
  • When \(N = 19\), the number of stored integers is about \(10^7\), and the memory usage is within several tens of megabytes, which is well within the memory limit.

Key Implementation Points

• Fast Retrieval of the LSB (Least Significant Bit): By using the bitwise operation S & -S, we can extract the rightmost set bit (the bit that is 1) of an integer \(S\) in \(O(1)\) time.

• Conversion to Index: By preparing an array lsb_index in advance, we can map the bit representation 1 << i back to the building index i in \(O(1)\) time.

• Iterating Only Over Set Bits: In the DP transitions, to iterate only over the buildings in set \(S\) (the set bits), we start with temp = S and repeatedly use temp &= temp - 1 (or temp ^= lsb). This avoids wasting loop iterations on 0 bits, achieving a constant-factor speedup.

  Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    C = [int(x) for x in data[1:N+1]]
    
    W = []
    idx = N + 1
    for _ in range(N):
        W.append([int(x) for x in data[idx:idx+N]])
        idx += N
        
    # LSBのインデックスを高速に引くためのテーブル
    lsb_index = [0] * (1 << N)
    for i in range(N):
        lsb_index[1 << i] = i
        
    # f[u][S] = Sに含まれる建物からuへのコストの和
    f = [[0] * (1 << N) for _ in range(N)]
    for u in range(N):
        fu = f[u]
        Wu = [W[i][u] for i in range(N)]
        for S in range(1, 1 << N):
            lsb = S & -S
            fu[S] = fu[S ^ lsb] + Wu[lsb_index[lsb]]
            
    INF = 10**18
    dp = [INF] * (1 << N)
    dp[0] = 0
    
    for S in range(1, 1 << N):
        temp = S
        min_val = INF
        while temp > 0:
            lsb = temp & -temp
            u = lsb_index[lsb]
            prev_S = S ^ lsb
            val = dp[prev_S] + C[u] + f[u][prev_S]
            if val < min_val:
                min_val = val
            temp ^= lsb
        dp[S] = min_val
        
    print(dp[(1 << N) - 1])

if __name__ == '__main__':
    solve()

---

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