TC ReverseResources

• http://www.topcoder.com/stat?c=problem_statement&pm=7415

Summary

You are given some resource strings which contain letters and the special substitution command %s. Each error message in the system is derived starting from the string "%s" consisting only of the substitution symbol, and then by successively replacing occurrences of %s by resource strings. You are to find how many different ways a given error message can be derived. (See link for a more precise definition of how error messages can be built.)

From TopCoder Single Round Match 342.

Example

• If the resource strings are
  • "%s and %s"
  • "one"
• Then "one and one and one" can be generated in 2 ways.

Hints

• The problem defines a special kind of Context Free Grammar.
• Look at the categories: use dynamic programming!
• Chomsky Normal Form may also give you an idea of what to do.