USACO 2026 Third Contest Bronze Division - Make All Distinct

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Residue classes are independent: A single operation adds \(K\) to one element, so \(a_i\) can only ever become one of \(a_i+tK\), \(t\ge 0\) --- all congruent to \(a_i\) modulo \(|K|\). Elements in different residue classes modulo \(|K|\) can never be made equal, so each class is solved separately and the costs are added. (Final values may leave \([1,N]\).)

Negative \(K\). Write \(K=-K'\) with \(K'>0\); element \(v\) then moves only along \(v-tK'\). The bijection \(\phi(x)=N+1-x\) satisfies \(\phi(v-tK')=\phi(v)+tK'\), so the instance with values \(N+1-a_i\) and step \(K'\) has exactly the same optimal cost. From now on assume \(K>0\).

Sort the values of one class ascending: \(v_1\le\dots\le v_m\). We must pick pairwise distinct finals \(f_i\ge v_i\) with \(f_i\equiv v_i \pmod K\); since each operation shifts a value by exactly \(K\), the class costs \(\sum_i (f_i-v_i)/K\). The greedy gives each element the smallest still-free spot on its chain: keep \(v_i\) if it exceeds the last value used in the class, otherwise take that value plus \(K\).

A global sort keeps every class in ascending relative order, so one sweep over the sorted array suffices, remembering only the last used value per class:

Why It Is Optimal

Take any valid assignment for a class. If \(v_i\le v_j\) but \(f_i>f_j\), swapping the two finals stays valid: \(f_j\ge v_j\ge v_i\) and \(f_i>f_j\ge v_j\); the cost sum and the congruences (all values of a class are congruent) are unchanged. Repeating such swaps, some optimum matches the sorted \(v\)'s to increasing finals \(f_1 \lt \dots \lt f_m\); distinctness plus congruence forces consecutive gaps of at least \(K\), hence \(f_i\ge\max(v_i,\,f_{i-1}+K)\).

Let \(g\) be the greedy finals and \(f\) any increasing valid assignment. Induction gives \(f_i\ge g_i\) for all \(i\): \(f_1 \ge v_1=g_1\), and if \(f_{i-1}\ge g_{i-1}\) then \(f_i \ge \max(v_i,\,g_{i-1}+K)\), while \(g_i\) is by construction the \emph{smallest} value congruent to \(v_i\) that is \(\ge \max(v_i,\,g_{i-1}+K)\). So \(g\) is pointwise minimal, and therefore minimizes the total cost.

The sort dominates: \(O(N \log N)\) time and \(O(N)\) memory per test. The answer can reach \(N(N-1)/2 \approx 2 \cdot 10^{10}\) (all values equal, \(K=1\)), hence the 64-bit integer type used in the reference code.

Source code

The source code for the solution in C++ can be seen below.

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 200000;

long long a[MAX_N + 1];
long long last_value[MAX_N + 1];

void solve() {
    int n;
    long long k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    if (k < 0) {
        k = -k;

        for (int i = 1; i <= n; i++) {
            a[i] = n + 1 - a[i];
        }
    }

    sort(a + 1, a + n + 1);

    for (int i = 0; i < k; i++) {
        last_value[i] = 0;
    }

    long long answer = 0;

    for (int i = 1; i <= n; i++) {
        long long value = a[i];
        int remainder = value % k;

        if (last_value[remainder] < value) {
            last_value[remainder] = value;
        }
        else {
            long long new_value = last_value[remainder] + k;

            answer += (new_value - value) / k;
            last_value[remainder] = new_value;
        }
    }

    cout << answer << "\n";
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}