Bogosort

The trick is to stop staring at the condition like it insulted your mother and just algebra it.

Key observation

The array is bad if there exists a pair $i<j$ such that

$$j-a_j=i-a_i.$$

Rearrange it:

$$a_i-a_j=i-j.$$

Now look at the signs:

• since $i<j$, we have $i-j<0$,
• so any bad pair must satisfy $a_i-a_j<0$, i.e. $a_i<a_j$.

That means a bad pair can only happen when a later element is strictly larger than an earlier one.

So what arrangement completely kills that possibility?

A non-increasing arrangement.

Why descending order always works

Suppose we sort the array so that

$$a_1\ge a_2\ge \dots \ge a_n.$$

Take any $i<j$. Then $a_i\ge a_j$, so $a_i-a_j\ge 0$. Now compute

$$(j-a_j)-(i-a_i) = (j-i) + (a_i-a_j).$$

Here:

• $j-i>0$,
• $a_i-a_j\ge 0$.

Therefore,

$$(j-a_j)-(i-a_i) \ge j-i > 0.$$

So it is never equal to $0$, which means

$$j-a_j \ne i-a_i$$

for every pair $i<j$. Exactly what we need.

So the whole problem is hilariously simple:

• sort the array in decreasing order,
• print it.

The statement says a solution always exists. Cool. We don’t even need that promise, because descending order is always a solution.

Algorithm

For each test case:

1. Read $n$ and the array.
2. Sort it in descending order.
3. Output it.

Complexity

Sorting dominates:

$$O(n \log n)$$

per test case, with $O(1)$ extra space apart from the array.

Given $n\le 100$, this is absurdly safe.