ICPC 2929 Hang or not to hang

題意：

給定一個 program（LOC ≤ 16）
有 ≤ 32 個 boolean variable（值 = 0 或 1）
instruction 有以下 10 種：

 
每個 instruction 執行時間花費 1 cycle（包括 STOP）

variable 的起始狀態是隨機的
問，程序最早結束時間可以是多少？
是否對任何起始狀態，都會「Loop死」？

---

枚舉全 2³² 種 variable 的起始狀態再逐一 simulate
顯然會超出 時間／memory 限制...

細心一想... 所謂 randomness 其實只是 JZ 指令

---

分析：

情況一）

若果沒有 JZ (jump if) 指令，則結果是 deterministic

──即無論 varaible 的起始值如何，結果都是一樣

情況二）

假設只有一項 JZ 指令：「JZ x a」
則我們只關注 a 的值
在這情況下，所謂的 randomness，便是 a 的值
以及能有機會影響 a 值 的 variable（包括 a 本身）

Claim：能影響 a 值的 variable，最多 16 個

證：令 S := 這些 variable 的集合（i.e., 有機會影響其 a 值的 variable）

我們把每個 variable 想成一個 node（一共 32 個）
每個 binary instruction（e.g., AND a b）想成一條 edge
e.g., 「AND a b」⇒ 從 a 往 b 連一條 edge

顯然，a 可到達 (reachable) 的 node 的集合就是 S

由（不計 STOP 的）instruction 數量最多 15個可知

1. edge 的數量 ≤ 15 
2. 最多 30 個 variable 出現

把 edge 的 direction 去掉，換成 undirected
在這個新 graph 當中
令 T := 包含 a 的 connected component 的 node 集合

易知，T ⊆ S 及 | T | ≤ 16

情況三）

最後，即使 JZ 指令多於一個
「有關痛癢」的 variable 的數目依然 ≤ 16

---

算法：

所以，我們只消顧及這 16 個 variable 的值

program 的狀態只取決於下列兩項：

• 目前所在的 instruction
• 這 16 個 variable 的值

∴ 狀態數目 最多 16 × 2¹⁶ 個

BFS 就 OK了！

在起點暴力窮舉這 ≤ 16 個 variable 的起始值（一共 ≤ 2¹⁶ 個）
expand 過程中，只執行有關這些 variable 的 instruction

最後
若果未能到達 其中一條 STOP 指令 ⇒「Loop 死」
若否，便可知道「最短路」

---

實踐：

BFS
就是做！

bitwise operation 大概無可避免
instruction 改變 varaible 值這操作... 要 小心+小心+小心...

在 PKU 上也可以提交
但 memory 比較緊...

---

Subtlety：

對於沒有 JZ 指令存在的情況，可以融入至上述的 BFS，無須另外處理

──「假裝」只有 1個重要的 variable，再把其值 set 為 0

---

當時的思路：

一開始想到 brute force exhaust 所有 state...

但 變數一共 32個.... 2³² 這數... 無論 時間 還是 memory 都絕對承受不了

後來發現 instruction 數目只有 16 後，突然想出上述算法