PROBLEM STATEMENT
A jeweler needs a set of diamonds to complete an order. He needs a set of
diamonds satisfying an exotic requirement: for each pair of diamonds in the
set, either the diamonds need to be of the same size, or the larger diamond
needs to be less colored. The jeweler has access to a large lot of diamonds.
From that lot he needs to select the largest subset of diamonds satisfying his
requirement. Write a method that, given the size and the coloring information
of each diamond in the lot, returns the total weight of a subset of diamonds
that satisfies the jeweler's requirement, and includes more diamonds than any
other such subset. If multiple subsets with the same diamond count exist,
return the total weight of the one with the highest total weight.
DEFINITION
Class name: DiamondSet
Method name: largestSet
Parameters: String[]
Return type: int
Method signature (be sure your method is public): int largestSet (String[]
diamonds);
diamonds specifies the size and the color of each diamond in the jeweler's lot.
The string is formatted as follows (here and below, quotation marks and angular
brackets '<' and '>' are for clarity only)
"<SIZE><COLOR CODE>"
Diamond size is expressed in whole carat points (one carat point is 1/100 of a
carat); diamond color is expressed as a single-character code from 'D'
(colorless) to 'Z' (strong yellow color). For example, "95F" specifies a
diamond weighing 95 carat points (0.95 carats), with the color code 'F'.
Your method should return the total weight of a subset of diamonds such that
for each possible pair of diamonds in the subset, either the larger diamond is
less colored, or the diamonds are of the same size.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- diamonds contains 1 to 50 elements, inclusive.
- Each element of diamonds is formatted as "<SIZE><COLOR CODE>".
- <SIZE> is between 5 and 500, inclusive, with no leading '0' (zero) characters.
- <COLOR> is an upper-case letter from 'D' to 'Z', inclusive.
NOTES
- The total weight of a subset of diamonds should be taken into account only to
resolve conflicts between subsets with the same count of diamonds. For example,
if you have a subset of three diamonds with the total weight of 300 carat
points, and a subset of four diamonds with a total weight of 200 carat points,
your method should return 200.
- If there is only one diamond in the initial set, your method should return
that diamond's weight.
- Your method should *not* assume that the input set of diamonds is sorted in
any particular order.
EXAMPLES
1. If diamonds= {"10F"}, your method should return 10.
2. If diamonds= {"10F","10F","10F","10F","10F","10F"}, your method should
return 60.
3. If diamonds= {"10F", "20F"}, your method should return 20.
4. If diamonds= {"20X","30D","60Y"}, your method should return 50. This test
case shows how your method should prefer a subset with the larger diamond count
({"20X","30D"}) to a subset with a higher total weight ({"60Y"}).
5. If diamonds= {"300X","200Y","30D","20E"}, your method should return 500.
This test case shows how your method should prefer a subset with the highest
total weight out of multiple subsets with the same diamond count (in this case,
{"200Y", "300X"} vs. {"20E", "30D"}).
6.If diamonds= {
"345X","234F","234G","113Y","24D","480D","11X","28Y","80L","90K","112J","200M","
300E","450F"}, the largest subset that satisfies jeweler's criteria is {"480D",
"300E", "234F", "234G", "112J", "90K", "80L", "28Y"}. Your method should return
1558.
7. If diamonds= {"5D", "6E", "5F", "6G", "7H", "8D", "5E", "5X", "6Y", "9E",
"7F", "6H", "5K", "6J", "7H", "6J", "8S", "9W", "8Y", "5X", "9Z", "6R", "7V",
"9L", "8L", "7L", "6K", "5D", "9D", "9D", "9D", "8R", "7Q", "8Q", "5Q", "9G",
"8H", "7K", "5P", "6N", "8N", "9Z", "5Z", "5Z", "6X", "7X", "8X", "9X", "5D",
"7F"}, your method should return 118. This test case shows how your method
should not time out for large input sets.