Blog entries - Codeforces

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	162
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

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 $\text{[math]}$ such that $\text{[math]}$ . Consider the permutation (size n) in which the first $\text{[math]}$ terms are 1, 3, 2, 6, 5, 4, 10, 9, 8, 7, ... (OEIS A038722), followed by the rest of $\text{[math]}$ 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:

$\text{[math]}$

The number of such subarrays (denoted as m) is either t or t + 1, depends on whether $\text{[math]}$ 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.

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.
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); $\text{[math]}$ ; $\text{[math]}$ . With this in mind:

$\text{[math]}$

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:

$\text{[math]}$

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 $\text{[math]}$ such that $\text{[math]}$ .

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

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