TopCoder problem "QuasiLatinSquares" used in SRM 392 (Division II Level Three)



Problem Statement

    

You are given two positive integers, n and d.

Create a square table of size n×n containing only integers between 0 and d-1, inclusive, such that each row and each column contains each number between 0 and d-1, inclusive, at least once.

Return this table as a String[] containing exactly n elements. Each element represents a single row of the table and contains a single space delimited list of the numbers in that row from left to right. The numbers must have no extra leading zeroes.

If there are multiple possible answers, return the one with the lexicographically smallest first element. If there is still a tie, return the one with the lexicographically smallest second element, etc.

 

Definition

    
Class:QuasiLatinSquares
Method:makeSquare
Parameters:int, int
Returns:String[]
Method signature:String[] makeSquare(int n, int d)
(be sure your method is public)
    
 

Notes

-A string S is greater than a string T lexicographically if T is a proper prefix of S, or if S has a greater character at the first position where the strings differ. A space character (' ') is considered smaller than any digit character ('0'-'9').
-It is guaranteed that there exists an answer for each valid input.
 

Constraints

-n will be between 1 and 10, inclusive.
-d will be between 1 and n, inclusive.
 

Examples

0)
    
3
3
Returns: {"0 1 2", "1 2 0", "2 0 1" }
If d equals n the desired table is called a Latin square. This is the lexicographically smallest Latin square of size 3.
1)
    
5
2
Returns: {"0 0 0 0 1", "0 0 0 0 1", "0 0 0 0 1", "0 0 0 0 1", "1 1 1 1 0" }
2)
    
5
4
Returns: {"0 0 1 2 3", "0 0 1 2 3", "1 1 0 3 2", "2 2 3 0 1", "3 3 2 1 0" }
3)
    
9
7
Returns: 
{"0 0 0 1 2 3 4 5 6",
"0 0 0 1 2 3 4 5 6",
"0 0 0 1 2 3 4 5 6",
"1 1 1 0 3 2 5 6 4",
"2 2 2 3 0 1 6 4 5",
"3 3 3 4 5 6 0 1 2",
"4 4 4 2 6 5 1 0 3",
"5 5 5 6 1 4 2 3 0",
"6 6 6 5 4 0 3 2 1" }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8561

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11126&pm=8561

Writer:

darnley

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem categories:

Search