PROBLEM LINK:
Author: Aleksa Plavsic
Tester: Hussain Kara Fallah
Editorialist: Hussain Kara Fallah
PROBLEM
You are given two integer sequences S1, S2, S3…SN, and T1, T2, T3…TM and an integer X.
You are allowed to perform the following operation any number of times:
Choose an element of S and an element of T (let’s denote them by Si and Tj respectively), then decrease both Si and Tj by X, i.e. replace Si by Si-X and Tj-X.
Let’s denote the minimum and maximum value in the sequence S after performing the chosen operations (possibly none) by minS and maxS respectively. Similarly, let’s denote the minimum and maximum value in T after performing the chosen operations by minT and maxT respectively. The goal is minimizing the expression (maxS+maxT)−(minS+minT). Compute the minimum value of this expression.
PREREQUISTES:
Basic Number Theory
CONSTRAINTS
N,M <= 5*105
All other values don’t exceed 109.
DIFFICULTY
Medium
EXPLANATION
A very important observation:
The answer is always no more than 2*X. Let’s try first to make all the values of one array in the range [0,X-1].
Let’s introduce:
sum_1 = \sum_{i = 1}^{N} \lfloor \frac{A_i}{X} \rfloor
sum_2 = \sum_{i = 1}^{M} \lfloor \frac{A_i}{X} \rfloor
For simplicity let’s assume that sum2 > sum1. We need to apply this operation sum1 times to the first array to make all values in the range [0…X-1]. Since sum2 > sum1 then we can pick sum1 pairs from both arrays and apply the operation.
The second array won’t be in the range [0…X-1] necessarily. We need to apply a few more sum2-sum1 operations to transform all numbers into that interval. Actually, we can do that, by picking each time a number from the second array with the maximum number in the first array (doing this operation sum2 - sum1 times). You can see that the difference between the maximum number and the minimum in the first won’t ever exceed X (Try to prove it, it’s easy).
Now we have the first array with maximum - minimum <= X and the second array has all numbers in the range [0…X-1].
By observing the problem a little bit, we can see that the optimal solution is to apply the same operation N*M times always by picking the maximum number in the first array and the maximum number in the second array. This will be enough to solve 2 subtasks. (because it’s the only way to keep the difference in each array no more than X) and we can prove that there is no optimal scenario where the difference between the max and the min in one of the arrays is more than X. It’s also obvious that N*M operations are enough because it’s the number of all rotations of first multiplied by the number of all rotations of the second.
If GCD(N,M) = 1, we can prove that for any pair of indices (the first index is from the first array and the second index from the second array), we can prove that we can fix them as the starting elements of our arrays by applying this operation a finite number of times (because GCD(N,M)=1). (Try the proof yourself).
Then the answer can be calculated easily. Let’s take the difference between every 2 consecutive elements in both arrays (take into account that last and first element are equal), our answer would be the sum of the minimum difference in the first + the minimum difference in the second.
If GCD(N,M)!=1 . We must group our numbers by their modulo to G (by G we mean GCD(N,M)). It would be possible also to fix any pair of elements ( ** Si, Tj ** each of them to be the starting number of its corresponding array) if and only if i Modulo G = j Modulo G.
As a conclusion, we take the differences between every 2 consecutive elements in both arrays, group them by modulo. For each group take the minimum possible difference. Check each modulo, and calculate the sum of the best differences (in both arrays). Our answer would be the minimum cost of all modulos.
Complexity
O(n log n + m log m) for sorting.
Rest of calculations can be done in O(n + m)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s/Editorialist’s solution can be found here.