# HW-4
### 1
**演算法 :**
Step 0: 把所有點依照 X 軸由小到大排序，若 X 軸相同就依照 Y 軸由大到小。
Step 1: 若 n = 1，回傳 S 中唯一一個點的 rank = 0 並結束
Step 2: 找出所有點的 X 軸中位數，畫出垂直於 X 軸的直線 L，將 S 中的點分為兩個集合 $S_L 和 S_R$
Step 3: 遞迴使用 2D ranking 演算法分別求出 $S_L 和 S_R$ 中所有點的 rank
Step 4: 掃描所有在 S = $S_L \cup S_R$ 中的點，設定 cnt = 0。若掃到 $S_L$ 中的點則 cnt 加一；反之，若掃到 $S_R$ 中的點，令為 P，則將 P 點的 rank 加上目前的 cnt ( 在 $S_L$ 中 y 座標比 P 小的點個數)。最後回傳所有點的 rank。

**Time : O(nlgn)**
Step 0 : O(nlgn)
Step 1 : O(1)
Step 2 : O(1)
Step 3 : 2$T(\frac{n}{2})$
Step 4 : O(n)
=> Step 1 ~ 4 總共 O(nlgn)，再加上前處理 O(nlgn) => 2D Ranking Time complexity 為 O(nlgn)
### 2
(a)
(b)
若好晶片有超過 $\frac{n}{2}$ 個，則可利用以下演算法保證篩出一個好晶片，接著再利用這個好晶片去比對每個晶片就可以知道每個晶片是好的還是壞的。
1. 將所有晶片兩兩配對，若 n 為奇數，多出來的晶片這輪先不處理。
2. 若結果出現至少一壞，捨棄這兩個晶片，因為我們只能知道其中一個是壞掉，無法判斷哪個是好的。
3. 若結果出現兩好，捨棄其中一張，這樣還是可以確保好晶片數量超過 $\frac{n}{2}$。
4. 重複以上動作直到剩下 1 或 2 張晶片，則剩下的晶片一定是好的。

Step 3 證明 : 為何捨棄其中一個可以確保好晶片數量超過 $\frac{n}{2}$?
由結果可知，這兩個晶片可能都是好的或都是壞的。

Case 1: 兩個晶片都是好的
(a )如果 n 為偶數，在最差的清況下，好晶片有 $\frac{n}{2} + 1 個$，壞晶片有$\frac{n}{2} - 1 個$，好晶片多壞晶片兩個，所以丟掉一個好晶片還是滿足好晶片數量大於一半。
(b) 如果 n = 2k + 1 為奇數，在最差的清況下，好晶片有 k + 1 個，壞晶片有 k 個。如果在 Step 1 被留下來的是**好晶片**，則剩下的配對全部都是一好一壞，則這些晶片都會被 Step 2 丟棄掉，最後剩下一個晶片一定是好的，故成立。如果在 Step 1 被留下來的是**壞晶片**，則留下來兩兩配對的好晶片有 k + 1 個，壞晶片有 k - 1 個，好晶片多壞晶片兩個，所以丟掉一個好晶片還是滿足好晶片數量大於一半。

Case 2: 兩個晶片都是壞的
因為題目已知超過 $\frac{n}{2}$ 為好晶片，所以丟掉一個壞晶片還是符合好晶片數量大於一半。

(c\)
### 3

### 4
[Edit Distance 筆記](https://hackmd.io/@_EUdnTNeRl-LUa2kz_WvLw/S1mZ_XYua)
### 8
[Weighted Interval Scheduling](https://hackmd.io/@_EUdnTNeRl-LUa2kz_WvLw/SJKCLFYwp)
### 9
解法二 : [Erdős–Gallai Theorem](https://hackmd.io/@_EUdnTNeRl-LUa2kz_WvLw/B1_y5F_Pp)

### 10

### 11
想法 : 把所有數字進行 XOR 運算，結果就是缺少的數字


int findMissing_1(int bit, vector<int> indices, vector<vector<int>> array){
    if(bit == 0){
        int digit = array[indices[0]][bit] == 0 ? 1 : 0;
        return digit;
    }
    vector<int> A0, A1;
    int n0 = 0, n1 = 0;
    for(int i:indices){
        if(array[i][bit] == 0){
            n0++;
            A0.push_back(i);
        }
        else{
            n1++;
            A1.push_back(i);
        }
    }

    if(n0 < n1){
        return findMissing_1(bit-1, A0, array) + pow(2, bit) * 0;
    }
    else{
        return findMissing_1(bit-1, A1, array) + pow(2, bit) * 1;
    }
}
vector<int> toBinary(int n)
{
    vector<int> r;
    while(n!=0) {
        int tmp = (n%2==0 ?0:1);
        r.push_back(tmp); 
        n/=2;
    }
    
    return r;
}
vector<vector<int>> complement(vector<vector<int>> array, int n){
    int N = pow(2, ceil(log2(n)));
    for (int i=0;i<N;i++){
        if(i >= n+1){
            vector<int> temp = toBinary(i);
            array.push_back(temp);
        }else{
            reverse(array[i].begin(), array[i].end());
        }
        
    }
    return array;

### 12

Function `P(max_k, max_type, i, j)`