I have been thinking about a problem for a while. It is from OBI, the Brazilian Olympiad in Informatics. Can anyone give me some ideas/solutions to the problem? Sorry if there are some mistakes in the translation. ↵
Original link: https://olimpiada.ic.unicamp.br/pratique/p2/2011/f1/quadrado/ ↵
This is the statement:↵
↵
Given an $N$ x $N$ matrix, a _good choice of cells_ is a choice that every row and every column of the matrix has exactly one cell chosen. An _arithmetic square_ of size $N$ and sum $S$ is a matrix of integers of $N$ lines and $N$ columns that **all** _good choices_ has sum $S$ and all the numbers in the matrix are distinct. Your task in this problem is to generate an _arithmetic square_ of size $N$ and sum $S$, given $N$ and $S$. Each absolute value of the matrix has to be lower or equal to $10^9$.↵
↵
**Input**: $N$ and $S$, both integers with absolute value between $1$ and $1000$, inclusive. $S$ can be negative and $N$ is positive.↵
↵
**Output**: **Any** possible matrix that is an _arithmetic square_ of size $N$ and sum $S$.↵
↵
Input 1: ↵
2 49↵
↵
Output 1: ↵
23 40 ↵
9 26 ↵
↵
Input 2: ↵
3 53↵
↵
Output 2: ↵
-41 -29 2 ↵
28 40 71 ↵
11 23 54 ↵
↵
Input 3: ↵
1 -55↵
↵
Output 3: ↵
-55
Original link: https://olimpiada.ic.unicamp.br/pratique/p2/2011/f1/quadrado/ ↵
This is the statement:↵
↵
Given an $N$ x $N$ matrix, a _good choice of cells_ is a choice that every row and every column of the matrix has exactly one cell chosen. An _arithmetic square_ of size $N$ and sum $S$ is a matrix of integers of $N$ lines and $N$ columns that **all** _good choices_ has sum $S$ and all the numbers in the matrix are distinct. Your task in this problem is to generate an _arithmetic square_ of size $N$ and sum $S$, given $N$ and $S$. Each absolute value of the matrix has to be lower or equal to $10^9$.↵
↵
**Input**: $N$ and $S$, both integers with absolute value between $1$ and $1000$, inclusive. $S$ can be negative and $N$ is positive.↵
↵
**Output**: **Any** possible matrix that is an _arithmetic square_ of size $N$ and sum $S$.↵
↵
Input 1: ↵
2 49↵
↵
Output 1: ↵
23 40 ↵
9 26 ↵
↵
Input 2: ↵
3 53↵
↵
Output 2: ↵
-41 -29 2 ↵
28 40 71 ↵
11 23 54 ↵
↵
Input 3: ↵
1 -55↵
↵
Output 3: ↵
-55
