2
$\begingroup$

We have an $ n \times n $ table, and in each cell of the table, there is a number from $1$ to $ 2n $. We want to change the numbers in some of the cells and replace them with other numbers from $1$ to $ 2n $ such that in the end, all the numbers in each row and each column are distinct. What is the minimum number of cells we need to change?

I have tried using dynamic programming and assumed the subproblems are $i\times i$ minors of the grid. However, I couldn't make significant progress with this approach. I also attempted to reduce the problem to graph problems, such as matchings, but again, I didn't succeed in finding a solution.

Any hints or help would be immensely valuable to me.

$\endgroup$
2
  • $\begingroup$ Do you care more about theoretical complexity or practical running time on real-world instances? If the latter, what are typical values for $n$ and for the number of cells that must be changed? $\endgroup$
    – D.W.
    Commented Jun 19 at 9:09
  • $\begingroup$ @D.W. Constraints on $n$ are $1\leq n \leq 300$. $\endgroup$ Commented Jun 19 at 14:04

1 Answer 1

3
$\begingroup$

Hint 1

If we have a cell $a_{i,j}$ which is duplicate to some other cell $a_{i, j_1}$ in its row, and some other cell $a_{i_1, j}$ in its column; we can always remove this duplicacy by only changing $a_{i,j}$. This is because the maximum number of unique numbers in the row $\cup$ column are $2(n-1)$ and we can select from $2n$ numbers, leaving us with a choice of atleast $2$ numbers.

Hint 2

Following the above hint, the crux of the problem remains on how to optimize number of changes on $(i, j)$'s where $a_{i,j}$ is duplicate both in the row and column. If the frequency of number $k$ in row $i$ is $f^r_{i, k}$ and in column $j$ it is $f^c_{j, k}$, then the answer is

$$\sum_{k=1}^{2n} \left( \sum_{i=1}^{n} \max(f^r_{i, k}-1, 0) + \sum_{j=1}^{n} \max(f^c_{j, k}-1, 0) - g(k) \right) $$

where $g(k)$ is some number produced by optimising on the common cells. Note we can't just add all the number of common cells as $g(k)$ (take the counter example of $\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$)

Hint 3

To compute $g(k)$, make a weighted directed graph $G=(V, E)$ with $$\begin{split} V&=\{S\} \\ &\cup \{{r_1}, {r_2}, \dots {r_n} \} \\ &\cup \{c_1, c_2, \dots c_n\} \\ &\cup \{T\} \end{split}$$ and $$\begin{split} E&=\{(S, r_i, \max(f^r_{i, k}-1, 0)) : \forall 1\le i \le n\} \\ &\cup \{(r_i, c_j, 1): \forall 1\le i, j \le n \text{ if } a_{i,j} = k\} \\ &\cup \{(c_j, T, \max(f^c_{j, k}-1, 0)) : \forall 1\le j \le n\} \end{split}$$

Then the max flow of this graph is $g(k)$

Example

Consider $n=5$ and the table to be $$A = \begin{bmatrix} 1 & 2 & 1 & 2 & 1 \\ 2 & 1 & 1 & 1 & 1 \\ 1 & 2 & 1 & 2 & 1 \\ 3 & 1 & 2 & 9 & 3 \\ 2 & 2 & 2 & 2 & 2 \\ \end{bmatrix}$$

  • For $k\in \{4, 5 ,6 ,7 ,8, 10\}$, we don't see a single cell $a_{i,j} =k$. So $$\begin{split} h(k) &= \sum_{i=1}^{n} \max(f^r_{i, k}-1, 0) + \sum_{j=1}^{n} \max(f^c_{j, k}-1, 0) - g(k) \\ &=0 \end{split}$$

  • For $k=9$, we see only a single cell $a_{4,4} = 9$. So $h(9) = 0$ too.

  • $k=3$ is also trivial with $h(3) = 1$

  • $k=2$'s graph $G$ has a max flow of $6$ (as seen in the image below) k=2 So $$\begin{split} h(2) &= \sum_{i=1}^{n} \max(f^r_{i, k}-1, 0) + \sum_{j=1}^{n} \max(f^c_{j, k}-1, 0) - g(k) \\ &= 6 + 6 - 6 \\ &=6 \end{split}$$

  • $k=1$'s graph $G$ has a max flow of also $6$ (as seen in the image below) k=1 So $$\begin{split} h(1) &= \sum_{i=1}^{n} \max(f^r_{i, k}-1, 0) + \sum_{j=1}^{n} \max(f^c_{j, k}-1, 0) - g(k) \\ &= 7 + 6 - 6 \\ &=7 \end{split}$$

So total number of changes required is $7 + 6 + 1 = 14$, as shown in the below table. $$ \begin{bmatrix} \color{red} 4 & 2 & \color{red} 3 & \color{red} 5 & 1 \\ 2 & \color{red} 3 & \color{red} 4 & 1 & \color{red} 5 \\ \color{red} 3 & \color{red} 4 & 1 & 2 & \color{red} 6 \\ \color{red} 5 & 1 & 2 & 9 & 3 \\ \color{red} 1 & \color{red} 5 & \color{red} 6 & \color{red} 3 & 2 \\ \end{bmatrix} $$

Algorithm runtime analysis

For each number $k$, let $f_k$ denote the total number of cells $a_{i, j} =k$ in the table.

Time complexity of

  • Finding $f^r_{i, k}$ and $f^c_{j, k}$ for all $i, j, k$ is $\mathcal{O}(n^2)$
  • Calculating max flow of graph $G$ for $k$ using ford fulkerson is $\mathcal{O}(EF) = \mathcal{O}((n+f_k) f_k)$ in worst case, but closer to $\mathcal{O}(n + f_k)$ in practice.

Then the time complexity is $$\begin{split} T &= \mathcal{O}(n^2) + \sum_{k=1}^{k=2n}( 2 \cdot \mathcal{O}(n) + \mathcal{O}(n + f_k)) \\ &= \mathcal{O}(n^2) + \mathcal{O} \left( \sum_{k=1}^{k=2n} f_k \right) \\ &= \mathcal{O}(n^2) \end{split}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.