Duplicates (Problem E, The 2024 ICPC Asia Pacific Championship, 2024)
Time limit: 2 sec
Author: Mitsuru Kusumoto

# Problem Statement

We say that a number sequence *contains duplicates* if there is an element that appears more than once in the sequence. Formally, a sequence $(a_1, \dots, a_n)$ contains duplicates if there exist two indices $i$ and $j$ such that $i \ne j$ and $a_i = a_j$.

You are given an $n \times n$ matrix $X$. Each entry in $X$ is an integer between $1$ and $n$, inclusive. You can modify zero or more entries in $X$ to arbitrary integers between $1$ and $n$, inclusive. Different entries can be modified to different integers.

Your task is to make modifications to entries of $X$ such that all of the following hold:

- For each row $i$, the sequence $(X_{i1}, X_{i2}, ..., X_{in})$ contains duplicates.
- For each column $j$, the sequence $(X_{1j}, X_{2j}, ..., X_{nj})$ contains duplicates.

Compute the minimum number of entries that need to be modified to achieve this. Also, find one possible set of modifications to do it. For each modification, you have to specify which entry will be modified and to what value. Note that the minimum number of entries to be modified can be zero when the given matrix $X$ already satisfies the conditions above.

# Input

The first line of input contains one integer $t$ $(1 \le t \le 1000)$ representing the number of test cases. After that, $t$ test cases follow. Each of them is presented as follows.

The first line of a test case contains one integer $n$ $(3 \le n \le 100)$. Each of the next $n$ lines contains $n$ integers. The $j$-th integer in the $i$-th line denotes $X_{ij}$ $(1 \le X_{ij} \le n)$.

The sum of $n^2$ across all test cases in one input file does not exceed $10\,000$.

# Output

For each test case, output a set of modifications in the following format.

On the first line, output an integer $m$ representing the minimum number of entries that need to be modified. On each of the next $m$ lines, output three integers $i$, $j$, and $v$. This represents a single modification where the entry $X_{ij}$ will be modified to $v$. All of the three integers must be between $1$ and $n$, inclusive.

If there are multiple solutions, you can output any of them.

# Sample Input #1
```
5
4
3 2 1 1
2 1 3 4
1 3 3 1
4 4 4 2
3
1 3 1
2 1 3
3 2 2
5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
3
1 1 2
2 2 1
2 3 2
3
1 1 3
3 2 1
3 1 3
```
# Sample Output #1
```
2
2 1 1
4 2 3
3
2 1 3
2 2 3
3 3 3
0
1
1 2 2
1
2 1 1
```

*Explanation for the sample input/output #1*

In the first test case, the matrix after the modification is as follows.

$$
\begin{bmatrix}
3 & 2 & 1 & 1 \\
\mathbf{1} & 1 & 3 & 4 \\
1 & 3 & 3 & 1 \\
4 & \mathbf{3} & 4 & 2 \\
\end{bmatrix}
$$

Sample inputs:
5
4
3 2 1 1
2 1 3 4
1 3 3 1
4 4 4 2
3
1 3 1
2 1 3
3 2 2
5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
3
1 1 2
2 2 1
2 3 2
3
1 1 3
3 2 1
3 1 3

Sample outputs:
2
2 1 1
4 2 3
3
2 1 3
2 2 3
3 3 3
0
1
1 2 2
1
2 1 1

# Solution Analysis
Analysis author: Mitsuru Kusumoto

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 > 0$ and $m_c > 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 > 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 > 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.

Special judge (C++ scorer):
#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>
#include <vector>
#include <set>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  vfprintf(stderr, err, pvar);
  fprintf(stderr, "\n");
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

int X[120][120];

struct Mod {
  int i, j, v;
};

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  int t;
  if (!(judgein >> t)) judge_error("input broken! t not found\n");
  if (t < 1 || t > 1000) judge_error("input broken! t=%d\n", t);
  int nsum2 = 0;
  while (t--) {
    int n;
    if (!(judgein >> n)) judge_error("input broken! n not found\n");
    if (n < 3 || n > 100) judge_error("input broken! n=%d\n", n);
    nsum2 += n * n;
    if (nsum2 > 10000) judge_error("input broken! nsum2=%d\n", nsum2);

    for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) {
      if (!(judgein >> X[i][j])) judge_error("input broken! Xij not found\n");
      if (X[i][j] < 1 || X[i][j] > n) judge_error("input broken! X[%d][%d]=%d\n", i, j, X[i][j]);
    }

    int m_ans;
    if (!(judgeans >> m_ans)) judge_error("model solution broken! m_ans cannot be read");
    for (int i = 0; i < m_ans; ++i) {
      int nop1, nop2, nop3;
      if (!(judgeans >> nop1 >> nop2 >> nop3)) judge_error("model solution broken! mod values cannot be read");
    }

    int m_con;
    if (!(conans >> m_con)) wrong_answer("m cannot be read");
    if (m_con > m_ans) {
      wrong_answer("contestant's output has more modifications: expected=%d, received=%d", m_ans, m_con);
    }

    std::vector<Mod> mod_con;
    for (int it = 0; it < m_con; ++it) {
      int i = 0, j = 0, v = 0;
      if (!(conans >> i >> j >> v)) {
        wrong_answer("unable to read the %d-th modification", it + 1);
      }
      if (i < 1 || i > n) wrong_answer("i is violating range");
      if (j < 1 || j > n) wrong_answer("j is violating range");
      if (v < 1 || v > n) wrong_answer("v is violating range");

      mod_con.push_back({i, j, v});
    }

    for (auto mod : mod_con) {
      X[mod.i - 1][mod.j - 1] = mod.v;
    }

    for (int i = 0; i < n; ++i) {
      std::set<int> st;
      for (int j = 0; j < n; ++j) st.insert(X[i][j]);
      if ((int)st.size() == n) {
        wrong_answer("row %d does not contain duplicate", i + 1);
      }
    }

    for (int j = 0; j < n; ++j) {
      std::set<int> st;
      for (int i = 0; i < n; ++i) st.insert(X[i][j]);
      if ((int)st.size() == n) {
        wrong_answer("column %d does not contain duplicate", j + 1);
      }
    }

    if (m_con < m_ans) {
      judge_error("contestant's output is better than us!? that cannot be happening! expected=%d, received=%d", m_ans, m_con);
    }
  }

  std::string j;
  if (judgein >> j) {
    judge_error("Unread token:\n%s", j.c_str());
  }

  std::string team;
  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}