UVa 517
From Algorithmist
Contents |
[edit] 517 - Word
[edit] Summary
Word is a nice little problem, where a little bit of discrete mathematics will give all the insight needed for a solution.
[edit] Explanation
We are given a word w of length n in a 2-character alphabet {a,b}, 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 fs(w). That is, the result of applying f to w s times. Clearly, the naive method, actually doing s applications of f, will timeout. Notice that after evaluating f at most 2n times, the next function evaluation must be exactly the same as some previous function evaluation by the pigeon hole principle. Also notice that 2n 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.
[edit] Gotcha's
- The intended output is the lexicographically least cyclic representation of the string, eg baba should be shifted to abab.
[edit] 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.
[edit] Input
8 abbbbaba aaab aabb abab abbb baaa baba bbab bbba 29411 16 baaabbaaabbabbba 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
[edit] Output
ababbabb aaaaaaaababaaaab abb aabbb abbbbbbb
