Overview

This problem is a game between Takahashi (who wants to maximize the sum) and Aoki (who wants to minimize the sum) involving the design of a transmission network and the rewriting of values.

By focusing on the fact that \(N\) is very small (at most \(12\)), we can reduce the problem to a “set partition problem” based on the properties of the transmission operations. We can solve it by exhaustively searching all partition patterns using Depth-First Search (DFS).

---

Analysis

1. Properties of Transmission Operations (Takahashi’s Moves)

In a single transmission operation, the value of each person \(i\) moves to the destination \(A_i\), and values gathered at the same destination are XORed together. After \(K\) operations, the initial value \(V_i\) reaches a unique destination determined by \(A\).

Since the constraint is \(K \le 10^{18}\), which is sufficiently large compared to the number of people \(N \le 12\), and Takahashi can freely design the destinations \(A\), he can partition the initial values of the \(N\) people into any arbitrary groups (a partition of the set). Specifically, he can gather the initial values of people belonging to the same group in one location, and gather those of different groups in different locations.

For each group \(S_1, S_2, \ldots, S_m\) formed in this way, if we let the XOR sum of the initial values in the group be \(G_r = \bigoplus_{i \in S_r} V_i\), the values remaining at the end will be the XOR sums of each group: \(G_1, G_2, \ldots, G_m\).

2. Aoki’s Optimal Strategy

After observing the partitioning chosen by Takahashi (and the XOR sum of each group \(G_1, \ldots, G_m\)), Aoki can rewrite the initial value of exactly one person to any non-negative integer \(X\).

If Aoki rewrites the value of a person belonging to a group \(S_a\), he can change the XOR sum of that group \(G_a\) to any non-negative integer. Since Aoki wants to minimize the final sum, it is optimal for him to rewrite the XOR sum of the chosen group to \(0\).

Since Aoki can turn the XOR sum of any group into \(0\), it is most effective for him to reduce the group with the largest XOR sum to \(0\). Therefore, the sum after Aoki’s optimal action will be:

\[ \text{(Sum of the XOR sums of all groups)} - \text{(Maximum of the XOR sums)} \]

3. Takahashi’s Optimal Strategy

Takahashi wants to maximize this value. Since Takahashi can freely choose the partition of the set \(\{1, 2, \ldots, N\}\), the problem can be rephrased as follows:

Partition \(N\) elements into several groups. Maximize the value obtained by subtracting the maximum of the XOR sums from the sum of the XOR sums of all groups.

Concrete Example (\(N=3, V = [3, 5, 6]\))

• Partition Option 1: Partition into \(\{1, 2\}\) and \(\{3\}\)
  • XOR sum of Group 1: \(3 \oplus 5 = 6\)
  • XOR sum of Group 2: \(6\)
  • Sum after Aoki’s operation: \((6 + 6) - \max(6, 6) = 6\)
• Partition Option 2: Partition into \(\{1\}\), \(\{2\}\), \(\{3\}\)
  • XOR sum of each group: \(3, 5, 6\)
  • Sum after Aoki’s operation: \((3 + 5 + 6) - \max(3, 5, 6) = 14 - 6 = 8\)

In this case, it is optimal for Takahashi to choose Partition Option 2, and the answer is \(8\).

---

Algorithm

For \(N \le 12\), the total number of ways to partition a set into several groups (Bell number \(B_N\)) is \(B_{12} = 4,213,597\). This is a very small number for a computer, making it possible to exhaustively search all partition methods using Depth-First Search (DFS).

Steps for Exhaustive Search using DFS

1. Place the \(idx\)-th person into one of the already existing groups, or create a new group and place them there.
2. Once all people (\(idx = N\)) have been assigned to groups, calculate the XOR sum of each group.
3. Calculate the “sum of XOR sums - maximum of XOR sums” and update the maximum value found so far.

---

Complexity

Time Complexity

• \(O(B_N \cdot N)\) When \(N = 12\), the Bell number is \(B_{12} \approx 4.2 \times 10^6\). Since there are at most \(N\) groups at each leaf (terminal state) of the DFS, the computation at each state is extremely fast. It easily finishes within a few milliseconds to tens of milliseconds, well within the time limit (usually 2 seconds).

Space Complexity

• \(O(N)\) The maximum depth of the DFS recursion is \(N\), and the size of the array holding the XOR sums of the groups is also at most \(N\). It consumes almost no memory.

---

Implementation Points

• Enumerating Partitions Without Duplicates: When creating a new group in the DFS, if there are already num_groups existing groups, the ID of the new group should always be num_groups. This prevents searching duplicate partitions that differ only in the order of the groups (for example, {{1}, {2, 3}} and {{2, 3}, {1}}).

• Symmetry of XOR: By adding the value to the group with g[i] ^= V[idx] when entering the DFS state, and performing g[i] ^= V[idx] again when returning, we can efficiently backtrack using the same variable.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
long long K;
vector<long long> V;
long long ans = 0;
long long g[12];

void dfs(int idx, int num_groups) {
    if (idx == N) {
        long long sum = 0;
        long long mx = 0;
        for (int i = 0; i < num_groups; ++i) {
            sum += g[i];
            if (g[i] > mx) mx = g[i];
        }
        ans = max(ans, sum - mx);
        return;
    }
    for (int i = 0; i < num_groups; ++i) {
        g[i] ^= V[idx];
        dfs(idx + 1, num_groups);
        g[i] ^= V[idx];
    }
    g[num_groups] = V[idx];
    dfs(idx + 1, num_groups + 1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (!(cin >> N >> K)) return 0;
    V.resize(N);
    for (int i = 0; i < N; ++i) {
        cin >> V[i];
    }
    dfs(0, 0);
    cout << ans << "\n";
    return 0;
}

---

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