QuasiLatinSquares
SRM 392 · 2008-03-06 · by darnley
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
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.
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.
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.
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" }
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" }
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" }
10
10
Returns: {"0 1 2 3 4 5 6 7 8 9", "1 0 3 2 5 4 7 6 9 8", "2 3 0 1 6 7 8 9 4 5", "3 2 1 0 7 6 9 8 5 4", "4 5 6 7 8 9 0 1 2 3", "5 4 7 6 9 8 1 0 3 2", "6 7 8 9 2 3 4 5 0 1", "7 6 9 8 3 2 5 4 1 0", "8 9 4 5 0 1 2 3 6 7", "9 8 5 4 1 0 3 2 7 6" }
Submissions are judged against all 55 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class QuasiLatinSquares with a public method vector<string> makeSquare(int n, int d) · 55 test cases · 2 s / 256 MB per case