控制重力 - 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