A large committee of individuals is responsible for dealing with a wide variety
of problems that come up. Any problem can be described in terms of various attributes
about the problem. For instance, one problem may require a lot of planning, but not much
technical skill. Another might require a moderate amount of planning, and very little
technical skill.
Each member of this large committee has a certain ability level with respect to each of these
attributes. A problem requies a certain level of proficiency with each different attribute in order to be solved. When a group of people works together, the proficiency of the group with respect to an attribute `A` is the maximum proficiency of a group member on `A`.
Because the committee is large, it has been suggested that it be divided into subgroups,
so that the overall productivity of the committee can be improved. The productivity of a subgroup is described in terms of how large
a range of problems it can solve, and the productivity of the committee as a whole is the
sum of the productivity of the subgroups.
We can describe this system of attributes and abilities mathematically, by representing
each person as a point in *n*-dimensional space. (Where *n* is the number of
attributes we are examining.) The range of problems that can be solved by any group is then
the volume of the minimal bounding hyper-box around the origin, and each of the points in the group. For example, the points (3, 5) and (6, 2), would have a bounding box that extends from (0,0) to (6,5), so the potential productivity of the group is 6 * 5 = 30.
Your method, getGroups, is given String[] **members** as input. Each element is a space-delimited list of integers, representing the ability levels of a single member, with respect to each attribute. Each element will contain the same number of ability values. Your method should return a int[], where each element of the return is an integer between 0 and *n*-1, inclusive, indicating a group that the member should belong to. (*n* is the number of members) For instance, if there are five members, returning {0,1,0,1,1} would create a group of 2 (containing the first and third individual) and a group of three containing the remainder.
Test cases are generated as follows: The number of members is selected at random, between 50 and 10000, inclusive. The number of attributes to be assigned to each member is selected randomly, between 3 and 20, inclusive. Then, each ability value is assigned, again at random, between 0 and 99, inclusive. All ranges are inclusive, and all random choices are uniform.
Your score for an individual test case will be the d^{th} root of `volume/n*(1-time/100)`, where d is the number of dimensions and n is the number of members, and time is your execution time in seconds. Your overall score will simply be the sum of your scores on individual test cases. |