Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

My deterministic solution to CSES — Distinct Sums Grid for n > 4

Revision en1, by ocean_birb, 2026-08-16 20:24:03

Problem link: CSES — Distinct sums grids
Problem statement:
Create an $$$n \times n$$$ grid that fulfills the following requirements:
  $$$1. $$$ Each integer $$$1 \dots n$$$ appears n times in the grid.
  $$$2. $$$ If we create a set that consists of all sums in rows and columns, there are 2n distinct values.

My solution:
For a given $$$n \gt 4$$$, create a $$$n \times m$$$ matrix named A, every element in A will be as follow:

$$$ a_{i,j} = \begin{cases} n, & j = 1,\\ i, & j \gt i,\\ i-1, & 2 \le j \le i. \end{cases} $$$

For example, n = 6 would look like this:

$$$ A = \begin{pmatrix} 6 & 1 & 1 & 1 & 1 & 1\\ 6 & 1 & 2 & 2 & 2 & 2\\ 6 & 2 & 2 & 3 & 3 & 3\\ 6 & 3 & 3 & 3 & 4 & 4\\ 6 & 4 & 4 & 4 & 4 & 5\\ 6 & 5 & 5 & 5 & 5 & 5 \end{pmatrix} $$$

Now it can be seen that for each row $$$i$$$ from 1 to n, its sum is as follow: $$$row_{i} = 2 \times n - 1 + (n - 2) \times (i - 1)$$$
For each column from 2 to n, its sum is as follow: $$$column_{i} = \frac{n \times (n - 1)}{2} + i - 1$$$. And for the first columns, its sum is $$$n ^ 2$$$
This construction give us a powerful fact that is there can only be one row's sum being equal to a column's sum, and from the third to last row onward, there can not be a match between these and any column. Also the matching column can not be the second and the last. This is true for $$$n \gt 4$$$ and will be proven later in this blog.
From this we can do the following procedure: Find the matching row and column $$$i, j$$$, swap $$$a_{2, 1}, a_{2, j}$$$, and then swap $$$a_{i + 1, n}, a_{i + 2, n}$$$

Tags cses, constructive

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English ocean_birb 2026-08-17 18:08:42 50 adding example code cause i forgot
en2 English ocean_birb 2026-08-17 11:14:24 5576 saving (published)
en1 English ocean_birb 2026-08-16 20:24:03 1695 Initial revision (saved to drafts)