ORDDIST - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

Sorting

PROBLEM:

You’re given an array X. An array Y was created from it as follows:

  • Choose a pivot index i_0, and let P = X_{i_0}.
  • Sort the elements of X by their distance from P, breaking ties by choosing the smaller element. This is the array Y.

You’re given the arrays X and Y. Find any valid choice of pivot index i_0, or say that none exist.

EXPLANATION:

Suppose we fix i_0.
Clearly, the closest element to X_{i_0}, is X_{i_0} itself.

So, if a valid pivot element exists, it has to be equal to the first element of Y.
The array elements are distinct, so this also immediately tells us the pivot index in X (which is whichever index contains the element equal to Y_1).

Let i_0 be the pivot index found this way.
Now that i_0 is known, we can simply construct the expected array Y by performing the given process, and check if it equals the array we’re given.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    x = list(map(int, input().split()))
    y = list(map(int, input().split()))
    
    p = y[0]
    order = list(range(n))
    order.sort(key = lambda i: (abs(x[i] - p), x[i]))
    good = True
    for i in range(n): good &= y[i] == x[order[i]]
    print(order[0]+1 if good else -1)
1 Like