USACO 2026 Third Contest, Bronze

Problem 1. Make All Distinct


Contest has ended.

Log in to allow submissions in analysis mode


You have an integer array $a_1\dots a_N$ with elements initially in the range $[1,N]$ ($1\le N\le 2\cdot 10^5$), as well as a nonzero integer $K$ ($-N \le K\le N, K\neq 0$).

You may perform the following operation as many times as you'd like (possibly zero): select an index $i$ and set $a_i=a_i+K$.

Find the minimum number of operations to make all array elements distinct.

INPUT FORMAT (input arrives from the terminal / stdin):

The input consists of $T$ ($1\le T\le 10$) independent tests. Each test is described as follows:

The first line contains $N$ and $K$.

The second line contains $a_1\dots a_N$.

It is guaranteed that the sum of $N$ over all tests does not exceed $10^6$.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test, output a single line containing the minimum number of operations.

Note: The large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

SAMPLE INPUT:

4
4 1
4 1 4 1
4 -3
4 1 4 1
4 4
4 1 4 1
3 -1
1 1 2

SAMPLE OUTPUT:

2
4
2
1

For the first test, here is a possible sequence of two operations that makes all elements distinct. 

4 1 4 1
5 1 4 1 (a_1 += 1)
5 1 4 2 (a_4 += 1)

SCORING:

  • Inputs 2-4: $N\le 50$
  • Inputs 5-7: $N\le 2000$
  • Inputs 8-10: $K=1$
  • Inputs 11-13: No additional constraints.

Problem credits: Akshaj Arora, Benjamin Qi

Contest has ended. No further submissions allowed.