TopCoder problem "TheGarland" used in TCHS09 Final Round (Division I Level Three)



Problem Statement

    

When all the presents are delivered to the children, Santa Claus goes home to take some rest. Then, the most exciting part of the day begins - Santa starts making garlands. A garland is a sequence of lamps connected with a wire. You are given a String[] lamps containing the available lamps. Each element is formatted "color size" (quotes for clarity), where color is a string representing the lamp's color, and size is an integer representing the lamp's size. A garland must contain every available lamp, and every pair of consecutive lamps in a garland must have different sizes.

Santa will make every possible garland using these lamps. Each time he makes a garland, he will turn it on for a while and then disassemble it to make another one. Every garland he makes will be different. Two garlands are different if they have different lamps in at least one position. Santa will make one garland before another if it has a bigger first lamp. In case of a tie, he will choose the garland whose first lamp's color comes earlier alphabetically. If both garlands have the same first lamp, he will make his choice according to the second lamp, and so on. He will go to sleep after making all possible garlands.

Return a String[] containing the n-th garland Santa will make, where n is a 1-based index. The return String[] should be a permutation of the String[] lamps. If Santa will make less than n garlands, return an empty String[] instead.

 

Definition

    
Class:TheGarland
Method:find
Parameters:String[], int
Returns:String[]
Method signature:String[] find(String[] lamps, int n)
(be sure your method is public)
    
 

Constraints

-lamps will contain between 1 and 50 elements, inclusive.
-All elements of lamps will be distinct.
-Each element of lamps will be formatted "color size", where color is "Red", "Green", "Blue" or "Yellow", and size is an integer between 1 and 1,000,000,000, inclusive, with no leading zeroes (all quotes for clarity).
-n will be between 1 and 1,000,000,000, inclusive.
 

Examples

0)
    
{"Red 5", "Yellow 9", "Red 9", "Green 1"}
4
Returns: {"Red 9", "Green 1", "Red 5", "Yellow 9" }
Here are the first four garlands made by Santa:
  • {"Red 9", "Red 5", "Yellow 9", "Green 1"}
  • {"Red 9", "Red 5", "Green 1", "Yellow 9"}
  • {"Red 9", "Green 1", "Yellow 9", "Red 5"}
  • {"Red 9", "Green 1", "Red 5", "Yellow 9"}
1)
    
{"Yellow 47", "Blue 47"}
1
Returns: { }
It is impossible to make any garlands since the two lamps are of equal size and therefore cannot be next to each other.
2)
    
{"Green 4", "Blue 4", "Yellow 100"}
2
Returns: {"Green 4", "Yellow 100", "Blue 4" }
Only two possible garlands.
3)
    
{"Yellow 21", "Blue 24", "Red 29", "Blue 27", "Green 21", "Green 27", "Yellow 24", "Yellow 28"}
19
Returns: 
{"Red 29",
"Yellow 28",
"Blue 27",
"Yellow 24",
"Yellow 21",
"Blue 24",
"Green 27",
"Green 21" }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13731&pm=10282

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming