SMU Summer 2024 Contest Round 2

Sierpinski Carpet

Problem Statement

Given an integer n, output a matrix of size $3^n \times 3^n$.

Approach

For $n = 0$, the matrix is a single "#". For higher levels, each matrix is composed by placing a smaller matrix in the center and surrounding it with eight copies of the previous level's matrix. This can be simulaetd directly.

Code

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    map<int, vector<string>> mp;
    mp[0] = {"#"};

    auto build = [&](vector<string> s, int m)->vector<string> {
        const int sn = s.size();
        int N = 3;
        for (int i = 1; i < m; i ++) {
            N *= 3;
        }

        vector<string> res(N);
        for (int i = 0; i < N ; i ++) {
            string cs;
            if (i >= N / 3 && i < N / 3 * 2) {
                cs += s[i % sn] + string(sn, '.') + s[i % sn];
            } else {
                cs += s[i % sn] + s[i % sn] + s[i % sn];
            }
            res[i] = cs;
        }

        return res;
    };

    for (int i = 1; i <= n; i ++) {
        mp[i] = build(mp[i - 1], i);
    }

    for (auto &i : mp[n])
        cout << i << '\n';

    return 0;
}

Consecutive

Problem Statement

Given a string, answer Q queries about the number of adjacent pairs of identical characters within a given range [l, r].

Approach

Use prefix sums to calculate the count of such pairs efficiently. Handle boundary conditions carefully.

Code

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    string s;
    cin >> s;

    s = " " + s;
    vector<int> pre(n + 1);
    for (int i = 1; i <= n; i ++) {
        pre[i] = pre[i - 1];
        if (s[i] == s[i + 1]) pre[i] ++;
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << pre[r] - pre[l - 1] - (r < n && s[r] == s[r + 1]) << '\n';
    }

    return 0;
}

Minimum Width

Problem Statement

Given n word lengths, determine the minimum width w that allows all words to fit into at most m lines, considering spacing between words.

Approach

Use binary search on the possible values of w. The check function verifies whether a given width allows fitting all words within m lines.

Code

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<i64> L(n + 2);
    for (int i = 1; i <= n; i ++)
        cin >> L[i];
    L[n + 1] = LLONG_MAX / 2;

    auto check = [&](i64 x) -> bool{
        i64 res = 0, now = 0;
        for (int i = 1; i <= n; i ++) {
            if (x < L[i]) return false;
            now += L[i];
            if (now + 1 + L[i + 1] > x) {
                now = 0;
                res ++;
            } else {
                now ++;
            }
            if (res > m) return false;
        }
        return res <= m;
    };

    i64 l = 0, r = 10000000000000000ll, ans = 1;

    while (l <= r) {
        i64 mid = l + r >> 1;
        if (check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }

    cout << ans << '\n';

    return 0;
}

Printing Machine

Problem Statement

Given n attractions with opening times and durations, determine the maximum number of attractions you can visit, considering a 1 unit rest time after each visit.

Approach

Use a greedy approach with a priority queue to always visit the attraction that closes the earliest, ensuring maximum visits.

Code

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

using PII = pair<i64, i64>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<PII> td(n);
    for (auto &[t, d] : td) {
        cin >> t >> d;
        d += t;
    }

    sort(td.begin(), td.end());

    priority_queue<i64, vector<i64>, greater<>> Q;
    i64 time = 1, ans = 0, pos = 0;

    while (true) {
        if (Q.empty()) {
            if (pos == n) break;
            time = td[pos].first;
            Q.push(td[pos++].second);
        }
        while (pos < n && td[pos].first == time)
            Q.push(td[pos++].second);
        while (Q.size() && Q.top() < time)
            Q.pop();
        if (Q.size()) ans ++, Q.pop();
        time ++;
    }

    cout << ans << '\n';

    return 0;
}

Nearest Black Vertex

Problem Statement

Given a connected undirected graph with n nodes and m edges, determine if there exists a coloring scheme where each node has a specified minimum distance to the nearest black node.

Approach

First, compute distances using BFS. Then, mark nodes as white based on the constraints, and validate the final configuration.

Code

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i ++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<vector<int>> dist(n + 1, vector<int>(n + 1));
    auto bfs = [&](int s) {
        vector<bool> visited(n + 1);
        queue<pair<int, int>> q;
        q.push({s, 0});

        while (!q.empty()) {
            auto [u, len] = q.front();
            q.pop();

            if (visited[u]) continue;
            visited[u] = true;

            dist[s][u] = len;
            for (auto &v : g[u]) {
                if (!visited[v]) {
                    q.push({v, len + 1});
                }
            }
        }
    };

    for (int i = 1; i <= n; i ++)
        bfs(i);

    int k;
    cin >> k;

    vector<bool> color(n + 1, true);
    vector<pair<int, int>> constraints(k);
    for (auto &[p, d] : constraints) {
        cin >> p >> d;
        for (int i = 1; i <= n; i ++)
            if (dist[p][i] < d)
                color[i] = false;
    }

    for (auto &[p, d] : constraints) {
        int min_dist = 1 << 30;
        for (int i = 1; i <= n; i ++)
            if (color[i])
                min_dist = min(min_dist, dist[p][i]);
        if (min_dist != d) {
            cout << "No\n";
            return 0;
        }
    }

    cout << "Yes\n";
    for (int i = 1; i <= n; i ++)
        cout << color[i];

    return 0;
}

Christmas Present 2

Problem Statement

Given a starting point and n children locations, determine the shortest path to deliver gifts to all chidlren in order, with the ability to return home multiple times.

Approach

Use dynamic programming with a sliding window optimization via a deque to minimize the cost of delivering gifts to children in sequence.

Code

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<array<double, 2>> positions(n + 1);
    for (auto &[x, y] : positions)
        cin >> x >> y;

    vector<double> home(n + 1), prefix(n + 1), dp(n + 1);
    for (int i = 1; i <= n; i ++) {
        home[i] = hypot(positions[i][0] - positions[0][0], positions[i][1] - positions[0][1]);
        prefix[i] = prefix[i - 1] + hypot(positions[i][0] - positions[i - 1][0], positions[i][1] - positions[i - 1][1]);
    }

    auto calculate = [&](int j)->double{
        if (!j) return 0;
        return dp[j] + home[j] + home[j + 1] - prefix[j + 1];
    };

    deque<int> dq;
    dq.push_back(0);
    for (int i = 1; i <= n; i ++) {
        dp[i] = prefix[i] + calculate(dq.front());

        while (dq.size() && dq.front() <= i - k)
            dq.pop_front();

        while (dq.size() && calculate(dq.back()) >= calculate(i))
            dq.pop_back();

        dq.push_back(i);
    }

    printf("%.15lf", dp[n] + home[n]);

    return 0;
}