PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Given an array A of length N, find any contiguous subarray of even length such that its median doesn’t equal its left middle element.
The median of an even length is its left middle element after sorting it.
EXPLANATION:
First, observe that if we choose a subarray that’s already sorted (in non-descending order), its median will surely equal its left middle element anyway.
So, the subarray we choose definitely cannot be sorted.
In particular, if A is itself already sorted, then every subarray of A is sorted too - so no valid subarray can exist, and the answer is -1.
That leaves the case where A is not sorted.
Now, if this is the case, observe that by definition there must exist an index i such that A_i \gt A_{i+1}.
Note that simply choosing the subarray [A_i, A_{i+1}] is now a valid answer!
This is because the true median of this subarray is A_{i+1} (the smaller of the two elements), while simply taking the “median” without sorting will give A_i. Since we know A_i \gt A_{i+1}, we’re done.
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()))
for i in range(n-1):
if a[i] > a[i+1]:
print(i+1, i+3)
break
else:
print(-1)