PROBLEM STATEMENT
A "group" is defined as a set of elements S, and a binary operator *, that
satisfy the following axioms:
1) For all x and y in S, (x*y) is in S
2) For all x, y, and z in S, (x*y)*z = x*(y*z) (* is associative)
3) There is an element e of S, called the identity element, such that (x*e)=x
and (e*x)=x for all x in S
4) For each x in S, there is an element y in S, called the inverse of x, such
that (x*y)=e and (y*x)=e
A group is called "Abelian" if it also satisfies the following axiom:
5) For all x and y in S, (x*y) = (y*x) (* is commutative)
For this problem, the elements of S are the first n capital letters of the
alphabet, where n is the number of elements in the String[]. The String[]
represents a "multiplication table" of * on the elements of S. For example,
suppose the multiplication table is:
{ "ABC",
"BCA",
"CAB" }
Then S has 3 elements: 'A', 'B' and 'C'. We can write the multiplication table
as follows:
| A | B | C
--------------
A | A B C
----
B | B C A
----
C | C A B
To find the result of, say, C*B, we first look in the row of the table
corresponding to 'C' (the third row), and then look at the column corresponding
to 'B' (the second column). So C*B is the entry of the table in row 3, column
2, or 'A'.
Similarly:
A*A=A A*B=B A*C=C
B*A=B B*B=C B*C=A
C*A=C C*B=A C*C=B
groupType will determine if S and * form a group.
If S and * do not satisfy axioms 1-4 above, return "NOT A GROUP" (quotes are
for clarification only)
If S and * satisfy axioms 1-4 but not axiom 5 above, return "NON-ABELIAN GROUP"
(note the '-')
If S and * satisfy axioms 1-5 above, return "ABELIAN GROUP"
Note: return values are case-sensitive
DEFINITION
Class: Group
Method Name: groupType
Parameters: String[]
Returns: String
Method signature (be sure your method is public): String groupType(String[]
table);
NOTES
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- table has between 1 and 20 elements, inclusive
- each element of the table has length equal to the number of elements in the
table
- table contains only capital letters ('A'-'Z')
EXAMPLES
Consider the multiplication table { "ABC", "BCA", "CAB" } discussed above.
In this case, S and * form a group, because:
Axiom (1) is satisfied for all elements of S. For example, A*C = C, which is
in S. If we had A*C = D, then A*C would not be in S, so (1) would not be
satisfied.
Axiom (2) is satisfied for all elements of S. For example, A*(B*C) = A*(A) =
A, and (A*B)*C = (B)*C = A. If we had A*B = C, then (A*B)*C = C*C = B, which
does not equal A*(B*C), so (2) would not be satisfied.
Axiom (3): A is the identity element because A*B = B*A = B, A*C = C*A = C, and
A*A = A.
Axiom (4): Every element has an inverse. For example, the inverse of B is C
because B*C = C*B = A (the identity element).
Also, this group is Abelian. For example, A*C = C*A. So groupType should
return "ABELIAN GROUP".
More examples:
groupType( "BBB",
"CCC",
"AAA" ) returns "NOT A GROUP"
groupType( "ABCD",
"BADC",
"CDAB",
"DCBA" ) returns "ABELIAN GROUP"
groupType( "FEBACD",
"CDABFE",
"EFDCAB",
"ABCDEF",
"BAFEDC",
"DCEFBA" ) returns "NON-ABELIAN GROUP"