FIRSTCNT - Editorial

[iceknight1093]

PROBLEM LINK:

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

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Sorting

PROBLEM:

You’re given an array A with distinct elements.
Let f(X) be the index i such that |X - A_i| is minimized.
If there are multiple indices that attain minimum difference, choose the one with smallest A_i.

For each i, count the number of integers X such that f(X) = i.
If there are infinitely many such X, print -1 instead.

EXPLANATION:

If we are to have f(X) = i, we definitely need |X - A_i| \le |X - A_j| for all j \ne i.

When working with absolute differences, it’s often helpful to remove the ‘absolute’ part by considering the two cases separately.
Let’s do that here: we look at X \le A_i and X \gt A_i separately.

So, first let’s look at X \le A_i.
This means |X - A_i| = A_i - X.
Now, observe that:

• If A_j \gt A_i for some index j, then |X - A_j| = A_j - X, and this will definitely be strictly greater than A_i - X.
  So, we can just ignore elements larger than A_i here.
• If A_j \lt A_i, there’s potential for it to be closer to X than A_i.
  In particular, note that if there’s some A_j such that X \le A_j \lt A_i, then this A_j will definitely be closer to X than A_i is.

---

So, for some X \le A_i to be “valid”, it must be such that no element smaller than A_i comes between X and A_i.
Clearly, this means that among the elements \lt A_i, only the largest of them matters.
So, let’s define L to be the largest element of A that’s \lt A_i.

Suppose we know L.
Then, note that we now only care about X such that L \le X \le A_i.
Such an X can be valid if and only if (A_i - X) \lt (X - L), i.e. its distance to A_i is strictly less than its distance to L.
In any other case, L will be closer; and if the distances are equal then L will be chosen anyway because it’s the smaller element.

Rearranging the above inequality, we obtain (A_i + L) \lt 2X, or X \gt \frac{A_i + L}{2}.
So, all X that are \gt \frac{A_i+L}{2} and \le A_i are valid.

These form a contiguous range, so counting them is easy once the lower and upper bounds are known.
The upper bound is, of course, just A_i.
As for the lower bound:

• If \frac{A_i + L}{2} is an integer, then we need to be strictly greater than it, so the lowest valid integer is \frac{A_i + L}{2} + 1.
• If it’s not an integer, then we can simply round it up to the nearest integer instead.

A simple formula to represent this is \displaystyle \left\lceil\frac{A_i + L + 1}{2}\right\rceil, where \left\lceil \ \ \right\rceil denotes the operation of rounding up.

Note that there’s one edge case here: what if L doesn’t exist?
That is, what if A_i is the smallest element of the array?
In that case, observe that the answer is just -1, since every integer \le A_i will be valid, and there are infinitely many.

---

X \gt A_i can be analyzed similarly.
Here, what matters is the smallest integer in the array that’s \gt A_i, let’s call this R.
Then, X will be valid if X - A_i \le R - X, which in turn gives 2X \le A_i + R.
Note that equality is allowed here, because when the differences are equal, A_i will be chosen and not R (since A_i is smaller).

Once again, this will give some range of X that works, so find the appropriate bounds and then compute the length of the segment.

Here there is again the edge case of R not existing; which happens for only the largest element of the array.
Obviously, for this element the answer is -1.

---

There is only one detail remaining: if we know A_i, how do we quickly compute the values L and R, i.e. the nearest (by value) elements to A_i in the array?

This can be done in several ways; perhaps the simplest is to just sort the array A while remembering original positions.
That is, create a new array B that holds pairs of the form (A_i, i), and then sort B in ascending order.
Then, for each element in the (sorted) B, its neighbors in B will tell you the nearest elements that are smaller/larger than it.

TIME COMPLEXITY:

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

CODE:

Editorialist's code (PyPy3)

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = [(a[i], i) for i in range(n)]
    b.sort()
    
    ans = [-1]*n
    for i in range(n):
        if i == 0 or i == n-1: continue
        
        x, pos = b[i]
        L, R = b[i-1][0], b[i+1][0]
        # b[i]-x < x-L => 2x > b[i]+L => x > (b[i]+L)/2
        # x-b[i] <= R-x => 2x <= b[i]+R => x <= (b[i]+R)/2
        lo = (x+L+2)//2
        hi = (x+R)//2
        ans[pos] = hi - lo + 1
    print(*ans)