Farmer John's Favourite Operation — Editorial

References

Original problem: https://usaco.org/index.php?page=viewproblem2&cpid=1471

Community editorial: https://usaco.guide/problems/usaco-1471-farmer-johns-favorite-operation/solution

Prerequisites

Before getting into the problem itself, I think it's worth deriving some necessary background. Since this problem is filed under "prefix sums," I'll just assume prefix sums are all you know going in.

1. Minimizing the sum of |a^i - x|

Given a sequence a^n, find a number x such that the sum of the absolute differences between each term and x is minimized. The answer for x is the median of the sorted sequence. This is intuitive: imagine x sits "too far left" — then nudging it rightward makes the absolute differences on the left smaller and the ones on the right smaller, and this keeps holding until it reaches the median.

2. Congruence and modular arithmetic

The statement "a - b is divisible by M" can be written mathematically as a ≡ b (mod M), read as "a is congruent to b modulo M," or alternatively as "a divided by M leaves remainder b" — so b can be called the "remainder" in this context.

It can also be written as a = b + kM. Notice that this form expands "the possible values of a" into an arithmetic sequence:

a = {..., b - 2M, b - M, b, b + M, b + 2M, ...}

Suppose the divisor M is 9 and the remainder is 3. Then the possible values of a are:

a = {..., -15, -6, 3, 12, 21, 30, ...}

So, given a divisor M and a remainder b, choosing a is essentially picking one element out of this arithmetic sequence.

3. Converting a cycle into a chain (indices)

When you cut a segment out of a cycle, handling the indices directly gets messy if the segment happens to wrap around the end and back to the start. The usual move is to "unroll" the cycle into a chain. Picture a cycle:

0, 1, 2, 3, 4, 5

Now cut out the segment 5, 0, 1:

5, 0, 1

To build the chain we need, imagine splitting it into 5 and 0, 1 and completing each part's cycle:

0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5

You can see straight away that this chain has length 2n — it's just the flattened cycle with one more copy appended.

4. Converting a cycle into a chain (moduli)

Modular arithmetic is a special case. In the example above, a can take the values 3, 12, 21, ..., so every lap forward adds one M and every lap backward subtracts one M. For modular arithmetic, then, building the chain requires appending one copy in front and one copy behind.

If a is the chain formed by flattening the cycle, the chain we need to build is:

b = {a - M, a, a + M}

with length 3n.

Walkthrough

The problem gives an array a, and for an arbitrary number x, asks you to "transform" a so that every element of a minus x is divisible by M. Each transformation adds or subtracts 1 from an arbitrary element. Compute the minimum number of transformations.

So the target value of a can be written as x + k*M, where k is any integer. Getting an element of a from its original value to its target value takes a number of operations equal to the absolute difference between the two, since each transformation moves by exactly 1.

The problem therefore reduces to minimizing the total sum of |original a - target a|. Clearly, to make this difference minimal, all we need is to find the right target a.

If this weren't a cycle, then to minimize a sum of the form |a - x|, x would just be the median of the sorted a.

But with modular arithmetic — a cycle — the values that a itself can take are not fixed, so the median of the sorted a isn't fixed either, since you can add or subtract any multiple of M to the entire array.

Before we start, let's preprocess a: we can normalize it by taking each element mod M, then sorting. Why is taking the modulus allowed? Because the modulus just walks around the cycle in place — it doesn't change the distance from a to the next candidate value of a — and it gives us a direct ordering that makes sorting convenient.

That gives us the processed array a: [a1, a2, a3, ..., an].

Adding one lap in front and one behind gives a total length of 3n; call this array b:

a1 - M, a2 - M, a3 - M, ..., an - M, a1, a2, a3, ..., an, a1 + M, a2 + M, ...

Observe that on this chain, we can take each ai in turn as the median (where i denotes which element it is), extend left and right, and grab a subchain of length n. The ai serving as the median is the target value of a on that subchain.

Since there are n such subchains in total, we can enumerate the answers produced by the x values these subchains give, and take the smallest one.

So we start at a1, treat it as the midpoint, and extract a subchain of length n. On that subchain, we apply our d(a,x) formula to each element to compute its contribution, then add up the contributions.

However, this is O(n^2), which is basically unusable once n exceeds 10^5. So we optimize with prefix sums.

For a1 through an, we precompute the prefix sum array from left to right. Note that since the array is naturally sorted, every value to the left of the median x must be less than x, and every value to the right must be greater than x.

So each element on the left contributes x - a, and each element on the right contributes a - x.

When the subchain has length n, the left portion's contribution can be written as:

left_n * x - (a1 + a2 + ... + median x)

and the right portion's contribution as:

(first a after the median, summed through to the last a) - right_n * x

where left_n + right_n = n.

Each subchain is computed in O(1), and there are n subchains, so the complexity is O(n).

Implementation Notes

First, note that the prefix sums and the answer computation need int64 to avoid overflow; in C++, computing an int64 result from int32 operands requires an explicit widening cast on one side.

Note also that the walkthrough was phrased in terms of values — the implementation has to work in terms of indices. The indices of a1 through an are [n, 2n) in the b array.

If we take a[j] with n <= j < 2n as the median, then the left endpoint's index is j minus an offset, and the right endpoint's index is the left endpoint's index plus n-1, giving:

p = (n - 1) / 2
l = j - p
r = l + n - 1

A single j represents one window, and [n, 2n) gives n windows in total. For each window, the answer is the left subchain's contribution plus the right subchain's contribution, computed as in the pseudocode above, refined further here:

cost = (j - l - 1) * x - (P(j+1) - P(l)) // left subchain
    +  (P(r+1) - P(j+1) - (r - j) * x) // right subchain

Enumerate j from n to 2n, tracking the running minimum of cost — that is the answer to this problem.

C++ Implementation (my own approach)

Accepted.

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
int main() {
  // ! Only becase I was testing with file I/O
  auto& fin = std::cin;
  auto& fout = std::cout;

  int T;
  fin >> T;

  while (T--) {
    int N, M;
    fin >> N >> M;

    // * Preprocess a: mod M and sort
    std::vector<int> a(N);
    for (int i = 0; i < N; ++i) {
      fin >> a[i];
      a[i] %= M;
    }

    std::sort(a.begin(), a.end());

    // Construct b: {a - M, a, a + M}
    std::vector<int> b(3 * N);
    for (int i = 0; i < N; ++i) {
      b[i] = a[i] - M;
    }

    for (int i = 0; i < N; ++i) {
      b[i + N] = a[i];
    }

    for (int i = 0; i < N; ++i) {
      b[i + N * 2] = a[i] + M;
    }

    // Process prefix sum
    std::vector<long long> psum(3 * N + 1); // * Use long long
    for (int i = 0; i < 3 * N; ++i) {
      psum[i + 1] = psum[i] + b[i];
    }

    long long min_cost = LLONG_MAX;
    int offset = (N - 1) / 2;

    // For each index j as the median number
    for (int j = N; j < 2 * N; ++j) {
      int l = j - offset;
      int r = l + N - 1;
      long long median = b[j];

      long long left_cost = (j - l + 1) * median - (long long)(psum[j + 1] - psum[l]);
      long long right_cost = (long long)(psum[r + 1] - psum[j + 1]) - (r - j) * median;

      min_cost = std::min(left_cost + right_cost, min_cost);
    }

    fout << min_cost << "\n";
  }

  return 0;
}