PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: munch_01
Preparer: satyam_343
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
1390
PREREQUISITES:
None
PROBLEM:
There’s an array with N elements.
Alice will pick an index i, with 1 \leq i \leq N.
Bob will then pick an index j such that 1 \leq j \leq N and |i-j| = 1.
The score of this choice is |A_i - A_j|.
Alice wants to minimize this score while Bob wants to maximize it.
What is Alice’s optimal final score?
EXPLANATION:
Suppose Alice picks an index i. Then, Bob will can only pick index i+1 or i-1 (provided the index exists, of course).
So, once i is fixed, Bob will pick whichever one of those will maximize his score.
That is, the score is \max(|A_i - A_{i-1}|, |A_i - A_{i+1}|).
This can be easily computed for every index in \mathcal{O}(N).
Alice wants to minimize the score, so she will choose i that minimizes this.
So, once all the score above is computed for every index, simply take the minimum of them all.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = 10 ** 9
for i in range(n):
cur = 0
if i > 0: cur = max(cur, abs(a[i] - a[i-1]))
if i+1 < n: cur = max(cur, abs(a[i] - a[i+1]))
ans = min(ans, cur)
print(ans)