PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: manaswirajne28, luvkansal29, himanshu2125
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
N people stand in a line to watch a performance. The i-th has height H_i.
A person can see the performance only if they are strictly taller than everyone ahead of them.
Every second, the last person, Bhoomi, can move one step forward in the line. How much time will it take for her to be able to see the performance?
EXPLANATION:
The constraints are small enough that simple simulation will work: repeatedly move Bhoomi one step forward, and check if everyone still ahead of her is smaller or not.
This will take quadratic time.
However, it is possible to solve the problem in linear time as well.
To do so, observe that only the leftmost person with height \geq H_N matters: if Bhoomi hasn’t crossed this person then they will block her, and if she has crossed them then everyone remaining is definitely shorter.
So, find the smallest index i such that H_i \geq H_N, and the answer is N - i since it will take that many moves for Bhoomi to reach position i.
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
h = list(map(int, input().split()))
ans, pos = 0, n-1
while pos > 0 and h[n-1] <= max(h[0:pos]):
pos -= 1
ans += 1
print(ans)