Overview

This problem asks us to find the maximum score Takahashi can achieve in a game where Takahashi divides people into groups and calculates the XOR sum of each group, and then Aoki changes the XOR sum of the largest group to 0. The score is defined as (the sum of XOR sums of all groups - the maximum XOR sum).

Analysis

1. Grouping by the result of transmission operations

After \(K\) transmission operations, the value of each person \(i\) is sent to \(A^K_i\) (the destination after applying \(A\) \(K\) times). In other words, the value held by person \(j\) after the operations is the XOR sum of the initial values of all people who reach person \(j\) in \(K\) steps. This divides the people into several groups of “people who reach the same destination after \(K\) steps”, and the final value of each group becomes the XOR sum of the initial values of the people in that group.

2. Arbitrary grouping is possible

Under the condition \(K \geq 1\), Takahashi can partition the people into arbitrary groups by appropriately designing the transmission network \(A\). For example, we can achieve any grouping by choosing one representative for each group to have a self-loop (\(A_i = i\)) and constructing paths of length \(K\) from the other members of the group to their representative.

3. Aoki’s optimal move

Aoki can rewrite the initial value of one person to any non-negative integer. If the XOR sum of the other people in the group is \(Y\), rewriting the chosen person’s value to \(Y\) makes the XOR sum of the entire group \(Y \oplus Y = 0\). Since Aoki wants to minimize the total sum, his optimal move is to choose one group with the largest XOR sum and set its value to 0.

4. Takahashi’s optimal move and exhaustive search

Knowing that Aoki will set the largest group’s XOR sum to 0, Takahashi partitions the people to maximize the sum of the XOR sums of all groups minus the maximum XOR sum. The number of people \(N\) is at most 12, and the total number of ways to partition 12 people (the Bell number) is \(B_{12} = 4213597\). Therefore, we can easily search all possible partitions.

Algorithm

We use Depth First Search (DFS) to enumerate all possible ways to partition the people into groups. 1. The DFS function takes the index of the person currently being considered, idx, as an argument. 2. For the idx-th person, we branch into either “add to one of the existing groups” or “create a new group”. 3. When adding to an existing group, we update the XOR sum of that group with XOR V[idx]. To revert this change after returning from the DFS, we perform XOR V[idx] again. 4. Once everyone has been assigned (idx == N), we calculate the total sum and the maximum value of the XOR sums of each group. If sum - max exceeds the maximum score found so far, we update the answer.

Complexity

• Time Complexity: \(O(N \cdot B_N)\) (where \(B_N\) is the Bell number. For \(N=12\), this is about \(5 \times 10^7\) operations, which is fast enough).
• Space Complexity: \(O(N)\) (for the recursion depth and the array storing the XOR sums of the groups).

Implementation Points

• When managing the XOR sums of the groups in an array, copying the array every time would increase the time complexity. Instead, by utilizing the self-inverse property of the XOR operation (\(A \oplus B \oplus B = A\)), we can add and remove elements using the ^= operator on the same variables, making the implementation both fast and concise.

• If all people belong to a single group, the score will be sum - max = 0. Considering cases where the initial values might be 0, we initialize the answer to 0.

  Source Code

#include <iostream>
#include <algorithm>

using namespace std;

int N;
long long V[12];
long long ans = 0;
long long groups[12];
int num_groups = 0;

void dfs(int idx) {
    if (idx == N) {
        if (num_groups == 0) return;
        long long sum = 0;
        long long mx = 0;
        for (int i = 0; i < num_groups; ++i) {
            sum += groups[i];
            mx = max(mx, groups[i]);
        }
        ans = max(ans, sum - mx);
        return;
    }
    
    // 既存のグループに入れる
    for (int i = 0; i < num_groups; ++i) {
        groups[i] ^= V[idx];
        dfs(idx + 1);
        groups[i] ^= V[idx];
    }
    
    // 新しいグループを作る
    groups[num_groups++] = V[idx];
    dfs(idx + 1);
    num_groups--;
}

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

This editorial was generated by or-glm5.2-high.