UVa 517

From Algorithmist
Jump to navigation Jump to search

517 - Word[edit]

Summary[edit]

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

Explanation[edit]

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.

Gotcha's[edit]

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

Optimizations[edit]

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[edit]

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[edit]

ababbabb
aaaaaaaaabaaaab
abb
aabbb
abbbbbbb

References[edit]

  1. Number of 2-bit strings under cyclic isomorphism