WF 2009 K - Suffix-Replacement Grammars

有趣的題目, 雖然其實不難不過挺 inspiring
Link: http://livearchive.onlinejudge.org/external/44/4455.pdf

解法

猜想: 只需考慮把 S 的 suffix 替換成某一條 rule 中的 string 的 string
一開始覺得每次做 replacement 前, current string 必定為 starting string 的 prefix + 某條 rule 為 suffix
但是很想便找到反例, 因為使用 production rule 的次序不一定按 increasing length order
例如
Goal: ABC → DEF
Rule:
BC → GH
H → I
AGI → DEF

於是, 便想到要把 string S transform 成 string T, 主要有兩種方法:
1. S → I₁ → I₂ → .. → T  (same length)
2. 對於每一個 S 與 T 的 common prefix, transform 餘下的 suffix

方法1 只要 shortest path 便可輕鬆解決
方法2 把問題 reduce 成 length 更小的 case, 所以只要由 length=1 開始便可以遞推上去

由於 constrains 不大加上已經是早上七時, 所以隨便寫了 Floyd-Warshall 和很多地方都沒 optimize
Execute 了差不多 30s (time limit = 36s)

答案上限

由於以前聽聞過, 答案是會 exceeds 32-bit integer 的所以避免了 (可能的) overflow 錯棍
但是上限是多少呢 ?
一開始以為是 100²⁰, 當然不是 tight 的

假設對 length 為 k 的 transform 的 rule 有 r_k 條 ( Sum{r_i} ≤ 100 )
假設 X, Y 為 length k 的 string, 若 X 能 transform 成 Y, 最多要做 MAX_k 次

所以, 得 MAX_k = MAX_k-1 * r_k
而且 MAX₁ = r₁
所以答案上限 = Product{r_i}

但也不是一眼看出即是多少, 2⁵⁰? 3³³?
使用 dp 可得最大約為 7.4 * 10¹⁵ (3³² * 4)