Overview

Starting from the initial arrangement (company \(i\) at booth \(i\)), we want to maximize the total effect of adjacent pairs on a circular arrangement, among all arrangements reachable within \(K\) swaps or fewer.
Since \(N \le 8\), we can try all arrangements (permutations) and determine reachability using the “minimum number of swaps required.”

Analysis

Key Insight 1: An arrangement can be represented as a “permutation”

The final arrangement can be represented by an array (permutation) \(p\) of length \(N\): - \(p[i] =\) the company number at booth \(i\)
(0-indexed in the code).

Since the adjacency is circular, the total score is: [ \sum{i=0}^{N-1} C{p[i],\,p[(i+1)\bmod N]} ]

Key Insight 2: “Reachable within \(K\) swaps” can be determined by the minimum number of swaps

The operation is “swap any two companies” = swap two elements of the array.
The minimum number of swaps needed to produce a permutation \(p\) from the initial arrangement (identity permutation \([0,1,2,\dots]\)) can be computed as follows:

• View the permutation \(p\) as a mapping \(i \to p[i]\) and perform cycle decomposition
• If the number of cycles is cycles, the minimum number of swaps is: [ \text{dist} = N - \text{cycles} ]

Example: \(N=4\), \(p=[1,0,3,2]\)
The cycles are \((0\,1)(2\,3)\) with cycles=2, so dist = 4-2 = 2. Indeed, it can be constructed with 2 swaps.

Therefore, for each arrangement \(p\), it is reachable if dist <= K, and unreachable otherwise.

Naively “enumerating all sequences of up to \(K\) swaps” is too expensive

There are \(\binom{N}{2}\) choices at each step, and searching to depth \(K\) leads to an explosion.
On the other hand, when \(N \le 8\), the total number of permutations is at most \(8! = 40320\), so “enumerating all arrangements and mathematically determining reachability” is both simple and reliable.

Algorithm

1. Enumerate all permutations \(p\) (company assignments to booths).
2. Count the number of cycles cycles of that permutation using a visited array (follow unvisited elements to trace one cycle).
3. Compute dist = N - cycles. If dist > K, skip this arrangement.
4. If dist <= K, compute the total score of circular adjacent pairs: [ (p[0],p[1]), (p[1],p[2]), \dots, (p[N-1],p[0]) ] and update the maximum value.
5. Output the maximum value.

Complexity

• Time complexity: \(O(N! \cdot N)\)
  (Cycle computation \(O(N)\) + score computation \(O(N)\) per permutation)
• Space complexity: \(O(N^2)\)
  (Dominated by the effect matrix \(C\). Other arrays like visited are \(O(N)\))

Implementation Notes

• The permutation perm is treated as “the company at booth \(i\)” (e.g., a=perm[i] in the code).

• The number of cycles can be counted using visited, by following j = perm[j].

• Since the arrangement is circular, use (i+1) % N for adjacency (the last and first elements are adjacent).

  Source Code

import sys
from itertools import permutations

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    C = [list(map(int, input().split())) for _ in range(N)]

    ans = 0
    for perm in permutations(range(N)):
        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]
        dist = N - cycles
        if dist > K:
            continue

        s = 0
        for i in range(N):
            a = perm[i]
            b = perm[(i + 1) % N]
            s += C[a][b]
        if s > ans:
            ans = s

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.