控制重力 - And Yet It Moves

最近玩了一幾有趣的 PC遊戲 - And Yet It Moves

基本上是 2D 的解謎遊戲, 特別之處在於可以控制重力方向 (上下左右)
(不禁想起那些經典的 BFS 練習題)

不難玩, 用了數個小時便玩完
不過每關也有新的元素, 所以不悶的

Trailer:

Sem 4 之後: 516 Project

由於去 world final 的關係, 逼不得而把 516 project 的 deadline 延後數日
topic 是 Graph Sparsifiers
一開始會選這個 topic 是覺得個 result 很強勁很神奇, 大約就是說
Given 一個任意的 weighted graph G, 可以 produce 一個 O(n/ε²) 條 edge 的 graph H, 而 H 是 G 的 ε-approximation

由於時間關係, 基本上只看了一篇 paper
一開始被整頁的運算, 公式嚇到
不過後來發現那些運算大多都是移項, 加加減減
真正難的地方在於對整個 proof 流程的理解
閉關了數個下午總算大致明白

做完後的感覺:
首先覺得個 proof 很神奇, 很多步都很有出 cheat 的感覺
對 linear algebra 又熟了一點
「知道 result」和「知道 proof」的分別就像睇戲和睇 behind the scene

CERC 2010 J - Justice for All

題目: Construct a bipartite graph with at most 200 vertex at each side that has exactly N (1 ≤ N ≤ 10⁶) perfect matching

如果想要一個有 k 個 perfect matching 的 graph, 可以使用 k 個 vertex construct 到
方法是 l[1] 連到 r[1], r[2].. r[k], 然後 l[i] 連到 r[1] 和 r[i]
fix 了 l[1] 的 match vertex 便 fix 了整個 matching

想要一個有 N 個 perfect matching 的 graph, 可以把 N factorize, 然後把上述的 subgraph disjoint union 一起
當然如果 N 有很大的 prime factor 便會使得 vertex 數目超出限制
既然 x 不足夠, 就要想方法去 implement + operation

例如, 把 N 分解成 Sum{2^m}
首先要 construct 一個有 2^m 個 perfect matching 的 connected subgraph
使用 m+1 個 vertex, 加上 edge {(l[i], r[j]): i ≤ m, j ≤ i+1}

為了做到 +, 我們希望每個 subgraph 都有兩種 'mode': 1 個 matching 以及 2^m 個 matching
並且每次有 exactly 一個 subgraph 是使用後者的 mode
因此, 便想到再新增一個 'control vertex'
一個 subgraph 的第 m+1 個 node match 到這個 control vertex 的話, 便可以有 2^m 個 matching
否則只有一種

因此, 只要在每個 subgraph 的 l[m+1] 連到 r[1] 及 control vertex
如果連到 control vertex 的話便可以有 2^m 個 matching
否則 l[i] 的 matching 數目便會 reduce 為 1 個
就可以砌到任意數目的 perfect matching

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, 十分煩膠