MOVHYPE - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

A theater has 2N+1 seats. The person in seat 2i-1 has a hype of A_i, while seats 2, 4, 6, \ldots, 2N are empty.
The loudness of an empty seat is the maximum of the hype levels of the two adjacent people.
Find the minimum loudness across all empty seats.

EXPLANATION:

Let’s compute the loudness of seat 2i.

This equals the maximum of the hype levels of the people in seats 2i-1 and 2i+1.
These two values are, by definition, A_i and A_{i+1}.

So, the loudness of seat 2i equals \max(A_i, A_{i+1}).

We want the minimum possible loudness, so the solution is to take the minimum of this quantity across all i.

That is, the answer equals

\min(\max(A_1, A_2), \max(A_2, A_3), \ldots, \max(A_N, A_{N+1})

This can easily be calculated using a simple for-loop.

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()))
    print(min(max(a[i], a[i+1]) for i in range(n)))