517 - Word
Word is a nice little problem, where a little bit of discrete mathematics will give all the insight needed for a solution.
We are given a word w of length n in a 2-character alphabet , followed by a structured set of rules which define a function . We are then given a number s (possibly very large, as big as ), and we are asked to output . That is, the result of applying to times. Clearly, the naive method, actually doing s applications of f, will timeout. Notice that after evaluating f at most times, the next function evaluation must be exactly the same as some previous function evaluation by the pigeon hole principle. Also notice that 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.
- The intended output is the lexicographically least cyclic representation of the string, eg baba should be shifted to abab.
Find the minimum lexicographic cyclic representation of each iterate after each iteration to give a reasonable size reduction to the number of possible states.
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
ababbabb aaaaaaaaabaaaab abb aabbb abbbbbbb