2017 Facebook Hacker Cup Round 1

contents

  1. 1. Facebook 2017 Hacker Cup Round 1
    1. 1.1. A. Pie Progress
    2. 1.2. B. Fighting the Zombies
    3. 1.3. C. Manic Moving
    4. 1.4. D. Beach Umbrellas
    5. 1.5. Solution A
    6. 1.6. Solution B
    7. 1.7. Solution C
    8. 1.8. Solution D

感謝小夥伴妮可、茵可熱情支援

Facebook 2017 Hacker Cup Round 1

A. Pie Progress

單身狗的 $N$ 天日子中 (娛樂性質翻譯),每天晚餐想要一道點心派搭配。每天早晨決定到當地的餅舖採購,每天一定會生產 $M$ 派,每一種派的價格也有所不同,不用考慮派會壞掉的情況,預先庫存保留著吃。為防止不當商人購買數量過多,當天若購買 $K$ 個派,需要額外支付 $K^2$ 的交易手續費,請問採購花費最少為何。

明顯地,每一天的狀態就是採購了多少個派,得到狀態 $\text{dp}[i][j]$ 表示前 $i$ 天總共採購 $j$ 個餅,轉移過程中要保證數量足夠支付每一天,意即只對 $i \le j$ 進行轉移。每一天窮舉購買的數量,窮舉採購的花費時,勢必要先排序每塊派的價格,每次只挑選前幾個小的,時間複雜度 $O(N^2 M)$

$$\begin{align*} dp[i][j] = \left\{\begin{matrix} 0 && i = 0\;, j = 0\\ \min(dp[i-1][j-k-1] + \text{SumC}[k] + (k+1)^2) && i \le j \\ \infty && \text{otherwise} \end{matrix}\right. \end{align*}$$

B. Fighting the Zombies

在 D&D 遊戲,身為一個魔法師要消滅地圖上的殭屍們。一次操作有兩個步驟,第一步驟圈選任意半徑內的所有殭屍,不改變其相對位置將他們進行轉移,第二步驟選擇長寬為 $R$ 的方形內的所有殭屍,請問一次操作最多可以消滅多少殭屍。

從第二步驟中觀察到消滅的大小是固定的,因此圈選半徑會被約束在 $R$ 內,實際上也不用考慮圓,因為方形被包含在圓裏。最後,我們直接求第一步驟的所有方形情況,將內部的殭屍全部移除後,再窮舉一次方形範圍內部的其他殭屍,所有可能取最大值即可。時間複雜度 $O(N^6)$ 。由於 $N \le 50$ ,六分鐘內是可以容忍的。

C. Manic Moving

搬家公司在 $N$ 個城鎮之間服務,貨車司機打算用最小的油量花費依序完成公司給定 $K$ 個訂單。第 $i$ 名客戶要求從 $S_i$ 地搬到 $D_i$ ,貨車一次可以載運兩名客戶的量。根據訂單順序,先來的就要載貨,同理也要先卸貨。

從題目中發現對於順序要求非常嚴苛,定出每一階段的狀態 $dp[i][j][2]$ 表示完成前 $i$ 個訂單、最後停留位置在 $j$ 地,最後的 [2] 表示前一個階段是否已經卸貨。分成兩種方式討論,時間複雜度 $O(KN)$

D. Beach Umbrellas

$N$ 個人各自帶著半徑 $R_i$ 的降落傘,在海岸進行降落,岸上有 $M$ 個降落點,每個降落點間隔一公尺,請問有多少種降落方式使得他們不會碰撞。

從題目給的說明中,我們發現到左右兩側的降落點比較特別,因為他們的傘的一部份可能會落在 $M$ 點之外,因此考慮窮舉降落在左右側的所有方法數 $N^2$ ,若要計算固定左右兩側的方法數,可以使用重複組合 H 得到 (滿足 $x_1 + x_2 + \cdots + x_n = Y$ 且每個數皆為非負整數的方法數)。然而,這樣計算方法缺少順序,最後補上排列計數 $(N-2)!$

來講講窮舉左右兩側之後怎麼算出方法數

  • 左右兩側分別為 $R_i$$R_j$ 的情況
  • 海岸左寬度增加 $R_i$,同理右寬度增加 $R_j$
  • 如此一來,左右變數的情況就能套用重複組合分配 $N$ 個變數,總和為 $M + R_i + R_j$ ,每個變數至少大於等於 $R_i$

特別地,變數 $M$ 過大。在窮舉所有情況中,組合類型最多 $2R$ 種,而非 $N^2$ 種。計算量多到必須預先建表,每一個組合數 $C^{M+?}_{N}$ ,由於底數是固定的,利用區間滑動在 $O(1)$ 轉換 (需要乘法反元素支援)。預先建表的時間 $O(R)$,窮舉部分 $O(N^2 \log R)$

Solution A

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
#include <bits/stdc++.h>
using namespace std;

int main() {
int testcase, cases = 0;
scanf("%d", &testcase);
while (testcase--) {
int N, M;
scanf("%d %d", &N, &M);
int dp[305][305] = {};
const int INF = 0x3f3f3f3f;
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++)
dp[i][j] = INF;
}

dp[0][0] = 0;
for (int i = 0; i < N; i++) {
int A[305];
for (int j = 0; j < M; j++)
scanf("%d", &A[j]);
sort(A, A+M);
for (int j = 0, sum = 0; j < M; j++) {
sum += A[j];
A[j] = sum;
}
for (int j = i; j < N; j++) {
if (dp[i][j] == INF)
continue;
for (int k = 0; k < M && k+j <= N; k++) {
dp[i+1][j+k+1] = min(dp[i+1][j+k+1], dp[i][j] + A[k] + (k+1)*(k+1));
}
}
for (int j = i+1; j <= N; j++)
dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
}
printf("Case #%d: %d\n", ++cases, dp[N][N]);
}
return 0;
}

Solution B

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
#include <bits/stdc++.h>
using namespace std;

int main() {
int testcase, cases = 0;
scanf("%d", &testcase);
while (testcase--) {
int N, R;
scanf("%d %d", &N, &R);
vector< pair<int, int> > A;
set<int> SX, SY;
for (int i = 0; i < N; i++) {
int x, y;
scanf("%d %d", &x, &y);
A.push_back(make_pair(x, y));
SX.insert(x), SY.insert(y);
}
sort(A.begin(), A.end());

int ret = 0;
for (auto LX : SX) {
for (auto LY : SY) {
int cnt = 0;
vector<int> used(N, 0);
for (int i = 0; i < N; i++) {
if (A[i].first >= LX && A[i].first <= LX+R
&& A[i].second >= LY && A[i].second <= LY+R)
cnt++, used[i] = 1;
}
for (auto TX : SX) {
for (auto TY: SY) {
int dd = 0;
for (int i = 0; i < N; i++) {
if (used[i])
continue;
if (A[i].first >= TX && A[i].first <= TX+R
&& A[i].second >= TY && A[i].second <= TY+R)
dd++;
}
ret = max(ret, dd+cnt);
}
}
}
}
printf("Case #%d: %d\n", ++cases, ret);
}
return 0;
}

Solution C

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
78
79
80
#include <bits/stdc++.h>
using namespace std;

int main() {
int testcase, cases = 0;
scanf("%d", &testcase);
while (testcase--) {
int N, M, K;
scanf("%d %d %d", &N, &M, &K);

long long g[105][105] = {};
const long long INF = 1LL<<60;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++)
g[i][j] = INF;
g[i][i] = 0;
}
for (int i = 0; i < M; i++) {
int A, B;
long long G;
scanf("%d %d %lld", &A, &B, &G);
g[A][B] = min(g[A][B], G);
g[B][A] = min(g[B][A], G);
}

for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++)
g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
}
}

// for (int i = 1; i <= N; i++) {
// for (int j = 1; j <= N; j++)
// printf("%lld ", g[i][j]);
// puts("");
// }

int S[5005], D[5005];
for (int i = 0; i < K; i++)
scanf("%d %d", &S[i], &D[i]);
static long long dp[5005][105][2] = {};
for (int i = 0; i <= K; i++) {
for (int j = 0; j <= N; j++)
dp[i][j][0] = INF, dp[i][j][1] = INF;;
}
dp[0][1][0] = 0;

for (int i = 0; i < K; i++) {
int s1 = S[i], d1 = D[i];
for (int j = 1; j <= N; j++) {
long long cc;
cc = g[j][s1]+g[s1][d1];
dp[i+1][d1][0] = min(dp[i+1][d1][0], dp[i][j][0] + cc);
cc = g[j][s1];
dp[i+1][s1][1] = min(dp[i+1][s1][1], dp[i][j][0] + cc);

if (dp[i][j][1] != INF && i > 0) {
int sP = S[i-1], dP = D[i-1];
cc = g[j][s1]+g[s1][dP];
dp[i+1][dP][1] = min(dp[i+1][dP][1], dp[i][j][1] + cc);
cc = g[j][s1]+g[s1][dP]+g[dP][d1];
dp[i+1][d1][0] = min(dp[i+1][d1][0], dp[i][j][1] + cc);
}
}

// for (int j = 1; j <= N; j++)
// printf("%lld ", dp[i+1][j][0]);
// puts("");
}

long long ret = -1;
for (int i = 1; i <= N; i++) {
if (dp[K][i][0] != INF)
ret = max(ret, dp[K][i][0]);
}
printf("Case #%d: %lld\n", ++cases, ret);
}
return 0;
}

Solution D

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
78
79
80
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007LL;
void exgcd(long long x, long long y, long long &g,
long long &a, long long &b) {
if (y == 0)
g = x, a = 1, b = 0;
else
exgcd(y, x%y, g, b, a), b -= (x/y) * a;
}
long long inverse(long long x, long long p) {
long long g, b, r;
exgcd(x, p, g, r, b);
if (g < 0) r = -r;
return (r%p + p)%p;
}

int main() {
int testcase, cases = 0;
scanf("%d", &testcase);
while (testcase--) {
int N, M, R[2048], S = 0, mxR = 0;
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++)
scanf("%d", &R[i]), S += R[i], mxR = max(mxR, R[i]);
if (N == 1) {
printf("Case #%d: %lld\n", ++cases, M);
continue;
}
fprintf(stderr, "%d %d %d\n", N, S, M);
long long invNplus = 1;
map<long long, long long> C;
{
long long f = 1;
for (int i = 1; i <= N; i++)
f = (f * i)%MOD;
invNplus = inverse(f, MOD);

int l = 1, r = 1;
f = 1;
for (int i = M - 2*S; i <= M - 2*S + 2*mxR; i++) {
int tM = i+N-1;
if (tM < N)
continue;
int L = tM-N+1, R = tM;
if (r < L)
l = r = f = L;
while (l < L)
f = (f*inverse(l, MOD))%MOD, l++;
while (r < R)
r++, f = (f * r)%MOD;
C[tM] = (f * invNplus)%MOD;
// printf("C(%lld %d) = %lld, %lld\n", tM, N, C[tM], f);
}
}
long long ret = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == j)
continue;
int tM = M + R[i] + R[j] - 2*S;
if (tM+N-1 < N)
continue;
// printf("add C(%d %d)\n", tM+N-1, N);
ret += C[tM+N-1];
ret %= MOD;
}
}

long long f = 1;
for (int i = 1; i <= N-2; i++)
f = (f * i)%MOD;
ret = ret * f;
ret %= MOD;
assert(ret >= 0);
printf("Case #%d: %lld\n", ++cases, ret);
}
return 0;
}