PROBLEM LINK:
Author: Vaibhav Tulsyan
Testers: Jakub Safin
Editorialist: Praveen Dhinwa
DIFFICULTY:
easy-medium
PREREQUISITES:
prefix-sums, data structures
PROBLEM:
You are given two arrays A, B each containing N integers. In a single operation, you can choose any index i (1 \leq i \leq N) and increment A_i by 1.
Find out minimum number of operations required such that A_i \bmod B_i is equal for all i, 1 \leq i \leq N.
SOLUTION
We want to make A_i \bmod B_i equal for all the 1 \leq i \leq N. Let K be this value. Note that K can’t greater than min(B_i) - 1.
The obvious approach is to iterate over all possible values of K, and for each of its value find the minimum cost required, and simply output the minimum of these costs.
So, lets see how to calculate the minimum cost to set all of the modulos to some particular value K.
- For all the positions having A_i \bmod B_i < K, you need to increment them until the value reaches K.
- For all the positions with A_i \bmod B_i > K, you need to make the values of A_i \bmod B_i reach zero first, and then increment them each K times.
Let us first rearrange the elements of the arrays A and B in increasing order of values A_i \bmod B_i.
Now, let’s see how to calculate the total number of operations required for first type. For each element i, we have to increment it K - A_i \bmod B_i times. Let L be the number of such elements of type 1. You can see that these elements will form a prefix of the rearranged array. Summing over all such elements, we get the total number of opeartions = K \cdot L - \sum\limits_{i = 1}^{L} {A_i \bmod B_i}. The quantity \sum\limits_{i = 1}^{L} {A_i \bmod B_i} can be computed by maintaining prefix sums over the values A_i \bmod B_i.
Now, let’s see how to calculate the second type of costs. All the positions that have A_i \bmod B_i > K will be some suffix of the rearranged array. You need to make the values of A_i \bmod B_i reach zero first. For each of the element i, such that A_i \bmod B_i > K, the cost required to make A_i \bmod B_i = 0 will be B_i - (A_i \bmod B_i) (note that it’s guaranteed that A_i \bmod B_i \neq 0 as A_i \bmod B_i > K, K \geq 0. The sum of the above quantity for each i in the suffix can be found using the suffix sums. Afterwards, we increase each of these elements by K, which contribution will be K \times number of such elements.
You can see #hemanth_1’s solution for a detailed explanation of this idea along with some examples.
Alternate approaches.
Please check meooow’s solution. It’s an alternate view of seeing this solution.