PROBLEM STATEMENT
A Latin square is an n x n square containing n distinct symbols, each appearing
n times, exactly once in each row and column. For example, the following are
examples of 3x3 Latin squares:
A B C a b c
C A B and b c a
B C A c a b
Two Latin squares are orthogonal if when overlapped, they form a square
containing every possible combination of letter pairs from the original Latin
squares. For example, the above two are orthogonal because when overlapped,
every possible combination of letter pairs appears in the resultant square
(below). Such a square is called a Greco-Latin square.
Aa Bb Cc
Cb Ac Ba
Bc Ca Ab
There are 9 possible combinations of letter pairs, and each appears in the
above square.
You are to write a method where given two squares, returns which (if any) are
Latin squares, and if both are Latin squares, whether or not they are
orthogonal to each other. See examples.
DEFINITION
Class Name: GrecoLatin
Method Name: isGrecoLat
Parameters: String[], String[]
Returns: int
Method Signature (be sure your method is public): int isGrecoLat(String[] sq1,
String[] sq2);
NOTES
- The return value is based on the following:
a) If neither sq1 or sq2 represents a Latin square, return 0.
b) If sq1 represents a Latin square, but sq2 does not, return 1.
c) If sq2 represents a Latin square, but sq1 does not, return 2.
d) If both represent Latin squares, but they are not orthogonal to each
other, return 3.
e) If both represent Latin squares that are orthogonal to each other, return 4.
- To check that a given square is a Latin square, you need to check that each
symbol appears in each row and each column exactly once. You do not need to
check diagonals.
- To check that two Latin squares are orthogonal, you need to check that in the
overlap, every possible combination of letter pairs appears exactly once.
- You may not rearrange the letters in any row or column.
- The format of the input is as follows:
* The ith element of sq1 represents the ith row of the square. The only
legal characters in a String in sq1 are the first n uppercase letters, where n
is the number of elements in sq1. For example, if n = 4, the only allowable
letters are 'A', 'B', 'C', and 'D'.
* The ith element of sq2 represents the ith row of the square. The only
legal characters in a String in sq2 are the first n lowercase letters, where n
is the number of elements in sq2. For example, if n = 2, the only allowable
letters are 'a' and 'b'.
* Within a String, a letter is allowed to appear more than once, but this
would mean that the square is definately not a Latin square.
* Since n is at most 10, no letter after 'J' (or 'j') will ever be used.
TopCoder will ensure that:
- sq1 and sq2 each contain n elements, where n is between 1 and 10 (inclusive).
- The same n will be used for both squares, i.e. they are the same size.
- Each element of sq1 is a String of length n containing only the first n
UPPERCASE letters.
- Each element of sq2 is a String of length n containing only the first n
LOWERCASE letters.
EXAMPLES
1. sq1 = {"ABC", "CAB", "BCA"}, sq2 = {"abc", "bca", "cab"}.
We have already seen that these are both Latin squares and that they are
indeed orthogonal to each other. Return 4.
2. sq1 = {"ABCD", "BCDA", "CDAB", "DABC"}, sq2 = {"abcd", "bcda", "cdab",
"dabc"}.
It is easy to see that both are Latin sqaures:
A B C D a b c d
B C D A b c d a
C D A B c d a b
D A B C d a b c
But they are clearly not orthogonal:
Aa Bb Cc Dd
Bb Cc Dd Aa
Cc Dd Aa Bb
Dd Aa Bb Cc
We can see that certain letter pairs do not appear ("Ab" for example).
Alternatively, we can see that certain letter pairs appear multiple times ("Aa"
appears 4 times).
Since both are Latin squares, but they are not orthogonal, return 3.
3. sq1 = {"AB", "BA"}, sq2 = {"ab", "ab"}.
It is easy to see that the first sqaure is a Latin square, but the second
is not:
A B a b
B A a b
In the second square, "a" appears twice in the first column.
Since only the first is a Latin square, return 1.
4. sq1 = {"ABC", "BCA", "BAC"}, sq2 = {"acb", "bac", "cba"}.
Lets look at the picture:
A B C a c b
B C A b a c
B A C c b a
The first is not a Latin square because "B" appears twice in the first
column. The second sqaure is a Latin square. Return 2.
5. sq1 = {"AB", "AB"}, sq2 = {"aa", "bb"}.
A B a a
A B b b
It is easy to see that neither of these are Latin squares. Return 0.
6. sq1 = {"A"}, sq2 = {"a"}.
These represent trivial Latin squares (they satisfy all of the rules).
Furthermore, they are orthogonal to each other. Return 4.