Editorial for Yet Another Contest 7 P2 - Coprime Grid

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.

Author: Josh

Note that there are many possible constructions which are not illustrated in this editorial.

Subtask 1

Observe that every integer $X$ ~X~ is coprime with both $X-1$ ~X-1~ and $X+1$ ~X+1~. It would therefore be useful to have consecutive integers in adjacent cells. This motivates a 'snake' pattern, where an example is shown for $N = M = 5$ ~N = M = 5~:

 1  2  3  4  5
10  9  8  7  6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25

This grid is coprime because:

$1$ ~1~ is coprime with all integers, and so is coprime with the two integers adjacent to it.
$X$ ~X~ is adjacent to $X-1$ ~X-1~ and $X+1$ ~X+1~, for all $1 < X < N^2$ ~1 < X < N^2~.
$N^2$ ~N^2~ is adjacent to $N^2-1$ ~N^2-1~ and $(N-1)^2$ ~(N-1)^2~, which are both coprime with it. Note that $N-1$ ~N-1~ and $N$ ~N~ do not share any prime factors, so $(N-1)^2$ ~(N-1)^2~ and $N^2$ ~N^2~ must also have no prime factors in common.

Time complexity: $\mathcal{O}(NM)$ ~\mathcal{O}(NM)~

Subtask 2

Our construction from subtask 1 does not always work because $NM$ ~NM~ is not always coprime with $NM-2M+1$ ~NM-2M+1~. It's possible that $NM$ ~NM~ is coprime with neither $NM-2M+1$ ~NM-2M+1~ nor $NM-2N+1$ ~NM-2N+1~, so snaking vertically rather than horizontally does not work either. Instead, we can make a simple modification to our snake: we snake from $2$ ~2~ to $NM$ ~NM~, and place $1$ ~1~ in the remaining cell. For example, when $N = 5$ ~N = 5~ and $M = 6$ ~M = 6~, our construction looks like:

 2  3  4  5  6  7
13 12 11 10  9  8
14 15 16 17 18 19
25 24 23 22 21 20
26 27 28 29 30  1

This grid is coprime because:

$1$ ~1~ is coprime with all integers, and so is coprime with the two integers adjacent to it.
$2$ ~2~ is adjacent to $3$ ~3~ and $2M+1$ ~2M+1~, both of which are odd.
$X$ ~X~ is adjacent to $X-1$ ~X-1~ and $X+1$ ~X+1~, for all $2 < X < NM$ ~2 < X < NM~.
$NM$ ~NM~ is adjacent to $NM-1$ ~NM-1~ and $1$ ~1~, which are both coprime with it.

There is an alternate construction where we change the path that the snake takes, such that $NM$ ~NM~ ends up next to either $1$ ~1~ or $2$ ~2~. Any such grid would be coprime because:

$1$ ~1~ is coprime with all integers, and so is coprime with the two integers adjacent to it.
$X$ ~X~ is adjacent to $X-1$ ~X-1~ and $X+1$ ~X+1~, for all $1 < X < NM$ ~1 < X < NM~.
$NM$ ~NM~ is adjacent to $NM-1$ ~NM-1~, and either $1$ ~1~ or $2$ ~2~, which are both coprime with it. We can show that if $NM$ ~NM~ is next to $2$ ~2~, it is coprime with it; if we checkerboard the grid, alternating black and white cells, we see that integers of the same parity are in the same colour of cell. Since $NM$ ~NM~ and $2$ ~2~ would be in different coloured cells, they must have opposite parities, so $NM$ ~NM~ is odd and therefore coprime with $2$ ~2~.

Time complexity: $\mathcal{O}(NM)$ ~\mathcal{O}(NM)~

Comments

There are no comments at the moment.