1312BUnreviewed1000GPT-5.4 (high)

Bogosort

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

constructive algorithms sortings

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Rewrite the bad condition a little: if for some $i<j$ we have $j-a_j=i-a_i$ , then what does that say about $a_i-a_j$ ?

From $j-a_j=i-a_i$ , you get $a_i-a_j=i-j.$ But for $i<j$ , the right-hand side is negative. So a bad pair forces $a_i<a_j$ .

So ask yourself: what if the array had the opposite property everywhere — namely, for all $i<j$ , we had $a_i\ge a_j$ ?

In a non-increasing array, for $i<j$ we have $a_i-a_j\ge 0$ , hence $j-a_j-(i-a_i)=(j-i)+(a_i-a_j).$ Both terms are nonnegative, and $j-i>0$ .

That expression is actually strictly positive: $j-a_j-(i-a_i)=(j-i)+(a_i-a_j)\ge j-i>0.$ So equality is impossible. Therefore any array sorted in decreasing order is good. Just sort descending and print it. Done. Bogosort my ass.

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:

Read $n$ and the array.
Sort it in descending order.
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.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int &x : a) cin >> x;

        sort(a.rbegin(), a.rend());

        for (int i = 0; i < n; ++i) {
            if (i) cout << ' ';
            cout << a[i];
        }
        cout << '\n';
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int &x : a) cin >> x;

        sort(a.rbegin(), a.rend());

        for (int i = 0; i < n; ++i) {
            if (i) cout << ' ';
            cout << a[i];
        }
        cout << '\n';
    }

    return 0;
}

View on Codeforces Back to the list