facebook.com/codingcompetitions/hacker-cup/..

Round1 竟然足足有 1 天時間，本來想下午再寫，但早上 6 點睡不著只好爬起來寫了 A 和 B。

Problem A: Consecutive Cuts

ProbA

題意整理

給兩個字串 \(A\)、\(B\)，要對 \(A\) 做 \(K\) 次旋轉，每一次旋轉至少要變動一個字元。問有沒有辦法變成 \(B\)。

題解

首先，可以先用 KMP 在線性時間內算出可以旋轉多少個字元達成，注意到這可能有複數個。

然後根據：字串長度 \(N \geq 2\)，旋轉次數 \(K\) 和移動目標格數 \(R\) 進行討論。

要點：

1. 把 \(N = 2\) 分開來討論。
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

ProbB

題意整理

給 \(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:

1. 一維的話要怎麼算？
2. 二維可以怎麼用一維的結果？

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;
}