Editorial for CCC '19 S3 - Arithmetic Square - Olympiads Online Judge

Editorial for CCC '19 S3 - Arithmetic Square

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

We will not cover solutions to subtasks in this editorial. This may change in the future based on demand.

Note firstly that if a row or column has two integers that are filled in, the third one can be filled in directly, irrespective of whether it's adjacent to both of them or exactly one of them. We will assume that after filling in any given integer, this principle is applied.

For many grids, blindly applying this rule repeatedly will result in filling in the grid. There are only two cases remaining:

The first case is where a row or a column is completely filled in. Assume without loss of generality that a row is filled in. If no other entry is filled in, then we can duplicate the row twice. Otherwise, the grid looks something like this:

$\begin{bmatrix} a & a+d & a+2d \\ x & ? & ? \\ y & ? & ? \\ \end{bmatrix}$

Take the first row, increment everything by $x-a$ ~x-a~, and place it on the second row, do the same for the third row except increment by $y-a$ ~y-a~.

The second case is where no row or column is filled in:

Consider the following 3 by 3 grid:

$\begin{bmatrix} a & b & 2b-a \\ d & e & 2e-d \\ 2d-a & 2e-b & 4e-2b-2d+a \\ \end{bmatrix}$

Note that irrespective of how we choose the initial values of $a$ ~a~, $b$ ~b~, $d$ ~d~, and $e$ ~e~, we can always generate a valid square. Therefore, if all the known values fit in a $2 \times 2$ ~2 \times 2~ square, we can fill in the remaining values arbitrarily, and generate the square from there!

The only cases left to handle are the following:

$\begin{bmatrix} a & ? & ? \\ ? & ? & c \\ ? & b & ? \\ \end{bmatrix}$

$\begin{bmatrix} a & ? & ? \\ ? & b & ? \\ ? & ? & c \\ \end{bmatrix}$

In the first case, you can set the middle element equal to $b$ ~b~. In the second case, set one of the elements adjacent to both $a$ ~a~ and $b$ ~b~ equal to $b$ ~b~.

Comments

0

Tomorrow commented on June 3, 2020, 7:26 p.m. ← edited →

Note that this problem can be solved efficiently using elimination. Also, testing random numbers can pass.

8
Render_Main commented on June 9, 2020, 7:56 p.m.
The elimination solution in your link passes all test cases, including the additional cases. But I found a bug in the code. (line 178)

Consider the following input:

-1 X 7 X X X X X X

That program outputs:

-1 1073741823 7 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823

4

Moana commented on June 11, 2020, 6:25 a.m. ← edit 3 →

That bug has been fixed. See this submission: https://dmoj.ca/src/2138481

It solves a linear system of 4 variables and 8 equations in the worst case, instead of the original 9 variables and 15 equations.

From the second matrix in the editorial, one can see all valid solutions can be determined with 4 variables, which are $a$ ~a~, $b$ ~b~, $d$ ~d~, and $e$ ~e~ in the matrix.

In my new solution, I express the solution in this form:

$\displaystyle M=C_0\begin{bmatrix}4&2&0\\2&1&0\\0&0&0\end{bmatrix}+C_1\begin{bmatrix}-2&0&2\\-1&0&1\\0&0&0\end{bmatrix}+C_2\begin{bmatrix}-2&-1&0\\0&0&0\\2&1&0\end{bmatrix}+C_3\begin{bmatrix}1&0&-1\\0&0&0\\-1&0&1\end{bmatrix}$

My code solves for the coefficients $C_0$ ~C_0~, $C_1$ ~C_1~, $C_2$ ~C_2~, and $C_3$ ~C_3~ and determine the solution.

EDIT: Although I know my code doesn't always work, I tested $10^8$ ~10^8~ randomly generated cases and it fails none of them. If someone could give one not-working case I'd appropriate.

51

indra commented on March 10, 2019, 3:31 a.m.

Thank you, Mr. Troy Vasiga.

15

p1geon commented on March 10, 2019, 9:45 p.m.

🙏