TopCoder problem "ColorfulDisks" used in TCHS07 Gamma 3 (Division I Level Two)



Problem Statement

    

You have several colorful disks of various sizes. You would like to build a pyramid of them by putting disks atop each other and using each disk exactly once. You are only allowed to put a disk of radius R1 atop a disk of radius R2 if R2 >= R1. For each pair of adjacent disks in the pyramid, the upper disk must be completely inside the lower disk when viewed from above. This means the lower disk will only be visible if it has a strictly larger radius than the upper disk.

You must build the pyramid in such a way that all visible disks have the same color when viewed from above. This color is called the color of the pyramid.

You are given a String[] disks, each element of which describes a single disk and is formatted as "color radius" (quotes for clarity). Return a String[] containing all possible colors of the pyramid in alphabetical order. If no pyramid can be built according to the rules, return an empty String[].

 

Definition

    
Class:ColorfulDisks
Method:singleColor
Parameters:String[]
Returns:String[]
Method signature:String[] singleColor(String[] disks)
(be sure your method is public)
    
 

Constraints

-disks will contain between 1 and 50 elements, inclusive.
-Each element of disks will contain between 3 and 50 characters, inclusive.
-Each element of disks will be formatted as "color radius" (quotes for clarity).
-In each element of disks, color will contain only lowercase letters ('a'-'z').
-In each element of disks, color will contain between 1 and 48 characters, inclusive.
-In each element of disks, radius will be an integer between 1 and 1000, inclusive, with no leading zeroes.
 

Examples

0)
    
{"red 1", "blue 1", "green 1"}
Returns: {"blue", "green", "red" }
In this case all disks have the same radius. Only the topmost disk of the pyramid will be visible, and it can have any of the colors.
1)
    
{"black 2", "white 1"}
Returns: { }
In this case there is no way to build a pyramid, because you can only put the white disk atop the black one, but you will see both disks.
2)
    
{"black 1", "white 1", "grey 1", "grey 2", "white 3", "black 3", "grey 3"}
Returns: {"grey" }
3)
    
{"red 1", "red 2", "red 3", "red 2"}
Returns: {"red" }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10720&pm=7556

Writer:

andrewzta

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Search, Sorting, String Parsing