2016-01-18

2016 Facebook Hacker Cup Round 1

1. Facebook Hacker Cup Round 1

Facebook Hacker Cup Round 1

A. Coding Contest Creation

給 $N$ 個整數序列，每一個整數表示題目難度，可以在序列中插入整數，目標在序列中依序挑出 4 個整數作為比賽題目配置，並且要求不改變原本序列順序，滿足題目難度嚴格遞增，相鄰題目難度不大於 10，請問至少加入幾道題目。 (意即要插入題目的數量使得序列長度被 4 整除。)

最保守的方式 DP，只需要 $\mathcal{O}(N)$ 時間，記錄狀態 dp[i] 表示前 i 個 (不含) 整數滿足前述要求至少要插入幾個數，得到

$$dp[i] = min(dp[i], dp[j] + 4 - (i-j+1)), \; i -3 \le j \le i, \; c_{j, i} + (i-j+1)\le 4$$

，計算 $c_{j, i}$ 列出 $A_j, A_{j+1}, ..., A_{i}$ 得知至少要插入幾個數，貪心計算兩兩數字之間的差值 $\textit{diff}_k$，$c_{j, i} = \sum (\left \lceil \frac{\textit{diff}_k}{10} \right \rceil - 1)$。每一個轉移最多 4 次，故時間複雜度 $\mathcal{O}(N)$。

B. Laundro, Matt

小夥伴有 $L$ 件未洗衣物，洗衣店有 $N$ 台洗衣機和 $M$ 台烘衣機，洗衣機和烘衣機一次只能處理一件衣物，而對於每一台洗衣機對於衣物都有不同的處理時間 $W_i$，烘衣機則固定每 $D$ 時間就能烘好一次衣物。小夥伴可以暫存洗好衣物的籃子無限大，同時移動衣物的時間快到可忽略，請問至少要隔多久才能帶著所有洗好烘好的衣物離開洗衣店。

時間軸模擬題，用 priority queue 維護時間軸，在每一個時間戳記下檢查事件發生。模擬兩台機器交換衣物會稍微複雜，事件定義有三種：

某洗衣機可以在 $t_i$ 時間完成洗好一件衣服，下一次事件發生則是 $t_i + W_i$。不考慮何時放入衣物，每一次抓最近可完成的洗衣機進行清洗，直接當作洗好。
若有空的烘衣機，將洗好但未烘的衣物放入烘衣機，並將此烘衣機設定忙碌。並且標記 $t_i + D$ 時間此烘衣機會從忙碌變成閒置。
從忙碌變成閒置的烘衣機，記錄有多少衣物洗好烘好。

時間複雜度 $\mathcal{O}(L \log (N+M))$。

C. Yachtzee

宅宅的退休工程師想建造遊艇，預算總額從 $[A, B]$ 隨機地挑一個，請問建造所剩餘金額的期望值為何。建造策略如下：

造遊艇分成 $N$ 個步驟，每一個步驟各自有其預算 $C_i$。
造完一艘後，便著手建造下一艘，
直到某一個步驟預算不夠，便放下手上的計劃。(可能建造出半艘船)

數學期望值計算，時間複雜度 $\mathcal{O}(N)$，窮舉在每一個步驟罷工，因為卡在區間 $[A, B]$，計算剩餘金額在此步驟停止會稍微複雜。一艘船需要的預算為 $C$，那麼在某些情況 $C_i$ 會完全被 $[A, B]$ 包含，累計期望值 $\frac{0+C_i}{2}$，接著針對部分在區間 $[A, B]$ 的邊界情況。計算方法很多，在此也不多作解釋。

D. Boomerang Tournament

$2^N$ 個人進行樹狀單淘汰賽，給予每名選手互打的獲勝結果，在還沒公佈對局樹狀圖之前，請問每名選手預期能得到的最好和最壞名次為何。排名為嚴格多於自己的勝場數的選手個數。

選手最多 16 位，直接來個 $\mathcal{O}(16!)$ 絕對不行。當然樹狀圖的對稱性也許足以讓數量變得在時間內可窮舉完畢，但寫起來也複雜許多。

因此，利用位元壓縮 dp[參與選手集合][勝者] = 1/0 記錄子樹的情況，只需要 $\mathcal{O}(2^{16} \times 16)$ 個狀態總數，在集合合併處理需要窮舉子集合，由於我們只需要窮舉特定集合大小，複雜度不會到 $\mathcal{O}(3^{16})$ 這麼慘。合併時根據兩子樹的勝者相對打，同時紀錄兩位可夠晉級的最大最小回合數即可。

### Solution ###

#### A. Coding Contest Creation ####

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 131072;
const int LMAX = 0x3f3f3f3f;
int dp[MAXN];
int main() {
    int testcase, n, x;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        vector<int> A;
        for (int i = 0; i < n; i++)
            scanf("%d", &x), A.push_back(x);
        
        for (int i = 0; i <= n; i++)
            dp[i] = LMAX;
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            vector<int> S;
            for (int j = 0; j < 4 && i+j < n; j++) {
                if (j && A[i+j] <= A[i+j-1])
                    break;
                S.push_back(A[i+j]);
                int inner = 0;
                for (int k = 0; k < j; k++) {
                    int diff = S[k+1] - S[k];
                    inner += max(diff / 10 + (diff % 10 != 0) - 1, 0);
                }
//                printf("[%2d,%2d] %d %d\n", i, j, inner, (int) S.size());
                if (inner + S.size() <= 4) {
//                    printf("update %d = %d from %d\n", i+j+1, dp[i] + 4 - (int) S.size(), dp[i]);
                    dp[i+j+1] = min(dp[i+j+1], dp[i] + 4 - (int) S.size());
                }
            }
        }
        printf("Case #%d: %d\n", ++cases, dp[n]);
    }
    return 0;
}

B. Laundro, Matt

#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 131072;
const int LMAX = 0x3f3f3f3f;
int main() {
    int testcase;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int L, N, M, D, W, target;
        multiset< pair<long long, int> > EMPTYN;
        multiset<long long> EMPTYM;
        set<long long> timeline;
        multiset< pair<long long, int> > S;
        scanf("%d %d %d %d", &L, &N, &M, &D);
        for (int i = 0; i < N; i++) {
            scanf("%d", &W);
            EMPTYN.insert({W, W});
            timeline.insert(W);
        }
        
        target = L;
        int basket = 0;
        int complete = 0;
        long long ret = 0;
        timeline.insert(0);
        while (timeline.size() != 0) {
            long long time = *timeline.begin();
            timeline.erase(timeline.begin());
            while (L != 0 && EMPTYN.begin()->first <= time) {
                pair<long long, int> e = *EMPTYN.begin();
                EMPTYN.erase(EMPTYN.begin());
                EMPTYN.insert({e.first+e.second, e.second});
                timeline.insert(e.first+e.second);
                L--, basket++;
            }
            while (!EMPTYM.empty() && *EMPTYM.begin() <= time) {
                EMPTYM.erase(EMPTYM.begin());
                M++;
                complete++;
                if (complete == target)
                    ret = time;
            }
            while (basket > 0 && M > 0) {
                basket--, M--;
                EMPTYM.insert(time + D);
                timeline.insert(time + D);
            }
        }
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}

C. Yachtzee

#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAXN = 131072;
const int LMAX = 0x3f3f3f3f;
long long C[MAXN];
double f(double l, double r) {
//    printf("[%lf, %lf]\n", l, r);
    return (r - l) * (r + l) / 2;
}
int main() {
    int testcase;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int N;
        double A, B;
        scanf("%d %lf %lf", &N, &A, &B);
        for (int i = 0; i < N; i++) {
            scanf("%lld", &C[i]);
        }
        
        double ret = 0;
        double sum = 0, pre = 0;
        for (int i = 0; i < N; i++)
            sum += C[i];
        for (int i = 0; i < N; i++) {
            double pp = ceil(A / sum);
            double qq = floor(B / sum);
            int st = pp, ed = qq;
            set<int> S;
            for (int j = max(0, st-3); j <= st+3; j++) {
                if (S.count(j))
                    continue;
                double l = j * sum + pre, r = j * sum + pre + C[i];
                if (max(l, A) <= min(r, B)) {
                    ret += f(max(l, A) - (j * sum + pre), min(r, B) - (j * sum + pre));
                }
                S.insert(j);
            }
            for (int j = max(0, ed-3); j <= ed+3; j++) {
                if (S.count(j))
                    continue;
                double l = j * sum + pre, r = j * sum + pre + C[i];
                if (max(l, A) <= min(r, B)) {
                    ret += f(max(l, A) - (j * sum + pre), min(r, B) - (j * sum + pre));
                }
                S.insert(j);
            }
            
            ret += f(0, C[i]) * max((ed-3) - (st+3)-1, 0);
            pre += C[i];
        }
        
        ret /= (B - A);
        printf("Case #%d: %.9lf\n", ++cases, ret);
    }
    return 0;
}
/*
 5
 2 100 200
 100 100
 2 100 200
 50 100
*/

D. Boomerang Tournament

#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAXN = 131072;
int g[16][16];
int dp[1<<17][16];
int main() {
    int testcase;
    int cases = 0, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                scanf("%d", &g[i][j]);
        }
        
        int ret[16][2], A[16];
        A[0] = n/2;
        for (int i = 1; i < n; i++)
            A[i] = A[i-1]/2;
        for (int i = 0; i < n; i++)
            ret[i][0] = 0, ret[i][1] = __builtin_ffs(n)-1;
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++)
            dp[1<<i][i] = 1;
        int round[64] = {1};
        for (int i = 0; i < 5; i++)
            round[1<<i] = i;
        for (int i = 0; i < (1<<n); i++) {
            int cnt = __builtin_popcount(i);
            if (cnt != (cnt & (-cnt)))
                continue;
            if (cnt == 1)
                continue;
            for (int j = (i-1)&i; j; j = (j-1)&i) {
                if (__builtin_popcount(j) != cnt/2)
                    continue;
                for (int p = 0; p < n; p++) {
                    if (dp[j][p])
                    for (int q = 0; q < n; q++) {
                        if (dp[i^j][q]) {
                            if (g[p][q]) {
                                dp[i][p] = 1;
//                                printf("%d %d %d\n", cnt, p, q);
                                ret[p][0] = max(ret[p][0], round[cnt]);
                                ret[q][1] = min(ret[q][1], round[cnt]-1);
                            } else {
//                                printf("%d %d %d\n", cnt, q, p);
                                dp[i][q] = 1;
                                ret[p][1] = min(ret[p][1], round[cnt]-1);
                                ret[q][0] = max(ret[q][0], round[cnt]);
                            }
                        }
                    }
                }
            }
        }
//        for (int i = 0; i < n; i++) {
//            printf("[%d] %d\n", i, dp[(1<<n)-1][i]);
//        }
        printf("Case #%d:\n", ++cases);
        
        int rank[16];
        for (int i = 0, sum = 0; i < n; i++) {
            sum += n>>(i+1);
            if ((1<<i) == n)
                rank[i] = 1;
            else
                rank[i] = n - sum + 1;
        }
        for (int i = 0; i < n; i++) {
            int a = ret[i][0];
            int b = ret[i][1];
//            if (ret[i][1] != n) a = max(a, ret[i][1]);
//            if (ret[i][0] != -1) b = min(b, ret[i][0]);
            printf("%d %d\n", rank[a], rank[b]);
        }
    }
    return 0;
}

Morris' Blog

2016 Facebook Hacker Cup Round 1

contents

Facebook Hacker Cup Round 1

A. Coding Contest Creation

B. Laundro, Matt

C. Yachtzee

D. Boomerang Tournament

B. Laundro, Matt

C. Yachtzee

D. Boomerang Tournament