Halloumi Boxes

Problem

You are given an array a of n boxes. In one move you may pick any contiguous subarray of length at most k and reverse it. You may do this as many times as you like.

Decide whether the array can be made sorted in non-decreasing order. Print YES or NO.

Input:
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

Output:
YES
YES
YES
YES
NO

Approach

If k is 1 then we cant have pairs reversed therefore the input array needs to be already sorted. If k is greater than 1 then pairs can be created and since we are allowed to reverse any number of times, any arrays can be sorted (bubble sort). So this question just boils down to two condition:

• Value of k

• Is the array already sorted

• If k == 1 then the array needs to be already sorted. If Both the conditions are true, then we output YES else NO.

• If k > 1 then array can be sorted so we output YES

Code

#include <bits/stdc++.h>

using namespace std;
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }

    bool sorted = true;
    for (int i = 0; i < n - 1; i++) {
      if (a[i] > a[i + 1]) {
        sorted = false;
        break;
      }
    }

    if (k < 2 && !sorted) {
      cout << "NO" << "\n";
    } else {
      cout << "YES" << "\n";
    }
  }
}

Complexity

• time: O(n) per test case — one read pass and one comparison pass
• space: O(n) for the array, and it is only ever read; O(1) if you fold the sortedness check into the input loop by keeping the previous value