Loading...

​​[Google DCJ] 解題筆記

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

​​1 DCJ 題目的共同特色

​​1–1. Input 透過 API 存取

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

​​

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

​​

​​每一個 node 可以拿到自己的 MyNodeID()​ ，因此我們可以令左界與右界的半開半閉區間為：

​​ 

​​​​$\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 秒。而且題目通常都不會有太深刻的資料結構或麻煩的遞迴順序。

​​在這邊要提及一個重點：本地的計算量可以高達 ​​$10^8$​，僅有 Input 的數量需要小心。

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

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

​​1–4. Everything is Long Long

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

​​

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

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

​​2–1. 計算統計量

​​常見如 partial sum, rolling sum, max, average, majority 等，都可以輕易地被平行化。 

​​

​​DCJ 2015 Practice Round - pC Majority

​​這題就是要判斷給定的 ​​$N$​ 個數字之中有沒有一個數字是絕對多數。

​​

​​​💡​ 參考題解：

​​把數字分成 100 堆，每一堆分別找出出現最多次的那個數字 ​​$maj_1, maj_2, \ldots, maj_{100}$​

​​我們宣稱『答案必定在這 100 個數字之中』。

​​因此，對於這 100 個數字，把它傳遞給每一個 Node，讓他們回傳每個數字出現的次數。最後再從中判斷是否有出現總次數嚴格超過 ​​$N/2$​ 的即可。

​​

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

​​

​​​🤔​ 延伸思考：

​​請構造一組測試資料使得真正的答案僅出現在 100 個數字之中恰好一次。因此這 100 個數字都必須逐一檢查才行。

​​

​​DCJ 2015 Online Round - pB Almost Sorted

​​我們想要對一個給定的序列將之由小到大排序。已知這個序列有神奇的特性：對於原本在位置 ​​$i$​ 的數字，其排序後位置保證在 ​​$[i-K, i+K]$​ 這個範圍內。請輸出排好序後的 checksum：即第 ​​$i$​ 個數字乘以 ​​$i$​ 後的總和、除以 ​​$2^{20}$​ 後輸出。

​​

​​​💡​ 參考題解：

​​假設每一個 Node 要負責的範圍是 ​​$[l, r]$​，我們只要讀取 ​​$[l-K, r+K]$​ 這個範圍的輸入拿來排個序就可以了！

​​

​​​⚠️​ 特別注意：

​​輸入的數值範圍是 long long，是 long long！在乘以 ​​$i$​ 之前請務必先行取餘數。