Overview

This problem asks us to divide \(N\) students into groups, conduct a knockout tournament, and determine the final winner. In each group, the student with the highest ability value wins (in case of a tie, the student with the smaller student number wins).

Analysis

In a straightforward approach, we simulate the group formation and winner selection in each round. In each round, the number of groups is approximately \(N/K\), and the number of rounds is approximately \(\log_K N\), so the overall time complexity is \(O(N \log_K N)\). The maximum value of \(N\) is \(500,000\). When \(K\) is large (e.g., close to \(N\)), the number of rounds is small and efficient. When \(K\) is small (e.g., \(K=2\)), the number of rounds is about \(\log_2 N \approx 19\), which is still sufficiently efficient.

Algorithm

1. Store all students in a queue in order of their student numbers (= input order). Each element is a tuple of (ability value, student number).
2. Repeat the following until only one student remains in the queue:
   • Take \(K\) students at a time from the front of the queue to form groups (the last group may have fewer than \(K\) students)
   • Select the student with the highest ability value in each group (in case of a tie, select the student with the smaller student number)
   • Add the selected winners to a new queue
3. Output the student number of the last remaining student

Complexity

• Time complexity: \(O(N \log_K N)\)
  • Each round processes in \(O(N)\), and the number of rounds is \(O(\log_K N)\)
• Space complexity: \(O(N)\)
  • Due to the use of a queue

Implementation Notes

• Using a deque allows efficient extraction and addition of elements during group formation

• By managing each student as a tuple of (ability value, student number), we can easily select the winner using the max function

• By specifying (x[0], -x[1]) as the key for the max function, we can select the student with the highest ability value, and in case of a tie, the student with the smallest student number

• During group formation, elements are extracted until the queue is empty or the group reaches \(K\) students

  Source Code

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    students = deque()
    for i in range(n):
        students.append((A[i], i + 1))
    
    while len(students) > 1:
        new_round = deque()
        group = []
        
        while students:
            group.append(students.popleft())
            if len(group) == k or not students:
                winner = max(group, key=lambda x: (x[0], -x[1]))
                new_round.append(winner)
                group = []
        
        students = new_round
    
    print(students[0][1])

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.