UVa 10506

From Algorithmist
Jump to: navigation, search

10506 - The Ouroboros Problem[edit]

Summary[edit]

Input is a base (b, at most 10) and a length (s). The task is to find a shortest "ouroboros" string of digits in base b such that each possible s-digit substring appears somewhere in the sequence. The string is considered to be circular, i.e., the first character follows the last one.

For example, let b=3 and s=2. All 2-digit strings are 00, 01, 02, 10, 11, 12, 20, 21, 22. The string 021211 contains the following ones: 02, 21 (twice), 12, 11, 10 (note the wrap-around). One optimal ouroboros string in this case: 001022112.

Explanation[edit]

One of the easier to see solutions is that one can write down each s-digit string as a vertex in a graph, then draw b directed edges out of each vertex into the strings you get by adding a new character to the end and removing one from the beginning. Label each edge with the letter you add when traversing it.

It can be shown (see Optimizations) that this graph always contains a Hamilton cycle. This cycle corresponds to a ouroboros string with no repeats, which is clearly optimal. To construct the string, start in any vertex, then traverse the edges along the Hamilton cycle and write down the edge labels. Note that at any time (except for the beginning) the vertex label corresponds to the last s digits you wrote down.

There are lots of possible Hamilton cycles, a backtracking solution will quickly find one.

Gotchas[edit]

  • The problem statement incorrectly talks about permutations, ignore this.
  • Note that just because your solution may not agree exactly with the sample output does not mean your output is incorrect. Because of the wrapping, one can start at any place in the sequence. Also any sequence can be reversed. Thus the judge has an alternate checker for this program, any correct sequence is valid. You can even code your own checker for this problem.

Notes[edit]

The sequences are known under the name de Bruijn sequences.

Optimization[edit]

The nice solution to this problem is seeing that it can be represented as an Euler tour in a more wisely constructed graph. Instead of each vertex representing the a full string of length s, each vertex will only correspond to a string of length s-1. Add directed edges in the same way as above. This time the ouroboros string corresponds to a closed Euler tour in this graph. When we find the tour, the string can be constructed in the same way as above. There are effective algorithms for finding Euler tours in general graphs, see the Euler tour article.

Proof: The graph is clearly strongly connected (in s-1 steps I can reach any vertex from any other vertex) and the in-degree and out-degree of each vertex is equal to b. Thus this graph has a closed Euler tour. This tour corresponds to an optimal solution of length b^{s}, which contains each s-letter string exactly once. To see this, note that if we are in a vertex labeled a_{1}\dots a_{{s-1}} and traverse an edge labeled a_{s}, we just added the string a_{1}\dots a_{s} into our ouroboros string.

Input[edit]

3 3
4 2
3 4
2 5
6 1
1 6

Output[edit]

000100201101202102211121222
0000100110101111
0001002003011012013021022023031032033111211312212313213322232333
0010203041121314223243344
0
012345