Overview

Given \(N\) gems, select \(K\) of them and arrange them in a circular formation. The goal is to maximize the sum of “brilliance values” plus the sum of “harmony values between adjacent gems.” Since the number of gems \(N\) is at most 16, which is very small, this can be solved efficiently using Bitmask DP.

Analysis

1. Reformulating the Problem

This problem is similar to finding a “weighted Hamiltonian cycle” in graph theory. - Each gem is treated as a vertex, where gem \(i\) has weight \(P_i\). - The edge between gems \(i\) and \(j\) has weight \(C_{i,j}\). - Select \(K\) vertices and maximize (vertex weights + edge weights) of a cycle of length \(K\) connecting them.

2. Why Brute Force Doesn’t Work

The number of ways to choose \(K\) gems from \(N\) is \(\binom{N}{K}\), and the number of ways to arrange them in a circular permutation is \((K-1)! / 2\). For \(N=16, K=16\), there is only 1 combination, but the number of arrangements is \(15! / 2 \approx 6.5 \times 10^{11}\), which is far too large for brute force within the time limit.

3. Using Dynamic Programming (Bitmask DP)

By managing the information “which gems have already been selected” as a bitmask (mask), we can dramatically reduce the computational complexity. Since the arrangement is circular, we think of it as “fixing one gem as the starting point, extending a path from it, and finally returning to the starting point.”

To avoid double counting, we fix the gem with the smallest index in each mask as the starting point \(s\). This prevents counting the same cycle multiple times from different starting points.

Algorithm

1. DP State Definition

dp[mask][i]: - mask: the set of gems selected so far (bit representation) - i: the index of the last gem selected - Value: the maximum (sum of brilliance values + sum of harmony values along the path) in that state

2. Initial State

For each gem \(i\), the state where only that gem is selected serves as the initial value. - dp[1 << i][i] = P[i]

3. Transitions

For the current set mask, the last selected gem i, and the starting point s (the minimum index in mask), consider the next gem j to select. - Condition: j is not in mask, and j > s (due to the fixed starting point). - dp[mask | (1 << j)][j] = max(dp[mask | (1 << j)][j], dp[mask][i] + C[i][j] + P[j])

4. Completing the Cycle (Computing the Answer)

When the number of selected gems (the number of set bits in mask) is exactly \(K\), add the harmony value from the last selected gem i back to the starting point s. - beauty = dp[mask][i] + C[i][s] The maximum value of beauty over all such cases is the answer.

Complexity

• Time Complexity: \(O(2^N \cdot N^2)\)
  • The number of states is \(O(2^N \cdot N)\), and each state requires \(O(N)\) for transitions.
  • For \(N=16\), this is \(2^{16} \cdot 16^2 \approx 6.5 \times 10^4 \cdot 256 \approx 1.6 \times 10^7\), which fits within the time limit even in Python with sufficiently fast implementation (such as optimizing bit operations).
• Space Complexity: \(O(2^N \cdot N)\)
  • This depends on the size of the DP table.

Implementation Notes

• Fixing the starting point: By using the lowest set bit of mask (mask & -mask) as the starting point \(s\), we efficiently prevent redundant computation.

• Loop order: The DP must be updated in order of increasing number of gems (popcount).

• Optimization: In Python, it is important to make use of bin(mask).count('1') and bit operations, keeping the inner loops as simple as possible. Additionally, pre-classifying masks by bit count (e.g., masks_by_size) reduces unnecessary loop iterations.

  Source Code

import sys

def solve():
    # Use fast I/O to read all input data at once
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Read N and K
    N = int(input_data[0])
    K = int(input_data[1])
    
    # Read jewel brightness values P
    P = list(map(int, input_data[2:2+N]))
    
    # Read harmony values C as an N x N matrix
    C = []
    for i in range(N):
        row = list(map(int, input_data[2+N+i*N:2+N+(i+1)*N]))
        C.append(row)

    # Precompute masks grouped by their popcount and identify the smallest set bit index
    masks_by_size = [[] for _ in range(K + 1)]
    trailing_zeros = [0] * (1 << N)
    bit_to_idx = [0] * (1 << N)
    for i in range(N):
        bit_to_idx[1 << i] = i
    
    for mask in range(1, 1 << N):
        # Calculate the number of set bits (popcount)
        cnt = bin(mask).count('1')
        
        # Identify the smallest index (trailing zero) in the mask to fix the cycle's start
        lowbit = mask & -mask
        tz = bit_to_idx[lowbit]
        trailing_zeros[mask] = tz
        
        # Only store masks with popcount up to K
        if cnt <= K:
            masks_by_size[cnt].append(mask)

    # INF is used for initializing the DP table
    INF = 10**18
    # dp[mask][i] stores the maximum beauty of a path visiting jewels in 'mask' and ending at jewel 'i'.
    # We fix the starting jewel as the one with the smallest index in the mask to avoid redundant calculations.
    dp = [[-INF] * N for _ in range(1 << N)]
    
    # Base case: paths consisting of a single jewel
    for i in range(N):
        dp[1 << i][i] = P[i]

    # Fill the DP table using the bitmask approach for paths of length 1 up to K-1
    for size in range(1, K):
        for mask in masks_by_size[size]:
            s = trailing_zeros[mask]
            dp_mask = dp[mask]
            
            # Identify jewels 'i' currently in the mask that have been reached
            in_mask = []
            temp_mask = mask
            while temp_mask:
                i_bit = temp_mask & -temp_mask
                i = bit_to_idx[i_bit]
                if dp_mask[i] > -INF // 2:
                    in_mask.append(i)
                temp_mask ^= i_bit
            
            if not in_mask:
                continue
            
            # Try adding a new jewel 'j' to the selection.
            # To ensure uniqueness, only consider jewels with an index greater than the fixed start 's'.
            possible_j_mask = ((1 << N) - (1 << (s + 1))) & ~mask
            temp_j_mask = possible_j_mask
            while temp_j_mask:
                j_bit = temp_j_mask & -temp_j_mask
                j = bit_to_idx[j_bit]
                temp_j_mask ^= j_bit
                
                # Pre-fetch the DP list for the updated mask to speed up access
                new_dp_mask = dp[mask | (1 << j)]
                
                # Find the maximum beauty by connecting some 'i' in the mask to 'j'
                max_val = -INF
                for i in in_mask:
                    val = dp_mask[i] + C[i][j]
                    if val > max_val:
                        max_val = val
                
                # Update the DP state for the new mask and end jewel 'j'
                new_val = max_val + P[j]
                if new_val > new_dp_mask[j]:
                    new_dp_mask[j] = new_val

    # Determine the maximum beauty by completing the Hamiltonian cycle for each mask of size K
    ans = -INF
    for mask in masks_by_size[K]:
        s = trailing_zeros[mask]
        dp_mask = dp[mask]
        # Any jewel 'i' in the mask (other than 's') can be the last one before closing the circle back to 's'
        temp_mask = mask ^ (1 << s)
        while temp_mask:
            i_bit = temp_mask & -temp_mask
            i = bit_to_idx[i_bit]
            temp_mask ^= i_bit
            
            if dp_mask[i] > -INF // 2:
                # Add the harmony between the final jewel 'i' and the initial jewel 's'
                val = dp_mask[i] + C[i][s]
                if val > ans:
                    ans = val
    
    # Output the maximum beauty found
    print(ans)

if __name__ == '__main__':
    solve()

---

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