PROBLEM LINK:
Author: Hanzala Sohrab
DIFFICULTY:
EASY
PREREQUISITES:
Sorting, Implementation, Arrays
PROBLEM:
Check if a given array can be sorted with maximum \frac{M(M - 1)}{2} - 1 swap operations.
EXPLANATION:
Number of swap operations is greater than \frac{M(M - 1)}{2} - 1 only when the array elements are already arranged in a strictly decreasing order. In all other cases, an array can be sorted within \frac{M(M - 1)}{2} - 1 swap operations.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main() {
cin.sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
int n, i;
cin >> n;
int l[n];
for (i = 0; i < n; ++i)
cin >> l[i];
bool possible = false;
for (i = 1; i < n; ++i)
if (l[i - 1] <= l[i])
{
possible = true;
break;
}
cout << (possible ? "YES\n" : "NO\n");
}
return 0;
}