MAXMINCRCDIF Editorial

DIFFICULTY:

3304

First, sort the array. There are two cases.

  • N is odd. Let K = \frac{N+1}{2}

Clearly, among any K consecutive integers in A, at least two will be neighbors on the circle. So, for any i, there is a consecutive absolute difference of at most A_{i + K - 1} - A_i for each i from 1 to N - K + 1.

It turns out that this bound is achievable: just put numbers in order A_1, A_{K+1}, A_2, A_{K+2}, \ldots, A_{K-1}, A_{2K-1}, A_K: here indexes of any two neighbors differ at least by K-1.

  • N is even. Let K = \frac{K}{2}.

Again, among any K+1 consecutive integers in A, at least two will be neighbors on the circle. In let’s call i supreme if among A_i, A_{i+1}, \ldots, A_{i + K - 1}, no two integers are neighbors on the circle. This means that they stand on all even (or on all odd) positions. Therefore:

  • If 1 (or K+1) is supreme, then K+1 (or 1) is supreme, and no other integer can be supreme.

  • If 2 \le i \le K is supreme, no other integer can be supreme.

What does this mean for our minimum M among adjacent differences? For any i that’s not supreme, it doesn’t exceed A_{i + K - 1} - A_i. For supreme i, it doesn’t exceed A_{i + K} - A_i.

So, what we should do is the following: let 1 \le best \le K+1 be such that A_{best + K - 1} - A_{best} is smallest. To try to make M>A_{best + K - 1} - A_{best}, we need to make best supreme. Now, let’s show how we can make i supreme while at the same time making sure that indexes of any two adjacent elements differ by at least K-1 (it turns out, it’s possible for any i!)

If we want to make 1 supreme, just order elements as A_1, A_{K+1}, A_2, A_{K+2}, \ldots, A_K, A_{2K}. Now suppose 2 \le i \le K.

from A_i to A_{i + K - 1}

Then, order integers as follows: A_{K+1}, A_{2}, A_{K+2}, A_{3}, A_{K+3}, \ldots, A_{i - 1}, A_{i + K - 1}. Then, add A_1, A_K. This way we have build a “bridge” from A_{K+1} to A_K. Go back the same way: through path A_K, A_{2K-1}, A_{K-1}, A_{2K-2}, \ldots, A_{i+K}, A_{i}. Then, add A_{2K} and A_{K+1}.

2 Likes