6
$\begingroup$

I have a square grid of size $N$, with rows numbered from $0$ to $N - 1$ starting from the top and columns numbered from $0$ to $N - 1$ starting from the left.

A cell $(u, v)$ refers to the cell that is on the $u$-th row and the $v$-th column. Each cell contains an integer $0$ or $1$. I can pick any cell and flip the number in all the cells (including the picked cell) within the distance $D$ from the picked cell. A flip here means changing the number from $0$ to $1$ and vice-versa. The distance from the cell $(u, v)$ to the cell $(x, y)$ is equal to $|u - x| + |v - y|$ where $|i|$ is the absolute value of $i$.

Now,I want to change all values in the grid to zero without using more than $N\cdot N$ flips. If not possible tell that its not possible. Otherwise i want to tell the total moves required to achieve it. Along with the position of cells on which the operation is to be performed.

EXAMPLE : Say i have $3\times 3$ grid and the distance $d = 1$.

$$\begin{array}{|c|c|c|} \hline 0&1&0\\ \hline 1&1&1\\ \hline 0&1&0\\ \hline \end{array}$$

Then clearly its possible to change all cells to zero by performing the first operation in the center cell, this will flip all the elements to $0$ within $1$ distance.

For a not possible case we can take a example :

Say i have $3\times 3$ grid and the distance $d = 2$.

$$\begin{array}{|c|c|c|} \hline 1&0&1\\ \hline 1&1&0\\ \hline 0&0&0\\ \hline \end{array}$$

ITS NOT POSSIBLE TO GET ALL ZEROS IN THIS CASE.

How to tackle this problem .? PLZ HELP

$\endgroup$

1 Answer 1

3
$\begingroup$

This is a linear algebra problem.

First note that there is no point in playing the same square twice. Each square should be played once, or not at all.

Consider the grid: \begin{array}{|c|c|c|c|} \hline a_{11}&a_{12}&a_{13}&a_{14}\\ \hline a_{21}&a_{22}&a_{23}&a_{24}\\ \hline a_{31}&a_{32}&a_{33}&a_{34}\\ \hline a_{31}&a_{42}&a_{43}&a_{44}\\ \hline \end{array}

Define $a$ as when $a_{yx} = 1$ you play the square, when $a_{yx} = 0$ you don't play the square. Then you can see that $a$ is the variable you want to solve for, and it is constrained by a set of linear equations shown below.

Let $b_{yx}$ be the initial values of the grid. Write out the statement "location y x becomes zero":

$b_{y, x} + \sum_{u,v}^{N,N} a_{u,v} \cdot (|u - x| + |v - y| \le_{1/0} D) \equiv 0 \pmod 2$

(Here I'm using $m \le_{1/0} n$ to mean "1 if $m \le n$ and 0 otherwise".)

...for example the the equation "the top left corner becomes zero for D=2" is:

$\begin{align} b_{11} & + a_{11}\cdot 1 + a_{12}\cdot 1 + a_{13}\cdot 1 + a_{14}\cdot 0 \\ & + a_{21}\cdot 1 + a_{22}\cdot 1 + a_{23}\cdot 0 + a_{24}\cdot 0 \\ & + a_{31}\cdot 1 + a_{32}\cdot 0 + a_{33}\cdot 0 + a_{34}\cdot 0 \\ & + a_{41}\cdot 0 + a_{42}\cdot 0 + a_{43}\cdot 0 + a_{44}\cdot 0 \equiv 0 \pmod 2 \end{align}$

This is a linear equation in $a$, the variable you need to solve for.

Build your $N^2 \times N^2$ matrix and solve for $a$:

$\begin {bmatrix} & \cdots \\ \vdots & \end{bmatrix} \begin{bmatrix} a_{11} \\ a_{12} \\ \vdots \end{bmatrix} \equiv \begin{bmatrix} -b_{11} \\ -b_{12} \\ \vdots \end{bmatrix} \pmod 2 $


Example as requested:

Consider the following initial position: $$b = \begin{array}{|c|c|c|c|} \hline 1&0&0\\ \hline 0&1&0\\ \hline 0&0&1\\ \hline \end{array}$$

Let $D = 1$.

The top left square is only affected by changes to 3 locations, $a_{11}, a_{12}, a_{21}$ : $$1 + a_{11} + a_{12} + a_{21} \equiv 0 \pmod 2$$ The center square is affect by changes to 5 locations: $$1 + a_{12} + a_{21} + a_{22} + a_{23} + a_{32}\equiv 0 \pmod 2$$ The bottom middle square is affected by changes to 4 locations: $$0 + a_{22} + a_{31} + a_{32} + a_{33} \equiv 0 \pmod 2$$

And so on, you can get 9 equations total like this.

Write them as a matrix: $$\begin{bmatrix}1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\cr 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0\cr 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0\cr 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0\cr 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0\cr 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1\cr 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0\cr 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1\cr 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1\end{bmatrix} \begin{bmatrix} a_{11} \\ a_{12} \\ a_{13} \\ a_{21} \\ a_{22} \\ a_{23} \\ a_{31} \\ a_{32} \\ a_{33} \\\end{bmatrix} \equiv \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} \pmod 2$$

Begin Reduced Row Echelon Reduction:

$$\begin{bmatrix}1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1\cr 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\cr 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0\cr 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0\cr 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 1\cr 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0\cr 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0\cr 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0\cr 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1\end{bmatrix}$$ $$\vdots$$ $$\begin{bmatrix}1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1\cr 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0\cr 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1\cr 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0\cr 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0\cr 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0\cr 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1\cr 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\cr 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1\end{bmatrix}$$ $$\vdots$$ $$\begin{bmatrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\cr 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\cr 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1\cr 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\cr 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\cr 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\cr 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1\end{bmatrix}$$

Which corresponds to $a_{11} = 1$, $a_{22} = 1$, $a_{33} = 1$, and the other $a$ values are zero. And if you check, flipping those 3 will solve the problem.


A more general example. Suppose $N=3$ and $D=2$. The resulting matrix:

$$\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & b_{11}\cr 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & b_{12}\cr 1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & b_{13}\cr 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & b_{21}\cr 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & b_{22}\cr 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & b_{23}\cr 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & b_{31}\cr 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & b_{32}\cr 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & b_{33}\end{bmatrix}$$

Which has reduced row echelon form: $$ \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & b_{23}+b_{12} \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & b_{31}+b_{22}+b_{21}+b_{11} \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & b_{22}+b_{21} \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & b_{13}+b_{12} \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & b_{31}+b_{23}+b_{22}+b_{13}+b_{12} \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & b_{22}+b_{11} \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & b_{22}+b_{12} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & b_{32}+b_{23}+b_{21}+b_{12} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & b_{33}+b_{31}+b_{23}+b_{21}+b_{13}+b_{11} \end{bmatrix} $$

Meaning that you only have a solution if $$b_{32}+b_{23}+b_{21}+b_{12} \equiv 0 \pmod 2$$ $$b_{33}+b_{31}+b_{23}+b_{21}+b_{13}+b_{11} \equiv 0 \pmod 2$$

For the second example in your question, this is given by : $$0+0+1+0 \equiv 0 \pmod 2$$ $$0+0+0+1+1+1 \equiv 0 \pmod 2$$

showing that your example is actually impossible.

$\endgroup$
4
  • $\begingroup$ Can you please explain it with some sort of example.I am not getting it fully $\endgroup$ Nov 23, 2013 at 20:13
  • $\begingroup$ Before I write an example, tell me do you know modular arithmetic? Like $1 + 1 \equiv 0 \pmod 2$? $\endgroup$
    – DanielV
    Nov 23, 2013 at 20:24
  • $\begingroup$ Ya..i know it..no problem $\endgroup$ Nov 23, 2013 at 20:24
  • $\begingroup$ Wrote 2 examples, hopefully they'll help. $\endgroup$
    – DanielV
    Nov 23, 2013 at 22:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .