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)

Sem 4 11/13

四月來臨, 意味距離 WF 只剩下約一個月
特訓 graph 和 geom
繼續 功課 + ACM + AOC 的 loop..

近排清掉了數份大功課, 總算可以稍為渣攤一下

CS 310 Project Coding Phase

多得 kn 的強力支援, 竟然可以在大約一日內過到 init code, 實為驚人
quote from whh: '最大問題係我地無一個對份功課感興趣'

CS 318 Project Phase 2

鬥獸棋, 我負責 C 的部份
又要用 ASCII art 砌 UI, 感覺像回到 CIT/ALCS 年代
發現自己還是不懂寫 GUI 的
其實用 C 也可以 code 得很 OO 的

CS 516 Asg 2

花了 4 個晚上, 最後還要半通頂才剛好做完
有大約 25% 要靠 chin, 不過對 course 的內容明白程度加深了
十分有得著的一份 assignment

CS 342 Project Phase 2

用 C 去模擬 CPU, 十分煩膠