# UVa 10506

## Summary

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

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

• 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.