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
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)