Overview

This problem asks you to divide \(N\) students into groups of \(K\) in order of their student numbers, keep only the student with the highest ability value in each group, and repeat this operation until one student remains, then determine the final winner.

Analysis

Understanding the Problem Structure

This problem is a tournament-style elimination. In each round, students are divided into groups of \(K\) from the front, and only the “strongest” in each group survives.

Concrete Example: For \(N = 7, K = 3\), with ability values \(A = [3, 1, 4, 1, 5, 9, 2]\):

• Round 1: Divide students into groups of \(K=3\)
  • Group 1: Student 1(3), Student 2(1), Student 3(4) → Student 3 (ability 4) wins
  • Group 2: Student 4(1), Student 5(5), Student 6(9) → Student 6 (ability 9) wins
  • Group 3: Student 7(2) → Student 7 remains as is
  • Remaining: [Student 3, Student 6, Student 7]
• Round 2: 3 students form 1 group
  • Group 1: Student 3(4), Student 6(9), Student 7(2) → Student 6 (ability 9) wins the tournament

Regarding Computational Complexity

In each round, we scan all remaining students once, so it takes \(O(n)\) (where \(n\) is the number of people in that round). Since the number of people decreases by a factor of approximately \(1/K\) each round, the total processing across all rounds forms a geometric series \(N + N/K + N/K^2 + \cdots\), which is \(O\left(\frac{NK}{K-1}\right) = O(N)\). Since \(K \geq 2\), this runs sufficiently fast.

A Naive Simulation Is Sufficient

In this problem, the number of people decreases rapidly, so simply simulating the process straightforwardly fits within the time limit without needing any special data structures or algorithms.

Algorithm

1. Store each student as a (student number, ability value) pair in a list.
2. While the list has 2 or more elements, repeat the following:
   • Partition the list into groups of \(K\) from the front.
   • Within each group, select the student with the highest ability value. If ability values are tied, select the student with the smallest student number.
   • Place only the selected students into a new list.
3. Output the student number of the last remaining student.

Complexity

• Time complexity: \(O(N)\)
  • Each round scans all students, and the number of people decreases by a factor of \(1/K\) each round, so the total number of scans is \(N \cdot \frac{K}{K-1} = O(N)\).
• Space complexity: \(O(N)\)
  • For storing the list of students.

Implementation Notes

• Selecting the winner: You could select the student with the maximum (ability value, -student number) within a group, but the code explicitly uses conditional branching to select the student who has “the highest ability value, or in case of a tie, the smallest student number.”

• Handling the last group: By using end = min(i + K, n), the last group is handled correctly even if it has fewer than \(K\) students.

• Fast input: sys.stdin.buffer.read() is used to read all input at once, speeding up input processing in Python.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    
    # Store (ability, index) - we want max ability, then min index
    # survivors is a list of (original_index, ability)
    survivors = []
    for i in range(N):
        survivors.append((i + 1, int(input_data[2 + i])))
    
    while len(survivors) > 1:
        new_survivors = []
        n = len(survivors)
        i = 0
        while i < n:
            end = min(i + K, n)
            # Find the winner in this group: max ability, then min index
            best_idx = i
            best_a = survivors[i][1]
            best_id = survivors[i][0]
            for j in range(i + 1, end):
                a = survivors[j][1]
                sid = survivors[j][0]
                if a > best_a or (a == best_a and sid < best_id):
                    best_a = a
                    best_id = sid
                    best_idx = j
            new_survivors.append(survivors[best_idx])
            i = end
        survivors = new_survivors
    
    print(survivors[0][0])

main()

This editorial was generated by claude4.6opus-thinking.