Overview

For each player, assuming they are the “absolute ace,” we calculate the number of increases needed so that they strictly exceed every other player in both attack and defense by at least 1, and find the minimum of these values.

Discussion

To make player \(i\) the ace, for all \(j \neq i\) we need: - \(A_i > A_j\) - \(B_i > B_j\)

Since training can only increase stats, it suffices to:

• Raise \(A_i\) to be 1 greater than the maximum attack power among all other players
• Do the same for \(B_i\)

The required number of increases is computed as follows:

• Required attack increases: \(\max(0, (\max_{j\neq i} A_j) + 1 - A_i)\)
• Required defense increases: \(\max(0, (\max_{j\neq i} B_j) + 1 - B_i)\)

The sum is the minimum number of training sessions to make that player the ace.

Why the naive approach doesn’t work

If we naively compute \(\max_{j\neq i} A_j\) and \(\max_{j\neq i} B_j\) for each \(i\), it takes \(O(N)\) per player for a total of \(O(N^2)\), which is too slow for \(N \le 2\times 10^5\).

Key insight

All we need is the “maximum after exclusion.” For each parameter, if we maintain: - The maximum value (top1) - The count of occurrences of the maximum - The second largest value (top2)

then we can compute \(\max_{j\neq i}\) for each player \(i\) in \(O(1)\).

For example, for attack power: - If player \(i\) is the sole holder of the maximum \(maxA1\), then the maximum after exclusion is \(maxA2\) - Otherwise (player \(i\) doesn’t have the maximum, or multiple players share the maximum), the maximum after exclusion is \(maxA1\)

The same applies to defense.

Algorithm

1. From the attack array \(A\), compute \((maxA1, cntA1, maxA2)\):
   • \(maxA1\): maximum value
   • \(cntA1\): count of the maximum value
   • \(maxA2\): second largest value
2. From the defense array \(B\), compute \((maxB1, cntB1, maxB2)\)
3. For each player \(i\), compute the following:
   • Maximum attack of other players \(maxA\_ex\):
     • If \(A_i = maxA1\) and \(cntA1 = 1\), then \(maxA2\)
     • Otherwise, \(maxA1\)
   • Maximum defense of other players \(maxB\_ex\) is computed similarly
   • Required training sessions: \(needA = \max(0, maxA\_ex + 1 - A_i)\) \(needB = \max(0, maxB\_ex + 1 - B_i)\) Total: \(needA + needB\)
4. Output the minimum of these totals as the answer.

Simple example

If the attack powers are \([5, 3, 5]\), the maximum is 5 and two players have it, so even after excluding one player with 5, another player with 5 remains. This means that player needs to raise their attack to \(5+1=6\) to become the ace (being equal is not enough — they must be “strictly greater”).

Complexity

• Time complexity: \(O(N)\) (computing the maximum and second maximum, plus scanning all players)
• Space complexity: \(O(N)\) (storing the input as arrays)

Implementation notes

• To correctly compute the “maximum after exclusion,” it is crucial to track how many times the maximum appears (if it appears once, use the second largest; if multiple times, the maximum remains).

• The condition is “strictly greater than,” not “greater than or equal to,” so the target is always \((maximum) + 1\).

• Since \(A_i, B_i\) can be up to \(10^9\), computations are safe with Python’s int, but it’s wise to initialize the answer to a sufficiently large value (the code uses \(10^{30}\)).

  Source Code

import sys

def two_max(values):
    max1 = -1
    max2 = -1
    cnt1 = 0
    for x in values:
        if x > max1:
            max2 = max1
            max1 = x
            cnt1 = 1
        elif x == max1:
            cnt1 += 1
        elif x > max2:
            max2 = x
    return max1, cnt1, max2

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    n = data[0]
    A = [0] * n
    B = [0] * n
    idx = 1
    for i in range(n):
        A[i] = data[idx]
        B[i] = data[idx + 1]
        idx += 2

    maxA1, cntA1, maxA2 = two_max(A)
    maxB1, cntB1, maxB2 = two_max(B)

    ans = 10**30
    for i in range(n):
        maxA_ex = maxA1 if (A[i] != maxA1 or cntA1 > 1) else maxA2
        maxB_ex = maxB1 if (B[i] != maxB1 or cntB1 > 1) else maxB2

        needA = max(0, maxA_ex + 1 - A[i])
        needB = max(0, maxB_ex + 1 - B[i])
        ans = min(ans, needA + needB)

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.