[Google DCJ] 解題筆記
這兩天與 @TimeString H 討論了 Distributed Code Jam,覺得相當有意思,決定把解題的一些想法寫在這邊。畢竟在平行演算法的世界中,有一些有趣的想法或問題,是平常我們在程式比賽的解題過程中不會遇到的。有任何心得也歡迎大家在這邊共同編輯、交流。

1 DCJ 題目的共同特色

1–1. Input 透過 API 存取

通常資料量會超級大,大約是 10910^9 數量級的。題目通常會給你一個函數,例如 GetIdentifier(i) 這樣的函數,可以讓每一個 node 都取得資料。但是,取得資料會需要一點時間,題目中通常也會明確告知呼叫一次 API 大約會花多少「微秒(microsecond)」的時間。請注意這裡的單位是微秒,也就是說其實一個 node 通常會有足夠時間存取到 2×1072\times 10^7 數量的 Input 的。

所以,一種常見的情形,便是設定每一個 node 的左、右界。如何把這個界線切得乾淨?

每一個 node 可以拿到自己的 MyNodeID() ,因此我們可以令左界與右界的半開半閉區間為:
 
[InputSize×MyNodeID()NumberOfNodes(),InputSize×MyNodeID()+1NumberOfNodes())\left[\displaystyle\mathrm{InputSize} \times \frac{\mathrm{MyNodeID}()}{\mathrm{NumberOfNodes}()}, \mathrm{InputSize}\times \frac{\mathrm{MyNodeID}()+1}{\mathrm{NumberOfNodes}()}\right)

由於是整數運算,可以先算上面乘號的部份,再除以分母。說真的,我之前都還傻傻地用
left_bound = (n / NumberOfNodes) * MyNodeID + min(n % NumberOfNodes, MyNodeID);
right_bound = (n / NumberOfNodes) * (MyNodeID + 1) + (n % NumberOfNodes > MyNodeID);

1–2. 通常是以「加快 10 倍或 100 倍」為目標

每一題通常允許跑 4~5 秒。而且題目通常都不會有太深刻的資料結構或麻煩的遞迴順序。
在這邊要提及一個重點:本地的計算量可以高達 10810^8,僅有 Input 的數量需要小心。

1–3. 避免串接式的「接收-計算-傳遞」模式

儘管可以傳遞到 8MB 的訊息總量,但是通常這步驟會不容易估計時間。避免串接式的「接收-計算-傳遞」,把一個可能可以高度平行化的方法寫成了 sequential,反而因此超時。大部分的簡單題都會比較尋求「每個 Node 分別計算 → 集中到 Node 0 彙整答案」的模式,減少來回溝通 Message 耗費的通訊資源。

1–4. Everything is Long Long

很多情形下連輸入都會到達 101810^{18} 的規模,因此儘管使用 Long Long 也要注意溢位的問題。

2 演算法中的平行思維 – DCJ 解題舉例

在 DCJ 的 Practice 裡面其實都有題目解答,這邊按照常見的幾個 Idea 把過去出現的有趣題目稍微分類。歡迎大家補充 😄 

2–1. 計算統計量

常見如 partial sum, rolling sum, max, average, majority 等,都可以輕易地被平行化。 
 
這題就是要判斷給定的 NN 個數字之中有沒有一個數字是絕對多數。

💡 參考題解:
把數字分成 100 堆,每一堆分別找出出現最多次的那個數字 maj1,maj2,,maj100maj_1, maj_2, \ldots, maj_{100}
我們宣稱『答案必定在這 100 個數字之中』。
因此,對於這 100 個數字,把它傳遞給每一個 Node,讓他們回傳每個數字出現的次數。最後再從中判斷是否有出現總次數嚴格超過 N/2N/2 的即可。

另一個解法是可以讓 Node 0 先隨機戳幾個點看看,若解存在,則有 1/21/2 的機會戳得到 Majority 代表的答案。再把這個數字丟進去問就可以了。(不過要小心,若生測資的 .h 檔案很邪惡的話,這方法就不能用了。)

🤔 延伸思考:
請構造一組測試資料使得真正的答案僅出現在 100 個數字之中恰好一次。因此這 100 個數字都必須逐一檢查才行。
 
我們想要對一個給定的序列將之由小到大排序。已知這個序列有神奇的特性:對於原本在位置 ii 的數字,其排序後位置保證在 [iK,i+K][i-K, i+K] 這個範圍內。請輸出排好序後的 checksum:即第 ii 個數字乘以 ii 後的總和、除以 2202^{20} 後輸出。

💡 參考題解:
假設每一個 Node 要負責的範圍是 [l,r][l, r],我們只要讀取 [lK,r+K][l-K, r+K] 這個範圍的輸入拿來排個序就可以了!

⚠️ 特別注意:
輸入的數值範圍是 long long,是 long long!在乘以 ii 之前請務必先行取餘數。