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
In any choice of cells you will select every row once and every column once. Therefore you can attribute values to the rows and columns in such a way that V[i][j] = Value of row i + Value of column j. By doing this every choice of cells will have a sum equal to the summation of row values + summation of column values. So all you need to do is choose values for the rows and columns in such a way that the summation of all of those values is equal to S and there are no repeated elements in the matrix. There are many ways to do this.
Thank you so much!
Auto comment: topic has been updated by Leonardo_Paes (previous revision, new revision, compare).