LadderPermutation | Topcoder Archive

Problem Statement

You have n distinct integers between 1 and n, inclusive. A permutation of these integers is called an (m,k)-ladder permutation if its longest increasing subsequence has length m and its longest decreasing subsequence has length k. A subsequence is a sequence created by removing zero or more elements from an original sequence. The relative order of the remaining elements must be preserved. For example, {1, 3} is a subsequence of {1, 2, 3}, but {3, 2} is not. An increasing sequence is one in which each element is greater than the previous element, and a decreasing sequence is one in which each element is less than the previous element.

You are given ints n, m and k. Return a int[] containing the (m,k)-ladder permutation of size n. If there are multiple possibilities, return the one that comes first lexicographically. If there is no such permutation, return an empty int[]. Sequence A comes before sequence B lexicographically if A contains a lower value at the first position where they differ.

Definition

Class:: LadderPermutation
Method:: createLadder
Parameters:: int, int, int
Returns:: int[]
Method signature:: int[] createLadder(int n, int m, int k)
(be sure your method is public)

Constraints

n will be between 1 and 50, inclusive.
m will be between 1 and n, inclusive.
k will be between 1 and n, inclusive.

Examples

```
4
```
```
2
```
```
2
```
```
Returns: {2, 1, 4, 3 }
```
In this case, all longest increasing subsequences have length 2 (for example, {1, 3}), and all longest decreasing subsequences have length 2 (for example, {2, 1}).
```
3
```
```
2
```
```
2
```
```
Returns: {1, 3, 2 }
```
```
2
```
```
1
```
```
1
```
```
Returns: { }
```
In this case, the two numbers will always form an increasing or decreasing sequence of length 2. There is no permutation where the longest increasing/decreasing subsequence only has length 1.
```
6
```
```
3
```
```
2
```
```
Returns: {2, 1, 4, 3, 6, 5 }
```
```
6
```
```
2
```
```
3
```
```
Returns: {3, 2, 1, 6, 5, 4 }
```
```
7
```
```
4
```
```
4
```
```
Returns: {1, 2, 3, 7, 6, 5, 4 }
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.