KCLOSE - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Sorting

PROBLEM:

You have an array A, whose elements you can increase by K as much as you like.
Find the minimum possible value of \max(A) - \min(A).

EXPLANATION:

First, note that since elements can only be increased by K, their value modulo K doesn’t change.
Furthermore, since elements can be increased as much as we like, we can always bring them into some ‘window’ of size K initially.
For instance, we can always ensure that every element lies in the range [10^9\cdot K, (10^9+1)\cdot K ) by repeatedly adding K to it till it lies in this range.
Now, every element differs by \lt K.
Notice that we can just pretend we have numbers in the range [0, K) now.

Let B_i = (A_i \bmod K) denote the remainder when A_i is divided by K, so B_i is the number we’re pretending A_i is.
Let’s sort the array B, so that B_i \leq B_{i+1}.

Notice that we can certainly get a value of B_N - B_1 as the difference between the minimum and maximum elements - in fact, this is exactly what our initial step of putting everything within a window of size K achieved: the difference between the maximum and minimum element is just the difference between the maximum and minimum remainders modulo K.

However, we can sometimes do a little better - for example, if we have 1 and K-1, it’s generally better to make the 1 into K+1 instead, since it’s closer to K-1.

Specifically, suppose we fix B_i to be the remainder of the smallest element.
Then,

  • For all j \lt i, we need to increase them (otherwise they’d be the smallest element instead).
    So, each of them goes to B_j + K.
    The largest element among them all is clearly just B_{i-1} + K (recall that B is sorted).
  • For all j \geq i, we can leave B_j unchanged.
    The largest among them is B_N (which is going to be smaller than B_{i-1} + K anyway, since B_N \lt K).

So, if we fix B_i to be the smallest element, the largest element will be B_{i-1} + K.
The difference obtained here is B_{i-1} + K - B_i.

The final answer is thus just

\min(B_N - B_1, \min_{i\gt 1} (B_{i-1} + K - B_{i}))

TIME COMPLEXITY:

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

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(n): a[i] %= k
    a = sorted(a)
    ans = a[-1] - a[0]
    for i in range(1, n):
        ans = min(ans, a[i-1]+k - a[i])
    print(ans)
1 Like