BALASUB - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given an array A, find any subarray of length at least 2 that has an equal number of prefix and suffix maximums.

EXPLANATION:

Since we must find a subarray of length at least 2, let’s try looking at some small-length subarrays.

First, consider length-2 subarrays.
If the subarray is [x, y], then:

  • If x = y, there are two prefix and suffix maxima, so we’re done.
  • If x \lt y, there are two prefix maxima but only one suffix maximum.
    Similarly, if x \gt y, there are two suffix maxima but only one prefix maximum.

So, the only “good” case is when the subarray is [x, x], i.e. has two equal elements.
If this is the case, we’re done - otherwise we look further.

Next, consider a length 3 subarray, say [x, y, z].
Note that x\ne y and y \ne z since otherwise we’d have triggered the first case above already.

Observe that if y\gt x and y\gt z, then this subarray has two prefix and suffix maximums each so we’re done.

So, the only interesting case is when there’s no subarray of this form.

However, consider what it means for an array to not have adjacent equal elements, and also not have any “peaks”, i.e. elements larger than both neighbors.

Such an array must have a “V-shape”. That is, it will first strictly decrease till it reaches the minimum value, and then strictly increase after that.
(Note that the array may also be only strictly increasing/decreasing.)

Let’s look at subarrays of a V-shaped array.
There are only three possibilities:

  1. A strictly decreasing subarray (using elements to the left of the minimum)
    Such a subarray cannot be balanced (unless it has length 1), because there’s only one prefix maximum but every element is a suffix maximum.
  2. A strictly increasing subarray (using elements to the right of the minimum)
    For the same reason, this can’t be balanced.
  3. A V-shaped subarray (using elements that contain the minimum)
    Here, observe that if the two endpoints of the subarray have the same value, then the subarray will be balanced (since both endpoints will be the only prefix/suffix maximums).
    However, if the endpoints are different, then the subarray won’t be balanced - for example, if the left endpoint is larger, then there’s only one prefix maximum but more than one suffix maximum.

So, the only possible way of getting a balanced subarray, is when both endpoints have the same value.

Thus, if a V-shaped array contains repeated elements, a balanced subarray can be found (take any subarray with repeated elements as its endpoints), and if all elements are distinct, no solution exists.

All the checks are easy to implement in linear time.

Also note that we don’t need to explicitly perform the A_i = A_{i+1} check directly; since it will be found by the repeated element check anyway.

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(1, n-1):
        if a[i] > a[i-1] and a[i] > a[i+1]:
            print(i, i+2)
            break
    else:
        pos = [-1]*(n+1)
        for i in range(n):
            if pos[a[i]] == -1:
                pos[a[i]] = i+1
            else:
                print(pos[a[i]], i+1)
                break
        else:
            print(-1)