TopCoder problem "LadderPermutation" used in SRM 332 (Division I Level Three)



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

0)
    
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}).
1)
    
3
2
2
Returns: {1, 3, 2 }
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.
3)
    
6
3
2
Returns: {2, 1, 4, 3, 6, 5 }
4)
    
6
2
3
Returns: {3, 2, 1, 6, 5, 4 }
5)
    
7
4
4
Returns: {1, 2, 3, 7, 6, 5, 4 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6175

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10012&pm=6175

Writer:

andrewzta

Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

Problem categories:

Greedy, Search