Overview

Given \(N\) gems, select \(K\) of them and arrange them in a circle to maximize “sum of brilliances + sum of harmony values of adjacent pairs.” This reduces to finding a maximum weight Hamiltonian cycle on a weighted graph, which we solve using bitmask DP.

Analysis

Organizing the Problem Structure

The beauty when \(K\) gems are arranged in a circle is the sum of two components: - The total brilliance \(P\) of the selected gems - The total harmony \(C\) of the \(K\) adjacent pairs in the circular arrangement

In other words, consider a complete graph on \(N\) vertices where edge \((i, j)\) has weight \(C_{i,j}\) and vertex \(i\) has weight \(P_i\). The problem becomes: select a subset of \(K\) vertices, find a Hamiltonian cycle on them (a cycle that visits every vertex exactly once and returns to the start), and maximize the sum of vertex weights + edge weights.

Issues with the Naive Approach

There are \(\binom{N}{K}\) ways to choose \(K\) gems, and for each choice there are \((K-1)!/2\) circular arrangements. When \(N = 16, K = 16\), this gives \((16-1)!/2 \approx 6.5 \times 10^{11}\) arrangements, making full enumeration completely infeasible.

Speeding Up with Bitmask DP

We use bitmask DP, a standard technique for Hamiltonian cycle problems. We manage the set of visited vertices as a bitmask, with the DP state being “which set of vertices has been visited and which vertex are we currently at.”

Algorithm

1. Fixing the Starting Point

In circular arrangements, rotations would count the same arrangement multiple times. To prevent this, for each subset, we fix the vertex with the smallest index as the starting point (beginning of the path). This ensures each Hamiltonian cycle is counted exactly once.

2. DP Definition

\[dp[\text{mask}][v] = \text{the maximum edge weight sum of a path that visits all vertices in mask, starting from the fixed origin and ending at vertex } v\]

Here, the set bits in mask represent the visited vertex set, and the starting point is the lowest set bit (smallest index vertex) of mask.

3. Initialization

For each vertex \(v\): \(dp[1 \ll v][v] = 0\) (the set containing only vertex \(v\), currently at \(v\). No edges have been traversed yet, so the weight is \(0\)).

4. Transitions

When all vertices in mask have been visited and we are currently at \(v\), we move to a vertex \(u\) not in mask (with the constraint that \(u > \text{start}\)):

\[dp[\text{mask} \mid (1 \ll u)][u] = \max\left(dp[\text{mask} \mid (1 \ll u)][u],\; dp[\text{mask}][v] + C_{v,u}\right)\]

The condition \(u > \text{start}\) maintains the invariant that the starting point is always the smallest index in the set.

5. Completing the Cycle

When \(|\text{mask}| = K\), we add the edge from the last vertex \(v\) back to the starting point start to form a cycle:

\[\text{beauty} = dp[\text{mask}][v] + C_{v,\text{start}} + \sum_{i \in \text{mask}} P_i\]

The maximum of this value over all mask and \(v\) is the answer.

Concrete Example

When \(K = 3\), selecting gems \(\{0, 2, 3\}\) (0-indexed): - Starting point = \(0\) (smallest index) - Example path: \(0 \to 2 \to 3\), edge weight = \(C_{0,2} + C_{2,3}\) - Completing the cycle: \(+ C_{3,0}\) - Beauty: \(P_0 + P_2 + P_3 + C_{0,2} + C_{2,3} + C_{3,0}\)

Complexity

• Time complexity: \(O(2^N \times N^2)\)
  • For each mask (\(2^N\) total), we iterate over pairs of the current vertex \(v\) and the next vertex \(u\) (at most \(N^2\)). In practice, since we only pair vertices in mask with vertices not in mask, the constant factor is somewhat smaller.
• Space complexity: \(O(2^N \times N)\)
  • This is the size of the DP table. When \(N = 16\), this is approximately \(2^{16} \times 16 = 1{,}048{,}576\) entries.

Implementation Notes

• Fixing the starting point: Use mask & (-mask) to get the lowest set bit of the bitmask, which serves as the starting point. Newly added vertices \(u\) are restricted to those with indices larger than the starting point, preventing duplicate exploration of the same cycle.

• Precomputing the sum of \(P\): Precompute sum_P[mask] so that the total brilliance can be added in \(O(1)\) when completing a cycle.

• Fast vertex enumeration using bit operations: The pattern tmp = remaining; while tmp: lb = tmp & (-tmp); ... efficiently enumerates positions of set bits.

• Special cases for \(K = 1, K = 2\): When \(K = 1\), the concept of a Hamiltonian cycle does not apply, so it requires separate handling. When \(K = 2\), there are two edges (round trip) between the two vertices, so we add \(C_{i,j} + C_{j,i} = 2C_{i,j}\).

  Source Code

import sys
from itertools import combinations

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    P = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    
    C = []
    for i in range(N):
        row = [int(input_data[idx + j]) for j in range(N)]
        C.append(row)
        idx += N
    
    if K == 1:
        print(max(P))
        return
    
    if K == 2:
        best = -float('inf')
        for i in range(N):
            for j in range(i+1, N):
                # In a cycle of 2, there are 2 edges both between i and j
                val = P[i] + P[j] + C[i][j] + C[j][i]
                best = max(best, val)
        print(best)
        return
    
    # For K >= 3, we use bitmask DP for finding the best Hamiltonian cycle on the chosen subset.
    # 
    # Approach: For each subset of size K, find the maximum weight Hamiltonian cycle.
    # We fix one vertex in the subset (the smallest numbered) to avoid counting rotations multiple times,
    # then do DP over bitmask for Hamiltonian path from that vertex, and close the cycle at the end.
    #
    # dp[mask][v] = max sum of edge weights for a path starting at the fixed vertex,
    #               visiting exactly the vertices in mask, ending at v.
    # 
    # Since N <= 16, total states = 2^16 * 16 = ~1M, and for each subset of size K we do work.
    # But actually we can do a single DP over all masks.
    
    # Global DP approach:
    # For any bitmask, we define a "starting vertex" as the lowest-numbered bit in the mask.
    # dp[mask][v] = best path weight from lowest-bit vertex to v, visiting all vertices in mask.
    
    NEG_INF = -float('inf')
    
    # Precompute sum of P for each mask
    sum_P = [0] * (1 << N)
    for mask in range(1, 1 << N):
        lb = mask & (-mask)
        sum_P[mask] = sum_P[mask ^ lb] + P[lb.bit_length() - 1]
    
    # Precompute popcount
    popcount = [0] * (1 << N)
    for mask in range(1, 1 << N):
        popcount[mask] = popcount[mask >> 1] + (mask & 1)
    
    # DP
    # dp[mask][v]: best Hamiltonian path cost (sum of edge weights) from start(mask) to v
    # where start(mask) = lowest set bit of mask, and all bits in mask are visited.
    
    dp = [[NEG_INF] * N for _ in range(1 << N)]
    
    # Initialize: single vertex masks
    for v in range(N):
        dp[1 << v][v] = 0
    
    ans = NEG_INF
    
    for mask in range(1, 1 << N):
        pc = popcount[mask]
        if pc > K:
            continue
        
        start = (mask & (-mask)).bit_length() - 1
        
        for v in range(N):
            if dp[mask][v] == NEG_INF:
                continue
            if not (mask & (1 << v)):
                continue
            
            cur_val = dp[mask][v]
            
            # If we have K vertices, try to close the cycle
            if pc == K:
                cycle_val = cur_val + C[v][start] + sum_P[mask]
                if cycle_val > ans:
                    ans = cycle_val
            else:
                # Extend path: add a new vertex u (u > start to ensure start remains the lowest)
                # Actually, u must not be in mask, and u > start is guaranteed if start is the lowest bit
                # and u is not in mask... not necessarily u > start. But start IS the lowest bit in mask,
                # so any bit not in mask that is < start would become the new lowest bit, breaking our invariant.
                # So we only add u > start.
                remaining = ((1 << N) - 1) & ~mask & ~((1 << (start + 1)) - 1)
                tmp = remaining
                while tmp:
                    lb = tmp & (-tmp)
                    u = lb.bit_length() - 1
                    new_mask = mask | lb
                    new_val = cur_val + C[v][u]
                    if new_val > dp[new_mask][u]:
                        dp[new_mask][u] = new_val
                    tmp ^= lb
    
    print(ans)

solve()

---

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