MINSMODM - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You have an array A of length N, with 0 \le A_i \lt M.
You can perform the following operation several times:

  • For every index i, replace A_i with (A_i + 1) \bmod M.

Find the minimum possible sum of A after performing this operation several times.

EXPLANATION:

If the operation is performed K times, the element at index i will become (A_i + K) \bmod M.

Observe that this means we’ll only ever need to perform \lt M operations.
This is because, if we perform M operations, the element at index i will become (A_i + M)\bmod M = A_i, so we could just as well not perform the first M operations.

Further, observe that when we perform an operation, every element will increase by 1, except for those elements equal to M-1, which will turn into 0 instead.

Now, suppose we perform K (0 \le K \lt M) operations. Let’s analyze how the array A changes.

  • First, consider elements that are “small” - that is, all i for which A_i \lt M - K.
    These elements will increase by 1 with each of the K operations made.
    So, they will increase by K in total.
  • Next, let’s look at the “large” elements - that is, A_i \ge M - K.
    These elements will increase till they reach M-1, then the next operation will set them to 0, and after that they’ll go back to increasing by 1 every operation.
    Since K \lt M, these elements will be reduced to 0 exactly once.
    These elements thus increase by one (K-1) times, and reduce by M-1 once.
    So, their overall change in value equals (K-1) - (M-1) = (K-M).

The nice thing that can be noticed here, is that the change in an element’s value doesn’t depend too much on its initial value at all: all elements \lt M - K will have the same change, and all elements \ge M - K will have the same change.

So, if there are Y elements in the array that are \lt M - K (and hence (N-Y) elements that are \ge M - K), the overall change in the sum of the array will equal

Y\cdot K + (N-Y)\cdot (K-M)

Our goal now is to compute the value of Y for a fixed K, i.e. the number of elements \lt M - K.
This can be done quickly in several ways:

  1. Let \text{freq}[x] denote the number of occurrences of x in the array.
    Then, the value we’re looking for is \text{freq}[0] + \text{freq}[1] + \ldots + \text{freq}[M-K-1].
    This is just a prefix sum of the \text{freq} array, so can be precomputed and then looked up in constant time.
  2. Alternately, you can binary search on A (after sorting it) to find the number of elements \lt M - K, for a complexity of \mathcal{O}(\log N).

In either case, once we fix a value of K, the quantity Y can be computed quickly.
Once Y is known, the change in the sum of A equals Y\cdot K + (N-Y)\cdot (K-M) as derived above.

The answer is then to simply take the minimum change in the sum of A across all values of K, and add it to the initial sum of A.

TIME COMPLEXITY:

\mathcal{O}(N + M) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    freq = [0]*m
    for x in a: freq[x] += 1
    
    pref = freq[:]
    for i in range(1, m): pref[i] += pref[i-1]
    
    ans = n*m
    for k in range(m):
        y = 0
        if m-k-1 >= 0: y = pref[m-k-1]
        ans = min(ans, k*y + (n-y)*(k-m))
    print(ans + sum(a))