Help in Problem from Brazilian OI

Revision en5, by Leonardo_Paes, 2019-05-09 04:58:39

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Leonardo_Paes 2019-05-09 04:58:39 0 (published)
en4 English Leonardo_Paes 2019-05-09 04:53:00 1 Tiny change: 'ood choice_ has sum ' -> 'ood choices_ has sum '
en3 English Leonardo_Paes 2019-05-09 04:52:38 8 Tiny change: 'umns that any _good cho' -> 'umns that **all** _good cho'
en2 English Leonardo_Paes 2019-05-09 04:48:50 78 (saved to drafts)
en1 English Leonardo_Paes 2019-05-09 04:26:43 1273 Initial revision (published)