解題區/解題區 - 其他題目

PTC 201508 八月小結

contents

  1. 1. Problem A Date Matching Problem
  2. 2. Problem B Community Detection in Social Media
  3. 3. Problem C Treasure
  4. 4. Problem D Coloring Statues
  5. 5. Problem E CPU

由於代碼有點長，所以就放在 Github 上進行瀏覽，在此只提供文字說明，題解代碼 點我。

現在還沒提供 OJ 線上測試，不保證代碼和算法的正確性。

Problem A Date Matching Problem

在一個二分帶權匹配問題中，模擬近似解的做法：每一次挑選權值最大的兩個未配對男女，請問最後得到的帶權匹配最大為何。

純粹模擬，沒有要求最大帶權匹配，最大帶權匹配可以用 KM 算法或者是最少費用流去完成。題目沒說明權重是否有相同情況，那麼模擬結果可能會有點問題在。

Problem B Community Detection in Social Media

在社群媒體中，用節點表示一個個體，節點和節點之間會有所關連，這時候用一條邊連接起來，邊上用權重大小表示關聯強度。現在要將這 $N$ 個節點分成恰好 $K$ 群，每一個節點只能分配到一個群集中，為了使得分群效果更好，定義分群的好壞程度，對於任意兩點若有一條邊且在不同群，則這些點對的邊權重最大值就是分群評價，這個評價分數越低越好，意即群之間的相似度越低越好。請求出分群評價最低為何。

貪心，按照邊權由大排到小，接著使用 disjoint set 並查集來合併，直到低於 K 群，此時的邊權就是答案。

Problem C Treasure

Alice 和 Bob 這對狗男女 又在玩遊戲，他們要分 $N$ 個寶物，每個寶物到兩個人手上的價值都不同，同時分配寶物的個數最多只能差 1，請問最少分配價值差的絕對值為何。

由於 $N \le 35$，直接窮舉 $O(2^N)$ 消耗時間，於是可以剖半搜索，類似中間相遇法，窮舉前一半、後一半的所有組合，接著二分去合併，時間複雜度 $O(2^{N/2} N)$。特別小心寶物數量只能差 1，需要窮舉其中一個人的分配數量、計算組合時紀錄其中一個人的個數。

Problem D Coloring Statues

夜晚不死之神－夜神月，由於他太無聊，決定去更改院子裡的雕像顏色，顏色只有黑白兩種，他會玩到所有雕像顏色都為黑色時停止，請問 $K$ 天之後黑色雕像的顏色數。

$N$ 個雕像排成一列，各自擁有初始化的顏色，每一天的規則如下

所有雕像顏色為黑色就停止操作 更改最左側的雕像顏色，滿足前面所有操作都不重複的狀態，並且結束這一天。
* 一天只能改一個雕像，並將黑色改白色、白色改黑色。

變化的格雷碼計算，$N, \; K$ 非常大，不能用遞迴慢慢窮舉。那麼就 wiki 得到計算方法。

1
2
3
4
5
6
7
8
9
10
unsigned int binaryToGray(unsigned int num) {
    return (num >> 1) ^ num;
}
unsigned int grayToBinary(unsigned int num) {
    unsigned int mask;
    for (mask = num >> 1; mask != 0; mask = mask >> 1) {
        num = num ^ mask;
    }
    return num;
}

主要核心為這兩個二進制和格雷碼的相互轉換，需要運用二進制的大數操作，只有位移、XOR、加法模擬，代碼的複雜程度可以接受。特別小心，由於雕像一開始有初始狀態，最終盤面 (全黑) 與格雷碼實際會有所不同，需要做每一個位置的黑白交換，否則不能滿足與前幾天都不重複的狀態。

用大數方法模擬上面兩個函數，並且在加法運算和最終盤面之間偵測 overflow 即可，時間複雜度 $O(N^2)$。

Problem E CPU

多核心排程問題，有 $C$ 個 CPU，每一個 CPU 可以用 $K$ 種不同的效能去完成工作，選擇哪一種效能會反映在處理時間$T_i$ 和電量消耗$E_i$，不同顆 CPU 的情況也各自不同，但它們可以平行工作。現在要安排 $N$ 份工作，每一個工作有 $I$ 個單位指令，不用考慮先做後做的順序，一旦他們進入排入 CPU，則一定會做完才能排定下一份工作。

每一個工作指派到 CPU 上會有處理的周轉時間 $Tu$ (turnaround time) 和能量消耗 $E$ (enery cost)，給定兩個常數$R_t, \; R_e$ 分別為總評價的參數，目標使得$\sum Tu_i R_t + E_i R_e$ 最小。

把$R_t, \; R_e$ 直接反應到效能和電量消耗，融進去之後就不用考慮。

首先，解決單一個 CPU 操作如何解決排程問題，藉由預先支付來解決週期時間 (turnaround time) 的計算，因此剩餘工作有 $R$ 個時，若要選入$Job_i$ 且使用 CPU 的第 $j$ 個方案，花費為$I_i \times R \times T_i + I_i \times E_i$，預先支付剩下 $R$ 個工作會增加的量，每一次抓最小的工作進行安排，樸素實作需要 $O(N^2 K)$。

從數學公式看出來，指令個數$I_i$ 可以提出，觀察一下，就是最短工作優先 (SJF) 的想法讓 turnaround time 總和最小，排序指令數量由小到大安排即可，複雜度降至 $O(N \log N + NK)$。

接著，考慮多核心情況，由於不知一個核心有多少個工作，無法預先支付接下來的工作成本，但 SJF 的思路仍然成立，即在每一個核心中，工作順序仍然是按照指令數量由小到大依序做。為了解決無法支付的問題，反向安排工作，決定最後一個工作要分配到哪一個 CPU，對於安排工作去找到 CPU 的成本$\text{CPUjob}_i \times T_i + E_i$ 最小，並且累計那一個 CPU 已經安排多少個工作$\text{CPUjob}_i$，複雜度降至 $O(N \log N + N (K + \log C))$