E  Duplicates

Let’s say a row or a column is colorful if the values within it are all distinct. Otherwise, we say it’s non-colorful. Our objective in this problem is to minimize the number of modifications needed to make all rows and columns non-colorful.

Let \(m_r\) denote the number of colorful rows, and \(m_c\) denote the number of colorful columns. Since the number of colorful rows and colorful columns decreases by at most one with each modification, we require a minimum of \(\max(m_r, m_c)\) modifications to make all rows and columns in the matrix non-colorful. We can show that \(\max(m_r, m_c)\) is indeed adequate for achieving this objective as follows.

When both \(m_r \gt 0\) and \(m_c \gt 0\) hold, there exists an entry \((i, j)\) such that row \(i\) and column \(j\) are colorful. By changing the value at \((i, j)\) to an arbitrary integer other than \(A_{ij}\), we simultaneously decrease the number of colorful rows and columns by one, respectively.

When \(m_r = 0\) and \(m_c \gt 0\), there exists a colorful column, let’s say column \(j\). In this case, there must be at least one value \(v\) such that modifying an entry \((1, j)\) to \(v\) makes column \(j\) non-colorful while keeping row \(1\) non-colorful.

A similar logic applies when \(m_r \gt 0\) and \(m_c = 0\).

Using this approach, we can accomplish the objective with \(\max(m_r, m_c)\) modifications. The computational time is \(O(n^3)\) with a sloppy implementation. This can be further improved to \(O(n^2)\) time.