Smart Thief (Problem C, 2018 ICPC Asia Jakarta Regional Contest, 2018)
Time limit: 1 sec
Memory limit: 256MB
Author: Suhendry Effendy

# Problem Statement

Ayu managed to steal Budi’s treasure box and ready to uncover any secret Budi hides. Unfortunately, the treasure box has some security system to prevent any unauthorized person (e.g., Ayu) from opening it.

To unlock the treasure box, Ayu has to input a correct PIN (Personal Identification Number) of length $N$, which of course, she doesn’t have. Ayu has no choice other than trying all possible PIN combinations. However, Ayu notices that this security system has an interesting (old) mechanic.

When you enter an $N$ digits PIN, it is evaluated automatically and promptly, i.e. you don’t need to push some “enter” button to confirm the PIN. Whenever your entered PIN is wrong, it removes the oldest (first) digit and shifts all the remaining to the left, thus, you only need to enter one more (last) digit to make it $N$ length again.

For example, let $N = 4$. If we input `204320435`, then we actually test 6 PINs (with 5 different PINs):

- [2043]20435, tested PIN = 2043  
- 2[0432]0435, tested PIN = 0432  
- 20[4320]435, tested PIN = 4320  
- 204[3204]35, tested PIN = 3204  
- 2043[2043]5, tested PIN = 2043  
- 20432[0435], tested PIN = 0435

Notice that 2043 is tested twice in this example.

As a CS student, Ayu knows that finding the correct PIN by trying all possible combinations can be very time-consuming, but alas, there’s no other way. Ayu decides that she wants to test at least $K$ different PINs on the first day. Your task is to help Ayu by simply giving her the string $S$ which contains at least $K$ different PINs. Ayu doesn’t care which PIN she’s going to test (so long at least there are $K$ different PINs) or whether any PIN is tested more than once in $S$, but string $S$ needs to be as short as possible. If there is more than one possible string for $S$, you can output any of them.

Note that, as this system is quite old, there are only $M$ available digits ranging from 0 to 9.

# Input

Input begins with a line containing three integers: $N$ $M$ $K$ ($1 \leq N \leq 100000$, $1 \leq M \leq 10$, $1 \leq K \leq \min(M^N, 100000)$), representing the PIN length, the number of available digits, and the minimum number of PINs to be tested, respectively. The next line contains $M$ integers: $A_i$ ($0 \leq A_i \leq 9$), representing the available digits. You may assume all $A_i$ are distinct. You may also assume that the values of $N$, $M$, and $K$ are chosen such that the answer contains no longer than 100000 digits.

# Output

Output in a line the **shortest** string which contains at least $K$ different PINs as its substring. If there is more than one such string, you can output any of them.

# Sample Input #1
```
3 2 5
4 7
```
# Sample Output #1
```
7477447
```
Explanation for the sample input/output #1

There are 5 different PINs of length 3 tested with the string 7477447, i.e. 447, 477, 744, 747, and 774.

# Sample Input #2
```
2 5 9
1 2 3 4 5
```
# Sample Output #2
```
1234554321
```
Explanation for the sample input/output #2

There are 9 different PINs of length 2 tested with the string 1234554321, i.e. 12, 21, 23, 32, 34, 43, 45, 54, and 55.

# Sample Input #3
```
6 3 2
9 3 5
```
# Sample Output #3
```
9353593
```
Explanation for the sample input/output #3

There are 2 different PINs of length 6 tested with the string 9353593, i.e. 353593, and 935359.



Sample inputs:
3 2 5
4 7

2 5 9
1 2 3 4 5

6 3 2
9 3 5

Sample outputs:
7477447

1234554321

9353593

# Solution Analysis

Observe that the length of the shortest string which contains $K$ distinct substrings of length $N$ (in other words, the length of the output) is exactly $N + K - 1$. More specifically, the output for this problem corresponds to a partial **de Bruijn sequence**.

Let $G = (V, E)$ be a directed graph where the set of nodes $V$ be all possible strings of length $N - 1$, and a node $u$ has a directed edge $(u, v)$ to node $v$ if and only if the string represented by node $v$ can be obtained by appending one character to $u$ and deleting the front-most character of $u$, e.g., “abcd” $\to$ “bcde” and the corresponding directed edge’s label is “e”. Then, the output for this problem corresponds to an **Eulerian path** of length $K$ in $G$.

However, the constraint for $N$ in the problem can be as large as $100000$, thus, we cannot simply build $G$ as described. Note that there are $M^{(N-1)}$ nodes in $G$.

Let’s consider two separated cases.

1. **Small** $N$ (e.g., $\leq 40$). In this case, we can solve the problem by using graph $G$, however, we should not construct $G$ as it. Instead, we should construct $G$ *on-the-fly* (as needed) and stop once we obtained the desired result, thus, we only have a “partial” $G$. With **Hierholzer’s algorithm** to find an Eulerian path, we can solve this in $O(NK)$ time, or $O(NK \log N)$ if you’re using an easier implementation.

2. **Large** $N$. In this case, simply output a random string (with the given alphabets) of length $N + K - 1$. Note that there are $M^N$ distinct substrings of length $N$. If $N$ is large and $M \geq 2$, then $M^N \gg K$, thus, the probability that the same substring appear more than once in the output is extremely low. Additionally, you can write a function to check whether the output string is valid, e.g., with **rolling hash** function (like the one implemented in the checker program for this problem), but it’s not necessary.

A note on Hierholzer’s algorithm. This algorithm finds an Eulerian tour in $O(E)$ and works by maintaining two lists, i.e. exploring list and result list. At any time, each list contains a valid Eulerian path. So, for the purpose of this problem, we can simply terminate when any of the lists contains $\geq K$ nodes, and work the output from that list.

Also, note that there are some implementation details not mentioned in this analysis for you to figure out.

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

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

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

const vector<long long> MOD = { 99999999999999997LL,
                               100000000000000003LL,
                               100000000000000013LL};
const vector<int> BASE = {11, 13, 17};

bool check_string(int N, const string &S) {
  const int H = MOD.size();
  assert(BASE.size() == H);

  vector<long long> power(H, 1);
  for (int i = 0; i < H; ++i) {
    for (int j = 1; j < N; ++j) {
      power[i] = (power[i] * BASE[i]) % MOD[i];
    }
    // power[i] = BASE[i] ^ (N - 1)
  }
  set<vector<long long>> visited;
  vector<long long> current(H, 0);
  for (int i = 0; i < H; ++i) {
    for (int j = 0; j < N; ++j) {
      current[i] = (current[i] * BASE[i] + S[j] - '0') % MOD[i];
    }
  }
  visited.insert(current);
  for (int j = N; j < (int)S.size(); ++j) {
    for (int i = 0; i < H; ++i) {
      current[i] = (current[i] - (S[j - N] - '0') * power[i]) % MOD[i];
      if (current[i] < 0) {
        current[i] += MOD[i];
      }
      current[i] = (current[i] * BASE[i] + S[j] - '0') % MOD[i];
    }
    if (visited.count(current)) {
      return false;
    }
    visited.insert(current);
  }
  return true;
}

int checks(istream& tc_in, istream& tc_out, istream& con_out) {
  int N, M, K;
  vector<bool> exists(10, false);

  tc_in >> N >> M >> K;
  for (int i = 0; i < M; ++i) {
    int A;
    tc_in >> A;
    exists[A] = true;
  }

  string S;
  if (!(con_out >> S)) {
    return wa(1);
  }

  if (S.size() != N + K - 1) {
    return wa(2);
  }

  for (int i = 0; i < (int)S.size(); ++i) {
    if (S[i] < '0' || S[i] > '9') {
      return wa(3);
    }
    if (!exists[S[i] - '0']) {
      return wa(4);
    }
  }

  if (!check_string(N, S)) {
    return wa(5);
  }

  if (con_out >> S) {
    return wa(6);
  }
  return ac();
}

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

  return checks(strcmp(argv[1], "-") == 0 ? cin : tc_in,
                strcmp(argv[2], "-") == 0 ? cin : tc_out,
                strcmp(argv[3], "-") == 0 ? cin : con_out);
}