Link to pdf version on UVa OJ
As you see in the problem description we have up to 10 rules, and at each step a character is replaced with the corresponding word. For example N->Not means at each step we look at the current word and we replace all 'N's with "Not".
What happened on my mind : First I was trying to find some kind of solution like finding n-th sentence of Fibonacci, like the matrix multiplication or something. Then I drew the underlying graph of the first test case.
After that the solution started to show itself to me. Let's say we are at G and we want to count the number of 's' after 5 step. All of a sudden I defined this function and tried to explore whether it makes sense or not.
Let's say target is fixed (per query), then:
f(c, step) : counts the number of occurrences of target after step steps, starting from c.
f(c, step) = f(c1, step-1) + f(c2, step-1) + ... + f(ck, step-1) + count( target, rule[c] )
So I could define f(c, step) based on smaller subproblems. By now I was sure I need to solve this using Dynamic Programming. I was just defining different things needed for a DP solution. After finding the recursion formula (which is the harder part in a DP solution) I checked for base case, when step = 0, it means this is what we have, we only have c and we cannot recurse any more. So if c equals target we return 1 otherwise we return zero.
And this is the top-down solution with memoization. Since dp is unsigned long long, I couldn't fill it with -1 (when a state is -1 it shows that this subproblem has not been solved yet), so I used a parallel boolean 2d array to know whether a subproblem has been solved or not. For more details look at the code on github.
Link to my own code on github
As you see in the problem description we have up to 10 rules, and at each step a character is replaced with the corresponding word. For example N->Not means at each step we look at the current word and we replace all 'N's with "Not".
What happened on my mind : First I was trying to find some kind of solution like finding n-th sentence of Fibonacci, like the matrix multiplication or something. Then I drew the underlying graph of the first test case.
Let's say target is fixed (per query), then:
f(c, step) : counts the number of occurrences of target after step steps, starting from c.
f(c, step) = f(c1, step-1) + f(c2, step-1) + ... + f(ck, step-1) + count( target, rule[c] )
So I could define f(c, step) based on smaller subproblems. By now I was sure I need to solve this using Dynamic Programming. I was just defining different things needed for a DP solution. After finding the recursion formula (which is the harder part in a DP solution) I checked for base case, when step = 0, it means this is what we have, we only have c and we cannot recurse any more. So if c equals target we return 1 otherwise we return zero.
And this is the top-down solution with memoization. Since dp is unsigned long long, I couldn't fill it with -1 (when a state is -1 it shows that this subproblem has not been solved yet), so I used a parallel boolean 2d array to know whether a subproblem has been solved or not. For more details look at the code on github.
Link to my own code on github
No comments:
Post a Comment