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

2016 Facebook Hacker Cup 資格賽

contents

  1. 1. Facebook Hacker Cup 2016 Qualification Round
    1. 1.1. A. Boomerang Constellations
    2. 1.2. B. High Security
    3. 1.3. C. The Price is Correct
    4. 1.4. D. Text Editor
    5. 1.5. Solution
      1. 1.5.1. Sol. A. Boomerang Constellations
      2. 1.5.2. Sol. B. High Security
      3. 1.5.3. Sol. C. The Price is Correct
      4. 1.5.4. Sol. D. Text Editor

好一陣子沒用 C++ 解題，感覺新鮮。嗯 … 

1
$ awk '{ sub("\r$", ""); print }' out.txt > output.txt

Facebook Hacker Cup 2016 Qualification Round

A. Boomerang Constellations

給予在星空下每顆星的座標，找出由三點構成回力鏢樣貌的組合個數，需滿足一點到兩點距離相等。

窮舉所有可能 $\mathcal{O}(N^3)$ 將會 TLE。窮舉回力鏢中心座標 $O$，統計其餘點到 $O$ 的距離，對於相同距離計數，套用組合公式 $C(n, 2)$ 加總，時間複雜度 $\mathcal{O}(n^2 \log n)$

B. High Security

給予只有兩排的長形棋盤狀的營地，雇用最少警衛監視每一塊區域，有些區域會因遮蔽物擋住警衛視線，而警衛只能監視平行兩軸的連續相鄰格子。求最少警衛個數。

第一眼覺得是 flow 可解，但求最少的模型建不太出來 Orz，就決定貪心。在同一行，連續片段上必然放置一個警衛，優先將連續片段總數匹配另一行連續個數恰好為一，剩下的情況再利用連續個數恰好一個的相互匹配。

C. The Price is Correct

參與一場遊戲，獎品價值為 $P$，給訂 $N$ 個正整數序列，挑選連續的序列總和小於等於 $P$ 即可獲得獎品，請問有多少挑選方式。

由於是序列為正整數，前綴和具有單調性，滑動窗口統計方法數只需要 $\mathcal{O}(N)$。最懶得方式是直接二分搜尋 $\mathcal{O}(n \log n)$。

D. Text Editor

從 $N$ 個不同的單字中，打印恰好 $K$ 個輸出在螢幕上，操作有三種 1. 在尾端插入一個字符 2. 刪除字串尾端一個字符 3. 將緩衝區的字串印出來，並且在操作結束後，緩衝區大小為 0。求最少操作個數為何？

第一次遐想，由於要最少操作個數，想必前綴相似的都必須連續，因此先對所有單字排序，接著按照順序 DP。先不考慮操作 3，最後一定恰好為 $K$ 次，只需要考慮插入和刪除操作，維護最後一個在緩衝區為單字 $i$，轉移到下一個單字 $j$ 的成本是 len(Wi) + len(Wj) - LCP[i, j]*2 (刪除前面 $W_i$ 的後綴再加入 $W_j$ 的後綴)，因此要預處理 LCA[i, j]，題目給訂範圍應該不用套用 Trie 或者是 Suffix Array 進行查找，暴力計算即可。定義 DP[i][k] 表示目前打了 $k$ 個單字，最後一個單字恰好為 $i$ 的最少操作次數。在 DP 部分，時間複雜度 $\mathcal{O}(N^2 K)$。

Solution

Sol. A. Boomerang Constellations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2048
long long X[MAXN], Y[MAXN];
int main() {
    int testcase, cases = 0, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        long long ret = 0;
        for (int i = 0; i < n; i++)
            scanf("%lld %lld", &X[i], &Y[i]);
        
        for (int i = 0; i < n; i++) {
            map<long long, int> R;
            for (int j = 0; j < n; j++) {
                if (i == j)
                    continue;
                long long dist = 0;
                dist += (X[i] - X[j])*(X[i] - X[j]);
                dist += (Y[i] - Y[j])*(Y[i] - Y[j]);
                R[dist]++;
            }
            for (auto &p : R)
                ret += p.second * (p.second-1)/2;
        }
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}

Sol. B. High Security

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1024
char g[2][MAXN];
int main() {
    int testcase, cases = 0, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        scanf("%s%s", g[0], g[1]);
        int ret = 0;
        int A[2][MAXN] = {}, B[2][MAXN] = {};
        int used[MAXN] = {};
        int gid = 0;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] != '.') 
                    continue;
                int x = j, cnt = 0;
                while (x < n && g[i][x] == '.')
                    x++, cnt++;
                x = j;
                gid++, ret++;
                while (x < n && g[i][x] == '.')
                    A[i][x] = gid, B[i][x] = cnt, x++;
                j = x;
            }
        }
        
//		for (int i = 0; i < 2; i++) {
//			for (int j = 0; j < n; j++)
//				printf("%d", A[i][j]);
//			puts("");
//		}
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] != '.')
                    continue;
                if (B[i][j] == 1)
                    continue;
                if (used[A[i][j]])
                    continue;
                int x = j;
                while (x < n && g[i][x] == '.') {
                    if (g[!i][x] == '.' && !used[A[!i][x]] && B[!i][x] == 1) {
                        used[A[!i][x]] = 1;
                        ret--;
                        break;
                    }
                    x++;
                }
                while (x < n && g[i][x] == '.')
                    x++;
                j = x;
            }
        }
        
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] != '.')
                    continue;
                if (used[A[i][j]])
                    continue;
                if (B[i][j] == 1) {
                    if (g[!i][j] == '.' && !used[A[!i][j]] && B[!i][j] == 1) {
                        used[A[!i][j]] = 1;
                        ret--;
                    }
                }
            }
        }
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}

Sol. C. The Price is Correct

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 131072;
int N;
long long P, B[MAXN], C[MAXN];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %lld", &N, &P);
        for (int i = 1; i <= N; i++)
            scanf("%lld", &B[i]);
        C[0] = 0;
        for (int i = 1; i <= N; i++)
            C[i] = C[i-1] + B[i];
            
        long long ret = 0;
        for (int i = 1; i <= N; i++) {
            int idx = (int) (lower_bound(C, C + N+1, C[i] - P) - C);
            ret += i - idx;
        }
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}

Sol. D. Text Editor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
const int MAXS = 131072;
const int MAXN = 512;
const long long LLMAX = 1LL<<60;
char s[MAXS];
int common[MAXN][MAXN];
long long dp[MAXN][MAXN];
int main() {
    int testcase, cases = 0;
    int N, K;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &K);
        vector<string> A;
        
        A.push_back("");
        for (int i = 0; i < N; i++) {
            scanf("%s", s);
            A.push_back(s);
        }
        
        sort(A.begin(), A.end());
        N = A.size();
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                int cnt = 0, x = i, y = j;
                for (int k = 0; k < A[x].length() && k < A[y].length(); k++) {
                    if (A[x][k] != A[y][k])
                        break;
                    cnt++;
                }
                common[i][j] = common[j][i] = cnt;
            }
        }
        
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= K; j++)
                dp[i][j] = LLMAX;
        }
        dp[0][0] = 0;
//		for (int i = 0; i < N; i++)
//			printf("%s\n", A[i].c_str());
            
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < K; j++) {
                if (dp[i][j] == LLMAX)
                    continue;
                for (int k = i+1; k < N; k++) {
                    long long t = 0;
                    t += A[k].length() - common[i][k];
                    t += A[i].length() - common[i][k];
                    dp[k][j+1] = min(dp[k][j+1], dp[i][j] + t);
                }
//				printf("%d %d - %lld\n", i, j, dp[i][j]);
            }
        }
        
        long long ret = LLMAX;
        for (int i = 0; i < N; i++)
            ret = min(ret, dp[i][K] + (long long) A[i].length());
        printf("Case #%d: %lld\n", ++cases, ret+K);
    }
    return 0;
}