Problem: second_second_meaning (2022 quals)

**Note: The only difference between this problem and [problem C1](https://www.facebook.com/codingcompetitions/hacker-cup/2022/qualification-round/problems/C1) is that here, the length of each output codeword may be at most 10.**

Morse code is a classic way to send messages, where each letter in an alphabet is substituted with a *codeword*: a unique sequence of dots and dashes. However, ignoring spaces, it's possible for a coded message to have multiple meanings. For example, "`.....--.-.-.-..-.-.-...-.--.`" can be interpreted as either "`HACKER CUP`" or "`SEE META RENT A VAN`":

{{PHOTO_ID:569216148234749|WIDTH:700}}

Beyond Morse code, a general set of codewords is an *unambiguous encoding* if any possible sequence of dots and dashes corresponds to either zero or exactly one sequence of codewords.

Given one codeword \(C_1\) from a set of \(N\) distinct codewords, your task is to generate another \(N - 1\) codewords \(C_2, ..., C_N\) to yield an unambiguous encoding. It can be shown that an answer always exists. If there are multiple answers, you may print any one of them.


# Constraints

\(1 \le T \le 95\)
\(2 \le N \le 100\)
The length of \(C_1\) is between \(1\) and \(100\), inclusive.
The length of each \(C_2, ..., C_N\) must be between \(1\) and \(\mathbf{10}\), inclusive.


# Input Format

Input begins with an integer \(T\), the number of test cases. For each case, there is first a line containing a single integer \(N\). Then, there is a line containing the codeword \(C_1\).


# Output Format

For the \(i\)th case, output a line containing only "`Case #i:`", followed by \(N - 1\) lines, the codewords \(C_2, ..., C_N\), one per line.


# Sample Explanation

In the first case, it can be shown that the codewords {"`.-.`", "`...`", "`---`"} are an unambiguous encoding. Any sequence of dots and dashes can be interpreted if and only if it has a length that's a multiple of 3, and can be broken up into instances of the three length-3 codewords.

In the second case, it can be shown that the codewords {"`-`", "`...`", "`.-`", "`..-`"} are an unambiguous encoding. For instance, "`..`" has no possible interpretation, and "`.-...--`" can only be interpreted as "`.- ... - -`".

In the third case, it can be shown that the codewords {"`..`", "`-`", "`.-`"} are an unambiguous encoding. For any sequence of dots and dashes:
- every odd group of dots followed by a dash can only be interpreted as repeated "`..`"s followed by a final "`.-`"
- every even group of dots followed by a dash can only be interpreted as repeated "`..`"s followed by a final "`-`"
- every group of dots not followed by a dash (i.e. at the end of the sequence), is interpretable if and only if there is an even number of dots
- this leaves only groups of dashes, interpreted only as repeated "`-`"s


Sample input:
3
3
.-.
4
-
3
..


Sample output:
Case #1:
...
---
Case #2:
...
.-
..-
Case #3:
-
.-


Solution: Another way to view a binary prefix code is as the [set of leaves on a unique binary tree](https://www.cs.princeton.edu/courses/archive/spr01/cs126/assignments/prefix.html). Each leaf corresponds to a codeword, given by the path of dots and dashes from the root. We can start with a binary tree consisting only of such a path to \(C_1\). To find an answer, we can continue adding nodes (without touching \(C_1\)'s leaf) until we have enough.

Implementation-wise, we can imagine a perfect binary tree that's pruned at the leaf corresponding to \(C_1\). Breadth-first search can be used to perform a level-order traversal of this tree without explicitly constructing it. Each node can be represented as a candidate codeword string, with children obtained by appending either a dot or dash.

As we BFS, we maintain all the current leaves (nodes enqueued but have yet to be processed), stopping once we hit \(N - 1\) leaves. We must be careful not to output anything on the path to \(C_1\). This can be handled by avoiding outputting prefixes of \(C_1\) or \(C_1\)-prefixed codewords, or by simply by prepending all output codewords with the opposite of \(C_1\)'s first character (essentially pruning the perfect binary tree at the start of \(C_1\) instead of the end).

Since a perfect binary tree of height \(h\) has \(2^h\) leaves, a maximum codeword length (tree height) of \(10\) still yields \(2^{10} = 1024\) leaves to work with. Since pruning once cannot get rid of more than \(1/2\) of a tree's leaves, we'll get at least \(1024/2 = 512 > 100\) leaves before hitting length \(10\).

Another approach, yielding a slightly longer total output length, is to generate bitstrings of a fixed length (\(\lceil \log_2 N \rceil + 1\) is sufficient), excluding any which prefixes or is prefixed by \(C_1\).

[See David Harmeyer's solution video here.](https://youtu.be/6Xgt70dfvNk)


Code: #include <iostream>
#include <queue>
#include <set>
using namespace std;

set<string> solve(int N, string C1) {
  set<string> leaves;
  queue<string> q;
  for (q.push(""); !q.empty(); q.pop()) {
    string curr = q.front();
    leaves.erase(curr);
    for (string s : {curr + ".", curr + "-"}) {
      q.push(s);
      if (C1.rfind(s, 0) != 0 && s.rfind(C1, 0) != 0) {
        leaves.insert(s);
        if (leaves.size() == N - 1) {
          return leaves;
        }
      }
    }
  }
  return {};
}

int main() {
  int T, N;
  string C1;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cin >> N >> C1;
    cout << "Case #" << t << ":" << endl;
    auto S = solve(N, C1);
    for (auto s : S) {
      cout << s << endl;
    }
  }
  return 0;
}