LadderPermutation

SRM 332 · 2006-12-28 · by andrewzta

SRM 332 · 2006-12-28 · by andrewzta · Greedy, Search

Show categories

Class Name: LadderPermutation

Return Type: int[]

Method Name: createLadder

Arg Types: (int, int, int)

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.

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 }

Submissions are judged against all 83 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LadderPermutation with a public method vector<int> createLadder(int n, int m, int k) · 83 test cases · 2 s / 256 MB per case