Halloumi Boxes (Codeforces 1903A)
Tags: Greedy, sortings

Theofanis is busy after his last contest, as now, he has to deliver many halloumis all over the world. He stored them inside $$$n$$$ boxes and each of which has some number $$$a_i$$$ written on it. He wants to sort them in non-decreasing order based on their number, however, his machine works in a strange way. It can only reverse any subarray$$$^{\dagger}$$$ of boxes with length at most $$$k$$$.Find if it's possible to sort the boxes using any number of reverses.$$$^{\dagger}$$$ Reversing a subarray means choosing two indices $$$i$$$ and $$$j$$$ (where $$$1 \le i \le j \le n$$$) and changing the array $$$a_1, a_2, \ldots, a_n$$$ to $$$a_1, a_2, \ldots, a_{i-1}, \; a_j, a_{j-1}, \ldots, a_i, \; a_{j+1}, \ldots, a_{n-1}, a_n$$$. The length of the subarray is then $$$j - i + 1$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.Each test case consists of two lines. The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$) — the number of boxes and the length of the maximum reverse that Theofanis can make. The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$) — the number written on each box.

Output: For each test case, print YES (case-insensitive), if the array can be sorted in non-decreasing order, or NO (case-insensitive) otherwise.

Note: In the first two test cases, the boxes are already sorted in non-decreasing order.In the third test case, we can reverse the whole array.In the fourth test case, we can reverse the first two boxes and the last two boxes.In the fifth test case, it can be shown that it's impossible to sort the boxes.

Sample Inputs:
5
3 2
1 2 3
3 1
9 9 9
4 4
6 4 2 1
4 3
10 3 830 14
2 1
3 1

Sample Outputs:
YES
YES
YES
YES
NO

Solution (Python):
n = int(input())

def is_sorted(arr):
    prev = arr[0]
    for i in range(1, len(arr)):
        if prev > arr[i]:
            return 0
        prev = arr[i]
    return 1
for _ in range(n):
    arr = list(map(int, input().split()))
    arr1 = list(map(int, input().split()))
    if arr[1] > 1:
        print('YES')
    elif is_sorted(arr1):
        print('YES')
    else:
        print('NO')

Solution (Python):
def solve():
    (n, k) = map(int, input().split())
    numbers = list(map(int, input().split()))
    if numbers == sorted(numbers) or k > 1:
        print('YES')
    else:
        print('NO')
if __name__ == '__main__':
    for test in range(int(input())):
        solve()

Solution (Python):
for _ in range(int(input())):
    (n, k) = list(map(int, input().split(' ')))
    a = list(map(int, input().split(' ')))
    if a == sorted(a) or k != 1:
        print('YES')
    else:
        print('NO')