STICKCOMP - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

There are N sticks, the i-th has size A_i.
Chef will pick up stick 1, and then for each i = 2, 3, \ldots, N in order, if A_i is strictly larger than his current stick, he will drop his current stick and pick up stick i.

Find the index of the last stick Chef will be holding.

EXPLANATION:

The process can simply be simulated in linear time.

Let x be the index of the stick Chef is holding.
Initially, x = 1.
Then, for each i = 2, 3, \ldots, N,

  • If A_i \gt A_x, set x = i.

In the end, print the value of x.

An alternate viewpoint is that the answer is simply the leftmost occurrence of the maximum element of A.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    m = max(a)
    
    for i in range(n):
        if a[i] == m:
            print(i+1)
            break