Facebook 2022 Hacker Cup Round1
facebook.com/codingcompetitions/hacker-cup/..
Round1 竟然足足有 1 天時間,本來想下午再寫,但早上 6 點睡不著只好爬起來寫了 A 和 B。
Problem A: Consecutive Cuts
題意整理
給兩個字串 \(A\)、\(B\),要對 \(A\) 做 \(K\) 次旋轉,每一次旋轉至少要變動一個字元。問有沒有辦法變成 \(B\)。
題解
首先,可以先用 KMP 在線性時間內算出可以旋轉多少個字元達成,注意到這可能有複數個。
然後根據:字串長度 \(N \geq 2\),旋轉次數 \(K\) 和移動目標格數 \(R\) 進行討論。
要點:
- 把 \(N = 2\) 分開來討論。
- 對於 \( N > 2 \)
- \(K = 0\): \(R\) 必須是 \(0\)
- \(K = 1\): \(R\) 必須不是 \(0\)
- \( K \geq 2 \): 一定可以。
Code
#include <bits/stdc++.h>
using namespace std;
// Morris Pratt: Find all mathing positions
template <typename T>
vector<int> mpMatching(const vector<T>& t, const vector<T>& p) {
vector<int> borderFunc(p.size(), -1);
for (int i = 1, j = borderFunc[0]; i < p.size(); ++i) {
while (j >= 0 && p[j + 1] != p[i]) {
j = borderFunc[j];
}
if (p[j + 1] == p[i]) {
++j;
}
borderFunc[i] = j;
}
vector<int> posMatching;
for (int i = 0, j = -1; i < t.size(); ++i) {
while (j >= 0 && p[j + 1] != t[i]) {
j = borderFunc[j];
}
if (p[j + 1] == t[i]) {
++j;
}
if (j == p.size() - 1) {
posMatching.push_back(i - p.size() + 1);
j = borderFunc[j];
}
}
return posMatching;
}
// input: n >= 2, r in [1, n-1]
bool canMatch(int n, int k, int r) {
if (n == 2) {
return ((k % 2) == (r % 2));
}
// n >= 3
if (k == 0) {
return r == 0;
} else if (k == 1) {
return r > 0;
} else {
return true;
}
}
// input: n >= 2, rs in [1, n-1]
template <typename T>
bool canMatchs(int n, int k, const T& rs) {
for (int r : rs) {
if (canMatch(n, k, r)) {
return true;
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (int lt = 1; lt <= T; ++lt) {
int N, K;
cin >> N >> K;
vector<int> A(N), B(N);
for (auto& a : A) {
cin >> a;
}
for (auto& b : B) {
cin >> b;
}
vector<int> B2 = B;
B2.insert(B2.end(), B.begin(), B.end());
auto poss = mpMatching(B2, A);
set<int> reducePoss;
for (int pos : poss) {
reducePoss.insert(pos % N);
}
cout << "Case #" << lt << ": "
<< (canMatchs(N, K, reducePoss) ? "YES" : "NO") << endl;
}
return 0;
}
Problem B: Watering Well
題意整理
給 \(P_i\), \(Q_j\) 兩群 2D 平面上的點集合 ,\(1 \leq i \leq N\),\(1 \leq j \leq M\)。求:
$$ \sum_i \sum_j \Vert \,P_i - Q_i \Vert ^ 2 $$
題解
主要是數學算式操作,這裡就只留 Hint 了。
HINT:
- 一維的話要怎麼算?
- 二維可以怎麼用一維的結果?
Code
#include <bits/stdc++.h>
using namespace std;
const int64_t P = 1e9 + 7;
// Calculate: sig x
inline int64_t sum1(const vector<int64_t> xs) {
int64_t r = 0;
for (int64_t x : xs) {
r += x;
r %= P;
}
return r;
}
// Calculate: sig x^2
inline int64_t sum2(const vector<int64_t> xs) {
int64_t r = 0;
for (int64_t x : xs) {
r += (x * x) % P;
r %= P;
}
return r;
}
// Calculate: sig sig (xi-yj)^2
int64_t dist(const vector<int64_t>& xs, const vector<int64_t>& ys) {
int64_t ret = ((int64_t(ys.size()) * sum2(xs)) % P) +
((int64_t(xs.size()) * sum2(ys)) % P) -
((int64_t(2) * sum1(xs) * sum1(ys)) % P);
ret %= P;
ret += P;
ret %= P;
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (int lt = 1; lt <= T; ++lt) {
int N;
cin >> N;
vector<int64_t> A(N), B(N);
for (int lx = 0; lx < N; ++lx) {
cin >> A[lx] >> B[lx];
}
int Q;
cin >> Q;
vector<int64_t> X(Q), Y(Q);
for (int lx = 0; lx < Q; ++lx) {
cin >> X[lx] >> Y[lx];
}
int64_t ans = (dist(A, X) + dist(B, Y)) % P;
cout << "Case #" << lt << ": " << ans << endl;
}
return 0;
}