Official Analysis (C++)

Solution

Consider the minimum number of needed subarrays. If this number is less than or equal to $k$ it is solvable using $k$ subarrays. To find the minimum number of subarrays, we can look for a configuration of subarrays where the number of subarrays is minimal. (Remember that the subarrays must be contiguous) Specifically, in this configuration, picture a single subarray. The order of the elements inside the subarray never change, so the order of the elements inside the subarray is the same before and after reordering the subarrays. This means that if we know the order of the sorted elements beforehand, we can apply a greedy algorithm which tries to maximize the size of the previous subarray.

For example, in the first testcase, the ordering of the elements is like so:

After sorting the list looks like so:

We may then create a map mapping each element to the element which should be before it:

With this map in mind, we generate the subsets as shown:

Thus, we need 4 subarrays at minimum.

Time Complexity: $\mathcal{O}(N\log N)$

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

void solve() {
	int n, k;
	cin >> n >> k;
	int arr[(int)1e5 + 5];
	int sarr[(int)1e5 + 5];
	for (int i = 0; i < n; i++) {
		cin >> arr[i];

Copy
import java.io.*;
import java.util.*;

public class MoamenSubarrays {
	public static void main(String[] args) throws IOException {
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(f.readLine());

		int testNum = Integer.parseInt(st.nextToken());
		for (int t = 0; t < testNum; t++) {

Copy
for _ in range(int(input())):
	n, k = map(int, input().split())
	arr = list(map(int, input().split()))

	sarr = arr.copy()
	sarr.sort()

	after = {}  # Map (dict) from one value to the value after it in the sorted array
	for i in range(n - 1):
		after[sarr[i]] = sarr[i + 1]