You are given a permutation of size n, i.e. a sequence of n distinct numbers. The task is to partition this permutation into monotonic subsequences. The number of subsequences (syn.: partition) does not need to be minimum, but it has to be smaller than f(n), which denotes the minimum k such that any permutation of size n can be split into at most k subsequences.

Egor and an RPG game

They did provide a solution, but since I had a hard time understanding it, and I love proving things, I want to note down some of my insights and findings. Please let me know if you find any mistakes.

Observations

Let t be the greatest such that . Consider the permutation (size n) in which the first terms are 1, 3, 2, 6, 5, 4, 10, 9, 8, 7, ... (OEIS A038722), followed by the rest of terms sorted decreasingly. We call this sequence σ(n). For example:

•   σ(6) = {1, 3, 2, 6, 5, 4}
•   σ(8) = {1, 3, 2, 6, 5, 4, 8, 7}

What is the minimum number of monotonic partitions of σ?

We notice that σ can be seperated into several contiguous subarray, each subarray has decreasing elements. For example:

The number of such subarrays (denoted as m) is either t or t + 1, depends on whether or not. What is the minimum number of partitions of σ (denoted as g(σ))? We can easily tell that every element in the subarray l is less than any element in the subarray r, if l is on the left of r. We will use a greedy algorithm to compute g(σ). Let's say a, b is the number of increasing / decreasing subsequences.

1.  b = 0. If two elements are in the same subarray, they must belong to two different increasing subsequences. The biggest subarray size is t, and each element in this subarray belong to a distinct increasing subsequence, hence a = t.

2.  b ≠ 0. If we have a decreasing subsequence d, we have to expand it to the whole subarray. The action of expanding means we take some elments from other subsequences and bring them into d. This cannot add more subsequences, but can even remove some of them. So it's legit to expand. If we have chosen b subarrays to be b decreasing subsequences, a will be the max size of the other subarrays. So, those b decreasing subsequences should be the b biggest subarrays of σ to reduce a. For example, the sizes of the subarrays in σ(8) is: 1, 2, 2, 3 (t = 3); ; . With this in mind:

Which basically means the first method always yields the minimal g(σ). The second method is as effective, sometimes worse, but never better than the first method.

Conclusion: g(σ) = t.

What is the relation between f(n) and t?

It's easy to see that:

I cannot tell the exact value of f(n) (anyone?), but I can use t as the new upper bound instead of f(n). If we can partition any permutation into at most t subsequences, since we're guaranteed that t ≤ f(n). Such a solution will be immediately valid. We're near to solving the problem.

How to partition a permutation of n into at most t subsequences?

Let me remind you that t is the greatest such that .

We can make use of the classic problem "Longest Increasing Sequence" (or LIS). The algorithm is as follows:

1. If n = 0, we have nothing to do.
2. If , then we can immediately split the permutation into decreasing subsequences. (See more: Patience Sort). There, we did it!
3. Otherwise, we erase exactly t elements from the LIS, use them as a subsequence, leaving n - t elements, and t - 1 is the largest such that . Back to step 1, with updated parameters: t:  = t - 1.

The partitioning strategy is very elegant, though the proof and observation leading to the algorithm are so sophisticated.

See my implementation in C++. Special thanks to Radewoosh for this problem, I really enjoy it.