Overview

This is a problem where you simulate a single-elimination tournament and find the number of the winning robot.

Analysis

Understanding the Problem

In a tournament, adjacent pairs of robots compete against each other, and the one with higher combat power wins and advances. This continues until only one robot remains.

For example, with \(N = 4\) and combat power \(A = [3, 7, 2, 5]\): - Round 1: - Robot 1 (combat power 3) vs Robot 2 (combat power 7) → Robot 2 wins - Robot 3 (combat power 2) vs Robot 4 (combat power 5) → Robot 4 wins - Round 2 (Finals): - Robot 2 (combat power 7) vs Robot 4 (combat power 5) → Robot 2 wins

Therefore, Robot 2 is the champion.

Why a Naive Approach Works

In this problem, the number of robots is halved each round. Starting with \(N\) robots, there are \(\log_2 N\) rounds.

• Round 1: \(N/2\) matches
• Round 2: \(N/4\) matches
• …
• Final round: 1 match

The total number of matches is \(N/2 + N/4 + \cdots + 1 = N - 1\), which can be processed efficiently even when \(N \leq 2^{20} \approx 10^6\).

Algorithm

1. Store each robot as a pair “(combat power, robot number)” in a list
2. Repeat the following until only one robot remains:
   • Compare adjacent pairs and advance the one with higher combat power to the next round
   • Create a new list with the robots advancing to the next round
3. Output the number of the last remaining robot

Initial state: [(3,1), (7,2), (2,3), (5,4)]
    ↓ Round 1
[(7,2), (5,4)]
    ↓ Round 2
[(7,2)]
    ↓
Champion: Robot 2

Complexity

• Time complexity: \(O(N)\)
  • The total number of matches across all rounds is \(N/2 + N/4 + \cdots + 1 = N - 1\)
• Space complexity: \(O(N)\)
  • \(O(N)\) space is needed for the list storing robot information

Implementation Notes

1. Managing Robot Numbers: You need to keep track of not only the combat power but also the original robot number. It’s convenient to manage this using tuples (combat power, number).

2. Converting Between 1-indexed and 0-indexed: In the problem, robot numbers start from 1, but array indices start from 0. We handle this by storing the number as i + 1.

3. Processing Two at a Time: By using for i in range(0, len(robots), 2), we loop through indices 0, 2, 4, … with a step of 2, processing pairs robots[i] and robots[i+1].

Source Code

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    # Manage each robot as a (combat power, robot number) pair
    # Robot numbers are 1-indexed
    robots = [(A[i], i + 1) for i in range(N)]
    
    # Simulate the tournament
    while len(robots) > 1:
        next_round = []
        for i in range(0, len(robots), 2):
            # Adjacent robots compete, the one with higher combat power wins
            if robots[i][0] > robots[i + 1][0]:
                next_round.append(robots[i])
            else:
                next_round.append(robots[i + 1])
        robots = next_round
    
    # Output the champion robot's number
    print(robots[0][1])

solve()

---

This editorial was generated by claude4.5opus.