🧩 AtCoder Beginner Contest 375

TayLockOctober 12, 2024About 4 min

🧩 AtCoder Beginner Contest 375

# Info & Summary

Date: 2024-10-12
Completion Status: A ✅ / B ✅ / C ✅ / D ✅ / E ❌ / F ❌ / G ❌
Problem Type:

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Prefix & Suffix	Prefix Sum & Suffix Sum	⭐🔥
E	DP	DP / Grouped DP	🧠🛠️
F	Shortest Distance	Floyd-Warshall	🧠🌀
G	Shortest Distance	Dijkstra’s algorithm	🌀

Details

`Emoji`	`Label`	`Meaning`
⭐	Important	Problem is strategically useful or has reusable patterns
🔥	Must master	Classic problem or technique that appears often and is worth mastering
⚠️	Reattempt	You attempted but failed; worth reviewing and solving again
🧠	New to me	Introduced a new idea, technique, or pattern you hadn’t seen before
🛠️	Template	You built or improved a code template from solving this problem
🌀	Too hard now	Beyond current ability to understand/solve; revisit after more practice

📌 A - Seats

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    string S;
    cin >> N >> S;

    int ans = 0;

    for (int i = 0; i < N - 2; i++)
    {
        ans += S[i] == '#' && S[i + 1] == '.' && S[i + 2] == '#';
    }

    cout << ans << endl;

    return 0;
}

📌 B - Traveling Takahashi Problem

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    double ans = 0;
    long long x = 0, y = 0;

    for (int i = 0; i < N; i++)
    {
        long long nx, ny;
        cin >> nx >> ny;

        ans += sqrt((x - nx) * (x - nx) + (y - ny) * (y - ny));

        x = nx;
        y = ny;
    }

    ans += sqrt(x * x + y * y);

    cout << fixed << setprecision(20) << ans << endl;

    return 0;
}

📌 C - Spiral Rotation

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    vector<string> grid(N);
    for (int i = 0; i < N; i++)
    {
        cin >> grid[i];
    }

    vector<string> ans(N, string(N, '.'));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int x = i, y = j;

            int t = min({i + 1, j + 1, N - i, N - j});
            t %= 4;

            while (t--)
            {
                tie(x, y) = pair(N - 1 - y, x);
            }
            ans[i][j] = grid[x][y];
        }
    }

    for (int i = 0; i < N; i++)
    {
        cout << ans[i] << endl;
    }

    return 0;
}

📌 D - ABA

#include <bits/stdc++.h>

using namespace std;

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

    string S;
    cin >> S;

    int n = S.size();

    vector<vector<long long>> pre(n, vector<long long>(26, 0));
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < 26; j++)
        {
            pre[i][j] += pre[i - 1][j] + (S[i - 1] - 'A' == j);
        }
    }
    vector<vector<long long>> suf(n, vector<long long>(26, 0));
    for (int i = n - 2; i >= 0; i--)
    {
        for (int j = 0; j < 26; j++)
        {
            suf[i][j] += suf[i + 1][j] + (S[i + 1] - 'A' == j);
        }
    }

    long long res = 0;

    for (int i = 1; i < n - 1; i++)
    {
        for (int j = 0; j < 26; j++)
        {
            res += pre[i][j] * suf[i][j];
        }
    }

    cout << res << endl;

    return 0;
}

Let $dp_{i, x, y, z}$ be the minimum number of people who need to switch their teams so that people $1, 2, ..., i$ are assigned to each team and the strengths of teams 1, 2 and 3 are $x$ , $y$ and $z$ , respectively (if it is impossible, let it $\infin$ )

Naively performing this DP does not finish within the execution time limit. However, considering the sum of strengths of people $1, 2, ..., i$ , it turns out that $z$ is uniquely determined given $i$ , $x$ and $y$ . This allows us not to maintain $z$ as the index

Tips

In short, the answer can be found with DP, where $dp_{i, x, y}$ is the minimum number of people who need to switch their teams so that people $1, 2, ..., i$ are assigned to each team and the strengths of teams 1 and 2 are $x$ and $y$

The sought answer is $dp_{N, \frac{S}{3}, \frac{S}{3}}$ , where $S = \sum_{i = 1}^{N}B_i$

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    vector<long long> A(N), B(N);
    long long sum = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i] >> B[i];

        sum += B[i];
    }

    if (sum % 3 != 0)
    {
        cout << -1 << endl;
        return 0;
    }

    // minimum switches to make team 1 have sum x and team 2 have sum y
    vector<vector<long long>> dp(501, vector<long long>(501, 1e9));
    // No person assigned, 0 total strength in teams 1 and 2, 0 switches
    dp[0][0] = 0;

    for (int i = 0; i < N; i++)
    {
        vector<vector<long long>> ndp(501, vector<long long>(501));

        for (int x = 0; x <= 500; x++)
        {
            for (int y = 0; y <= 500; y++)
            {
                ndp[x][y] = 1e9;

                // Assign to team 1
                if (x >= B[i])
                {
                    ndp[x][y] = min(ndp[x][y], dp[x - B[i]][y] + (A[i] != 1));
                }
                // Assign to team 2
                if (y >= B[i])
                {
                    ndp[x][y] = min(ndp[x][y], dp[x][y - B[i]] + (A[i] != 2));
                }
                // Assign to team 3
                ndp[x][y] = min(ndp[x][y], dp[x][y] + (A[i] != 3));
            }
        }

        dp = ndp;
    }

    cout << (dp[sum / 3][sum / 3] == 1e9 ? -1 : dp[sum / 3][sum / 3]) << endl;

    return 0;
}

📌 F - Road Blocked

Tips

By processing the queries in reverse order, we now how to handle edge-adding queries instead of removal queries

If there is no edge-adding queries, one can do precalculation of Warshall-Floyd algorithm in a total of $O(N^3)$ time to answer each query in $O(1)$ time

Tips

When an edge is added between vertices $u$ and $v$ , the shortest path from vertex $u$ to vertex $v$ is always one of the following, depending on whether the new edge should be used or not:

the original path
the path consisting of a shortest path from $x$ to $u$ , the edge from $u$ to $v$ , and the shortest path from $v$ to $y$ , in this order
the path consisting of a shortest path from $x$ to $v$ , the edge from $v$ to $u$ , and the shortest path from $u$ to $y$ , in this order

If we know the original all-pair shortest distances, this can be checked in $O(1)$ time, for a total of $O(N^2)$ time to update the all-pair shortest distances

// TODO

📌 G - Road Blocked 2

Warning

Hard Problems to Tackle Later

// TODO