TopCoder problem "GroupSkills" used in ()

Problem Statement

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.

Definition

Class:	GroupSkills
Method:	getGroups
Parameters:	String[]
Returns:	int[]
Method signature:	int[] getGroups(String[] members)
(be sure your method is public)

Notes

- The first few examples were generated with smaller sizes than the normal constraints, to help facilitate testing.

- The memory limit is 1024M.

- The time limit is 30 seconds per test case.

Constraints

- members will contain between 50 and 10000 elements, inclusive.

- Each element of members will be a space-delimited list of between 3 and 20 integers.

- Each element of members will contain the same number of integers.

- Each integer will be between 0 and 99, with no extra leading zeroes.

Examples

"10"

Returns: "There are 5 members, and 2 abilities.

 3  5
 6  2
60 83
79 84
38 26
"

This committee contains the two individuals referred to in the problem statement. In this case, the best we can do is to put the first two users in one group, and then have three more groups of single individuals. This gives a volume of 12634.

"11"

Returns: 
"There are 15 members, and 5 abilities.

38 26 23 94 99
76 32 18 60 72
 4 31 27 64 97
58 75  8 92 31
83 81 44 41 20
67 58 73 48 38
75 86 73 50 27
 3 86 71  8 69
 5 91 43 40 13
49 20 77 13 31
21 59 49 56 51
38 57 39 86 91
73 17 97 28 14
 7 36 22 57 67
66 41 42 74 19
"

The optimal volume here is over 1E10.

"12"

Returns: 
"There are 50 members, and 10 abilities.

21 91 40 93 30 87 14 44 68 33
86 55 40 43 51 77 53  8 42  3
16 27  9 70 72 42 36 14 92  2
15 41 19 69 68 99 31 33 85 58
12 98 61 10 60 17 51  3 58 90
95 35 58 12 46 56 25 67 86  5
89 95 44 30 58  3 90 40 30 25
79 68 10 53  4 70  5 49 20 51
94 86 97 22 41 53 70 51 69 25
 1 69 23 61 46 69 15 58 56 62
32 41 84 59 19 45 84 25 21 22
14 81 71 36 88 90 61 18 70 59
93 86 36 87 98 68 82 89 14 39
65 89 74 36 56  4 75  0 96 32
98 55 63 84 42 69 75 51 29 24
 7 31 85 98 60  1 63 56  1 90
21 43 43 46 28 73 83 59 22 77
12 91  2 85 37 89 75 77 39 91
72 62 77 91 50 36 83 27 89 11
31 21 53  5 46 65 12  2 46 52
46 13 55 73 23 50 16  3 66 33
68 48 33 16  5 89 91 25 71 47
88 79 64  2 97 20 68 59 44  7
83 88 81 16 61 58 72 81 67 31
85 41 65 54 13 63 52 15 69 54
39 87 86 92 37 60 94 14 44 30
35 28 20 17 50 44 10 37 33 78
56 79 50 16 45 24  9 44 93 95
96 21 68  6 70 16 61 20 57 37
70 60  5 28 32 86 23 90 38 81
75 40 52  8  0  3 24 55 18 42
46 51 39 13  1 60 75 23 21 32
92 39  2 68  7 15 33 16 52 13
 6 51 25 16  5  0  2 35 54 73
47 39 12 80 92 47 86 45 72 39
 0 24 66 73 52 67 43 94 53 77
48 88 97 29  4 81 53 47 26 55
87 16 83 18 78 89  2 87 18 86
26 58 92 12 16 52 82  4  2 83
12 48 70 54 43 86 49 99  5 38
67 95 87 95 68 70 79 31 52 95
17 81 29  9 38 42 81 10 69 58
58 48 85 14 47 37 33 64  4 85
68 26 57  8 90 27 69 78 86 99
96 84 28 68 16 77 92 42 52 34
14 52 41 52 28 36 75  2 27 91
78 77 23 21  0 15 24  2 19 98
98 12 76 23 31 35 77 76 74 71
33 14 77 42 14 99 94 13  7  1
86 41 51 18 21 81  8 93 24 77
"

"13"

Returns: "There are 200 members, and 20 abilities."

Download

"14"

Returns: "There are 1000 members, and 3 abilities."

Download

"15"

Returns: "There are 4958 members, and 3 abilities."

Download

"16"

Returns: "There are 8681 members, and 4 abilities."

Download

"17"

Returns: "There are 1626 members, and 13 abilities."

Download

"18"

Returns: "There are 137 members, and 9 abilities."

Download

"19"

Returns: "There are 10000 members, and 20 abilities."