# UVa 517

Jump to navigation Jump to search

## Summary

Word is a nice little problem, where a little bit of discrete mathematics will give all the insight needed for a solution.

## Explanation

We are given a word w of length n in a 2-character alphabet ${\displaystyle \{a,b\}}$, followed by a structured set of rules which define a function ${\displaystyle f:\{a,b\}^{n}\rightarrow \{a,b\}^{n}}$. We are then given a number s (possibly very large, as big as ${\displaystyle 2\times 10^{9}}$), and we are asked to output ${\displaystyle f^{s}(w)}$. That is, the result of applying ${\displaystyle f}$ to ${\displaystyle w}$ ${\displaystyle s}$ times. Clearly, the naive method, actually doing s applications of f, will timeout. Notice that after evaluating f at most ${\displaystyle 2^{n}}$ times, the next function evaluation must be exactly the same as some previous function evaluation by the pigeon hole principle. Also notice that ${\displaystyle 2^{n}}$ is a very feasible amount of computation, since n is no bigger than 16. Thus, we can iterate f until we hit a previous iterate, keeping track of the location in the sequence of every string, and then do some modular arithmetic to figure out which string that we have already seen which will be the s'th string in the sequence.

## Gotcha's

• The intended output is the lexicographically least cyclic representation of the string, eg baba should be shifted to abab.

## Optimizations

Find the minimum lexicographic cyclic representation of each iterate after each iteration to give a reasonable size reduction to the number of possible states.

## Input

8
abbbbaba
aaab
aabb
abab
abbb
baaa
baba
bbab
bbba
29411
15
baaabbaaabbabbb
aaab
aabb
abaa
abba
baaa
baba
bbaa
bbba
70309
3
bba
aaab
aabb
abaa
abba
baab
babb
bbab
bbbb
25683
5
abbba
aaab
aabb
abaa
abba
baab
baba
bbab
bbba
26168
8
abbbaaab
aaaa
aabb
abab
abba
baab
babb
bbab
bbbb
8662


## Output

ababbabb
aaaaaaaaabaaaab
abb
aabbb
abbbbbbb


## References

1. Number of 2-bit strings under cyclic isomorphism