Overview

This problem asks us to find the minimax value (the maximum of the minimum sum of final values) in a game involving value propagation (XOR sum) on a directed graph, where the opponent can rewrite one element.

Although the game seems complex at first glance, mathematical analysis reveals that the final sum when both players play optimally is always “the sum of the initial values minus the maximum of the initial values”, i.e., \(\sum V_i - \max(V)\).

Analysis

1. Modeling the Propagation Process

The array \(A\) chosen by Takahashi can be viewed as a graph where each vertex has exactly one outgoing directed edge (a Functional Graph). In this graph, let \(dest(i, K)\) denote the destination of person \(i\) after \(K\) transitions.

After performing the propagation process \(K\) times, the value \(V'_q\) held by each person \(q\) is the XOR sum of the initial values \(V_i\) of all people \(i\) such that \(dest(i, K) = q\). $\(V'_q = \bigoplus_{dest(i, K) = q} V_i\)$

2. Aoki’s Optimal Strategy

After Takahashi chooses \(A\), Aoki can rewrite the initial value of some person \(p\) to any non-negative integer \(X\). Rewriting the initial value \(V_p\) to \(X\) is equivalent to XORing \(Y = V_p \oplus X\) to the initial state.

Since the propagation process is linear with respect to the XOR operation, in the final state, \(Y\) will be XORed only to the value of person \(dest(p, K)\). Since Aoki can choose \(X\) freely, \(Y\) can also be any non-negative integer. This means that in the final state, “the final value of person \(dest(p, K)\) can be rewritten to any non-negative integer (specifically, \(0\))”.

Since Aoki wants to minimize the final sum, he will choose the person \(q^* = dest(p, K)\) with the largest final value and rewrite their value to \(0\). Therefore, the sum after Aoki’s optimal move is as follows: $\(\sum_{q=1}^N V'_q - \max_{q} V'_q\)$

3. Takahashi’s Optimal Strategy

Takahashi wants to maximize this value: \(\sum V'_q - \max V'_q\).

Now, consider the case where Takahashi sets \(A_i = i\) (everyone sends their value to themselves). In this case, no matter how many times the operation is performed, the destination does not change, so \(dest(i, K) = i\), and the final values remain the same as the initial values (\(V'_i = V_i\)). Under this strategy, Aoki will set the value of the person with the maximum initial value to \(0\), resulting in a sum of \(\sum V_i - \max(V_i)\).

4. Proof that this is always the maximum value

We will show that no matter what \(A\) Takahashi chooses, the sum cannot exceed \(\sum V_i - \max(V_i)\).

1. By the properties of XOR, for any non-negative integers \(a\) and \(b\), \(a \oplus b \le a + b\) holds.
2. Let \(i^*\) be the person with the maximum initial value (\(V_{i^*} = \max V_i\)), and let their destination after \(K\) steps be \(q^* = dest(i^*, K)\).
3. The maximum value that Aoki subtracts is at least \(V'_ {q^*}\) (i.e., \(\max_{q} V'_q \ge V'_{q^*}\)).

Using these facts, we can upper-bound the sum after Aoki’s operation.

\[\sum_{q} V'_q - \max_{q} V'_q \le \sum_{q \neq q^*} V'_q\]

Here, the right-hand side is the sum of the XOR sums of the initial values of people \(i\) such that \(dest(i, K) \neq q^*\). This can also be upper-bounded by the sum of the individual elements.

\[\sum_{q \neq q^*} V'_q \le \sum_{dest(i, K) \neq q^*} V_i\]

This right-hand side is equal to the total sum \(\sum V_i\) minus the sum of the initial values of people \(i\) for whom \(dest(i, K) = q^*\). Since the set of people with \(dest(i, K) = q^*\) always includes \(i^*\) (as defined earlier), this sum is at least \(V_{i^*} = \max V_i\).

\[\sum_{dest(i, K) \neq q^*} V_i = \sum V_i - \sum_{dest(i, K) = q^*} V_i \le \sum V_i - V_{i^*} = \sum V_i - \max V_i\]

From the above, it is proved that no matter what \(A\) Takahashi chooses, the final sum can be at most \(\sum V_i - \max V_i\).

Since Takahashi can achieve this upper bound by setting \(A_i = i\), the answer when both players play optimally is always \(\sum V_i - \max(V_i)\).

Algorithm

1. Calculate the sum of the given array \(V\), sum(V).
2. Calculate the maximum value of the array \(V\), max(V).
3. Output sum(V) - max(V).

Complexity

• Time Complexity: \(O(N)\)
  • Since we find the sum and the maximum of the array by scanning it once each, it runs in \(O(N)\) time.
• Space Complexity: \(O(N)\)
  • Only the memory to store the input array \(V\) is required.

Implementation Notes

• Although the number of operations \(K\) can be as large as \(10^{18}\), the final result does not depend on \(K\), so there is no need to use the value of \(K\) in the implementation.

• The constraint \(N \le 12\) is very small, but this \(O(N)\) solution can quickly find the correct answer even for much larger constraints such as \(N \le 10^5\).

  Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    V = [int(x) for x in data[2:2+N]]
    
    ans = sum(V) - max(V)
    print(ans)

if __name__ == '__main__':
    solve()

---

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