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

My deterministic solution to CSES — Distinct Sums Grid

Revision en3, by ocean_birb, 2026-08-17 18:08:42

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: $$$col_{i} = \frac{n \times (n - 1)}{2} + i - 1$$$ and $$$col_{1} = n ^ 2$$$
This construction give us a powerful fact that is there would always be atleast 1 matching position. Also, 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. Moreover 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 operations: 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}$$$
Doing this, we change $$$col_{1} = n ^ 2$$$ to $$$n \times (n - 1) + 2$$$ and $$$col_{j} = \frac{n \times (n - 1)}{2} + j - 1$$$ to $$$\frac{n \times (n - 1)}{2} + j - 3 + n$$$.

And $$$row_{i + 1} = 2 \times n - 1 + (n - 2) \times i$$$ to $$$2 \times n + (n - 2) \times i$$$, $$$row_{i + 2} = 2 \times n - 1 + (n - 2) \times (i + 1)$$$ to $$$2 \times n - 2 + (n - 2) \times (i + 1)$$$, this is true because $$$i + 1, i + 2$$$ is not $$$n - 1$$$ and $$$n$$$, which guarantee that $$$a_{i + 1, n} + 1 = a_{i + 2, n}$$$.

Consider $$$col_{1} = n \times (n - 1) + 2$$$: this is still the single largest value, so there is only one
        $$$row_{i + 1} = 2 \times n + (n - 2) \times i$$$: this value does not equal to any other rows or columns because the maximum column is $$$\frac{n \times (n - 1)}{2} + n - 1$$$, and since $$$i, j$$$ matches this value is smaller than $$$\frac{n \times (n - 1)}{2} + j - 3 + n$$$. Alongside the fact that $$$row_{i + 1} = 2 \times n + (n - 2) \times i = row_{i} + n - 2$$$, and because $$$row_{i} = col_{j}$$$:

$$$row_{i + 1} = 2 \times n + (n - 2) \times i = row_{i} + n - 2 = col_{i} + n - 2 = \frac{n \times (n - 1)}{2} + j - 3 + n \gt \frac{n \times (n - 1)}{2} + n - 1 $$$

        So there is only one sum equal $$$row_{i + 1}$$$
        $$$row_{i + 2}$$$ : the same as above, so there is also only one sum equal $$$row_{i + 2}$$$
        $$$col_{j} = \frac{n \times (n - 1)}{2} + j - 3 + n$$$ : after the increment, it now is larger than the $$$n\text{-th}$$$ column because it matches at a column with index larger than 2, the difference from that to the $$$n\text{-th}$$$ column is smaller than $$$n - 2$$$. This would have matched with the $$$i+1\text{-th}$$$ row but since we have changed it before, it now does not match with any row so there is only one appearance of this sum.
After doing all of the above, we would end up with a 2d matrix which satisfy the conditions.

Now i will be proving the claims above for $$$n \gt 4$$$, which is:
  $$$1. $$$ There would always be atleast 1 matching position.
  $$$2. $$$ There can only be one row's sum being equal to a column's sum.
  $$$3. $$$ From the third to last row onward, there can not be a match between these and any column.
  $$$4. $$$ The matching column can not be the second or the last.
Proof:
$$$1. $$$ It can be seen that the minimum of all column which is $$$col_{2} = 1 + \frac{n \times (n - 1)}{2} \gt row_{1} = 2 \times n - 1$$$ and the $$$n\text{-th}$$$ column which also is the second largest: $$$col_{n} = \frac{n \times (n - 1)}{2} + n - 1 \lt 2 \times n - 1 + n^n $$$. Which imply that there must be at least one matching position.
$$$2. $$$ For two of them to match, the matching column must be the second and the last column. You can visualize the value of the columns as a window of size n, while the difference between each column is n — 1. From this, we can try to find the first matching position $$$i$$$ by solving this equation:

$$$1\ +\ \frac{\left(n\ -\ 1\right)n}{2}=2\cdot n-1+\left(n-2\right)\cdot\left(i-1\right)$$$
$$$\implies \frac{n-1}{2}-\frac{n-1}{n-2}+1=i$$$

It can be shown that the function above only return positive interger for n = 2 and 4, so for $$$n /gt 4$$$ it return fractional numbers. From this, we can see that for n > 4 there can not be two matching positions.
$$$3. $$$ For it to match then $$$col_{n} \geq row_{n-2}$$$, which is the same as this inequation:

$$$n-1+\frac{\left(n-1\right)n}{2}-\left(2\cdot n-1\ +\ \left(n-3\right)^{2}+\left(n-2\right)\cdot2\right) \geq 0$$$
$$$\implies \frac{5}{2}x-\frac{x^{2}}{2}-5 \geq 0$$$

It can be shown that the inequation above have no real solution, so point proven.
$$$4. $$$ This is the direct result of $$$1. $$$, because no two matching so the position can not be the second or the last.
Example of the mentioned functions in desmos:

For the special case $$$n = 4$$$: we can just bruteforce to find the solution
               $$$n \le 3$$$: impossible

Code: Code

Thank you for reading my post, this is the first time i have ever written a blog, along with how bad i am at explaining so i expect a lot of criticism. Please point out what i could have done better so that i can improve, thank you so much!!

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)