Personality Test (Problem G, The 2024 ICPC Asia Pacific Championship, 2024)
Time limit: 3 sec
Author: Meng-Tsung Tsai

# Problem Statement

There are $n$ students taking a personality test consisting of $m$ questions. The students are numbered from $1$ to $n$ and the questions are numbered from $1$ to $m$. For each question, each student can either answer it with a single uppercase Latin character (A–Z) or not answer it. Let $S_i$ be a string of $m$ characters representing the answers of student $i$, where the $j$-th character of $S_i$ is an uppercase Latin character if they answered question $j$, or a period (.) if they did not.

Two students are considered *similar* if there is a set of at least $k$ questions where both students answered all questions in the set, and for each question in the set, they answered it with the same answer.

For example, let $n = 3$, $m = 3$, $k = 2$, $S_1 = \texttt{BBC}$, $S_2 = \texttt{..C}$, and $S_3 = \texttt{.BC}$. In this example, students 1 and 3 are similar since they answered questions 2 and 3 with the same answer, while students 2 and 3 are not similar since they answered only question 3 with the same answer.

You want to find a pair of integers $(a, b)$ such that $a < b$ and students $a$ and $b$ are similar, or determine if there is no such pair. If there is more than one pair, find the one with the *smallest* $b$. If there is still more than one pair, find the one with the *largest* $a$.

# Input

The first line of input contains three integers $n$, $m$, and $k$ ($2 \leq n \leq 5000$; $1 \leq m \leq 3000$; $1 \leq k \leq 5$). Each of the next $n$ lines contains a string of $m$ characters. The $i$-th line contains the string $S_i$.

# Output

Output one line containing the integers $a$ and $b$ representing the pair of similar students as mentioned in the problem statement, or just the integer $-1$ if there is no such pair.

# Sample Input #1
```
3 3 2
BBC
..C
.BC
```
# Sample Output #1
```
1 3
```
*Explanation for the sample input/output #1*

This is the example in the problem statement.

# Sample Input #2
```
3 3 1
BBC
..C
.BC
```
# Sample Output #2
```
1 2
```
*Explanation for the sample input/output #2*

Students 1 and 2 are similar.

# Sample Input #3
```
3 3 3
BBC
..C
.BC
```
# Sample Output #3
```
-1
```
*Explanation for the sample input/output #3*

There is no pair of similar students.

# Sample Input #4
```
4 12 2
GOOD.LUCK.IN
WINNING.ICPC
ASIA.PACIFIC
CHAMPIONSHIP
```
# Sample Output #4
```
2 3
```

Sample inputs:
3 3 2
BBC
..C
.BC

3 3 1
BBC
..C
.BC

3 3 3
BBC
..C
.BC

4 12 2
GOOD.LUCK.IN
WINNING.ICPC
ASIA.PACIFIC
CHAMPIONSHIP

Sample outputs:
1 3

1 2

-1

2 3

# Solution Analysis
Analysis author: Mitsuru Kusumoto

The problem can be reformulated as follows:

> Suppose there exists a graph with $n$ vertices, numbered from $1$ to $n$. Initially, each pair of vertices is connected by an undirected edge with weight zero. We increment an integer $b$ from $1$ to $n$. In each step, for every $1 \leq i < b$ and $1 \leq j \leq m$ such that $S_{ij} = S_{bj} \ne \texttt{'.'}$, we increment the weight between vertices $i$ and $b$ by one. If we encounter an edge with a weight of $k$ or more, we must report that edge and terminate the program.

A straightforward implementation of this procedure requires $\Theta(n^2 m)$ time. An important observation is that the sum of weights across all edges is bounded by $(k - 1)\binom{n}{2}$, unless the step is at the termination of the program. This implies that the increase in edge weights occurs at most $O(kn^2)$ times. With some precomputation, for each $j$ such that $S_{bj} \ne \texttt{'.'}$ in the steps of the above procedure, we can enumerate all indices $i$ satisfying $S_{ij} = S_{bj}$ in $O(\#\{i < b \mid S_{ij} = S_{bj}\})$ time, instead of $\Theta(b)$ time.

With this enumeration method, the runtime becomes $O(nm + m\Sigma + kn^2)$, where $\Sigma$ is the number of Latin characters (in this problem, $\Sigma = 26$).

Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to tcframe format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

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, ...) {
  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;
}

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]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

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

  ac();
}