XEN 3166 (Problem I, 2017 ICPC Asia Jakarta Regional Contest, 2017)
Time limit: 1 sec
Memory limit: 256MB
Author: Ilham Winata Kurnia

# Problem Statement

There are $N$ countries in this world, numbered from $1$ to $N$. Each country has a country name and a country code. Both of them can be represented as a string. No two countries share the same country name. For simplicity, in this problem we assume that a string consists only uppercase English alphabets (A–Z).

One of the widely recognised country code standard is published by ISO (ISO 3166). However, Xenia has noticed something strange about ISO 3166. The resulting code is no longer alphabetical! For example, "INDIA" has “IN” as its country code while "INDONESIA" is “ID”. "INDONESIA" comes after "INDIA" in alphabetical order, but “IN" comes after “ID”.

Unhappy about this indecent property of the ISO 3166 country codes, Xenia seeks for a more consistent coding. She develops her own standard, called XEN 3166. The rules of XEN 3166 are:

- For each country, its country code must be a subsequence of its country name.
- For each country, its first letter of the country code must be the same as its first letter of the country name.
- For each country, the length of its country code must be exactly $K$.
- If a country with a country name $S$ has a country code $S'$ and a country with a country name $T$ has a country code $T'$, then $S$ is lexicographically smaller than $T$ if and only if $S'$ is lexicographically smaller than $T'$.

A string $T = T_1T_2\cdots T_{|T|}$ is a subsequence of a string $S = S_1S_2\cdots S_{|S|}$ if there exists a sequence of integers $u_1, u_2, \cdots, u_{|T|}$ where $1 \le u_1 < u_2 < \cdots < u_{|T|} \le |S|$ and $S_{u_i} = T_i$ for all $1 \le i \le |T|$. For example, "ID", "IN", and "IND" are subsequences of "INDIA", but "IDN", "INN", "Z" are not subsequences of "INDIA".

String $S = S_1S_2\cdots S_{|S|}$ is lexicographically smaller than string $T = T_1T_2\cdots T_{|T|}$ if at least one of the following is true:

- $|S| < |T|$ and $S_i = T_i$ for all $1 \le i \le |S|$, or
- There exists an index $i$ where $S_i < T_i$ and $S_j = T_j$ for all $1 \le j < i$.

For example, suppose there are only two countries and $K = 2$. The name of the first country is "INDIA" and the name of the second country is "INDONESIA". Therefore, several possible country codes assignment are:

- "ID" for "INDIA" and "IN" for "INDONESIA
- "IA" for "INDIA" and "ID" for "INDONESIA"
- "II" for "INDIA" and "IO" for "INDONESIA"

Given $N$, $K$, and the list of country names. Help Xenia to assign the country codes for each country that follows the XEN 3166 rule, or state that it is impossible to do so.

# Input

The first line contains two integers: $N$ $K$ $(1 \le N \le 1000;\ 1 \le K \le 200)$ in a line denoting the number of countries and the length of country codes.
The next $N$ following lines, each contains a string which length between $1$ and $200,!000$ consisting of uppercase English alphabets (A–Z).
The string on the $i$-th line denotes the country name of the $i$-th country.
The sum of the length of all country names are guaranteed to be not more than $200,!000$.
It is also guaranteed that no two countries share the same country name.

# Output

- If it is possible for Xenia to assign the country codes for each country that follows the XEN 3166 rule, output "YES" (quotes only for clarity) on the first line.
The next $N$ following lines, each contains a string. The string on the $i$-th line denotes the country code of the $i$-th country.
If there are more than one possible country codes assignment, you may output any of them.

- If it is not possible for Xenia to assign the country codes for each country that follows the XEN 3166 rule, just output "NO" (quotes only for clarity) in a single line.

# Sample Input
```
2 2
INDIA
INDONESIA
```
# Output for Sample Input
```
YES
ID
IN
```
# Sample Input
```
3 2
IBAA
IAAA
IAAC
```
# Output for Sample Input
```
NO
```
# Explanation for the 1st sample case

The scenario in the first sample is the same as the scenario given in the problem description.

Sample inputs:
2 2
INDIA
INDONESIA

3 2
IBAA
IAAA
IAAC

Sample outputs:
YES
IA
ID

NO

# Solution Analysis
Analysis author: Jonathan Irvin Gunawan

For easier discussion, let us assume the countries are sorted in the ascending order of country name.

For each country, we want to greedily assign the lexicographically smallest possible country code, but still lexicographically larger than the previous country's country code, so that the next countries can have more valid country code possibilities. Therefore, we can loop the countries while keeping track of the last country's country code, and for the current country, we generate the lexicographically smallest possible country code that is still lexicographically larger than the last country's country code.

How to achieve that? Let $S$ be the current country name, $T'$ be the last country code, and $T$ is the current country code that we want to generate. Since $T > T'$, then there exists an integer $k$ where $T[k] > T'[k]$ and $T[i] = T'[i]$ for all $1 \le i \le k$. Since we want to make $T$ as lexicographically small as possible, we want to maximise the value of $k$. In other words, we want the common prefix of $T$ and $T'$ to be as long as possible.

We can check whether it is possible for $T$ and $T'$ to have a common prefix of length $l$ by checking whether we can construct a subsequence of $S$ which starts with $T[1..l] + c$ for some $c > T[l + 1]$. To do this, we can define a function $\text{nxt}(c, i)$ be the index of the next occurrence of character $c$ in $S$ after the $i$-th index, and then checking whether $\text{nxt}(c, \text{nxt}(T'[l], \text{nxt}(T'[l - 1], \ldots, \text{nxt}(T'[1], 0) \ldots)))$ is less than some upper limit.

Once we found the maximum $l$ possible, and the corresponding smallest $c$ that makes $l$ possible, we can greedily construct the lexicographically smallest subsequence that starts with $T[1..l] + c$ to become $T'$.

Special judge (C++ scorer):
#include <bits/stdc++.h>
using namespace std;

int wa() {
  cout << "WA" << endl;
  return 0;
}

int ac() {
  // cout << "AC" << endl;
  return 0;
}

int N, K;

// checks whether t is a subsequence of s
bool is_subsequence(string s, string t)
{
  int L = 0;
  for (int i = 0; i < t.size(); ++i) {
    while (L < s.size() && s[L] != t[i]) {
      ++L;
    }
    if (L == s.size()) return false;
    ++L;
  }
  return true;
}

int checks(istream& tc_in, istream& tc_out, istream& con_out) {
  tc_in >> N >> K;
  
  string s_tc, s_con;
  getline(tc_out, s_tc);
  getline(con_out, s_con);

  if (s_tc != s_con) return wa();
  if (s_tc == "NO") 
  {
    if (getline(con_out, s_con)) {
      return wa();
    }
    return ac();
  }

  vector<string> input(N);
  vector<string> output(N);
  vector<int> order(N);

  getline(tc_in, input[0]);
  for (int i = 0; i < N; ++i) {
    order[i] = i;
    getline(tc_in, input[i]);
    getline(con_out, output[i]);

    if (output[i].size() != K) return wa();
    if (output[i][0] != input[i][0]) return wa();
    if (!is_subsequence(input[i], output[i])) return wa();
  }

  if (getline(con_out, s_con)) {
    return wa();
  }

  auto f = [&](const int &a, const int &b) -> bool
  {
    return input[a] < input[b];
  };

  sort(order.begin(), order.end(), f);
  for (int i = 1; i < N; ++i) {
    if (output[order[i]] <= output[order[i - 1]]) return wa();
  }
  return ac();
}

int main(int argc, char* argv[]) {
  ifstream tc_in(argv[1]);
  ifstream tc_out(argv[3]);

  return checks(tc_in, tc_out, cin);
}