Overview

This problem asks us to arrange \(N\) companies into \(N\) booths placed in a circle, maximizing the total visitor attraction effect of adjacent pairs. We need to find the optimal arrangement under the constraint that the number of swap operations from the initial arrangement is at most \(K\).

Analysis

Key Observation ①: \(N\) is very small

Since \(N \leq 8\), even enumerating all possible orderings (permutations) yields only \(8! = 40320\) cases. This is small enough to process efficiently.

Key Observation ②: Relationship between swap count and permutations

The initial arrangement has company \(i\) at booth \(i\), i.e., the identity permutation \((0, 1, 2, \ldots, N-1)\). The minimum number of swaps required to reach a given permutation \(p\) can be determined from permutation theory using the following formula:

\[\text{Minimum number of swaps} = N - (\text{number of cycles in permutation } p)\]

Concrete example: Consider \(N = 4\) and permutation \(p = (1, 0, 3, 2)\). - Cycle decomposition: \((0 \leftrightarrow 1)(2 \leftrightarrow 3)\) → number of cycles \(= 2\) - Minimum number of swaps \(= 4 - 2 = 2\) (swap companies 0 and 1, swap companies 2 and 3)

The identity permutation has \(N\) cycles so the swap count is \(0\), while a single large cycle requires \(N-1\) swaps.

Solution Approach

Enumerate all permutations, and for each permutation: 1. Check if the minimum number of swaps is at most \(K\) 2. If the condition is satisfied, compute the total visitor attraction effect of adjacent pairs 3. Output the maximum value as the answer

Algorithm

1. Read the input.
2. Enumerate all \(N!\) permutations.
3. For each permutation \(p\):
   • Perform cycle decomposition and count the number of cycles.
   • If \(N - \text{number of cycles} \leq K\), then this permutation is reachable within \(K\) swaps.
   • If reachable, compute the score of all circularly adjacent pairs: \(\sum_{i=0}^{N-1} C_{p[i]}[p[(i+1) \bmod N]]\).
4. Output the maximum score.

How to Count the Number of Cycles

Treat the permutation as a directed graph with edges \(i \to p[i]\). Start from an unvisited vertex and follow edges until returning to the starting vertex — this identifies one cycle. Repeat this for all vertices to count the total number of cycles.

Complexity

• Time complexity: \(O(N! \cdot N)\)
  • Enumerating all permutations takes \(O(N!)\), and computing the cycle count and score for each permutation takes \(O(N)\) each
  • When \(N \leq 8\), this is \(8! \times 8 = 322560\), which is fast enough
• Space complexity: \(O(N^2)\)
  • Storing the attraction effect matrix \(C\) requires \(O(N^2)\)

Implementation Notes

• Using 0-indexed company numbers simplifies permutation and index operations.

• Since the arrangement is circular, the neighbor of booth \(i\) is booth \((i+1) \bmod N\). Be careful not to forget the adjacency between booth \(N-1\) and booth \(0\).

• The formula “minimum number of swaps \(= N - \text{number of cycles}\)” is a fundamental property of permutation groups. A cycle of length \(L\) requires \(L-1\) swaps to return to the identity permutation, and summing over all cycles gives \(\sum (L_i - 1) = N - \text{number of cycles}\).

  Source Code

from itertools import permutations

def solve():
    N, K = map(int, input().split())
    C = []
    for _ in range(N):
        C.append(list(map(int, input().split())))
    
    # Initial permutation is (0, 1, 2, ..., N-1) representing enterprise i at booth i
    # We need to find a permutation of enterprises placed in booths 1..N (circular)
    # such that the sum of C[perm[i]][perm[(i+1)%N]] is maximized
    # and the permutation can be reached from identity in at most K swaps.
    
    # The minimum number of swaps to go from identity to a permutation p is N - (number of cycles in p).
    
    def cycle_count(perm):
        visited = [False] * N
        cycles = 0
        for i in range(N):
            if not visited[i]:
                cycles += 1
                j = i
                while not visited[j]:
                    visited[j] = True
                    j = perm[j]
        return cycles
    
    def score(perm):
        s = 0
        for i in range(N):
            s += C[perm[i]][perm[(i + 1) % N]]
        return s
    
    best = 0
    for perm in permutations(range(N)):
        swaps_needed = N - cycle_count(perm)
        if swaps_needed <= K:
            s = score(perm)
            if s > best:
                best = s
    
    print(best)

solve()

---

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