🧩 AtCoder Beginner Contest 409

TayLockJune 7, 2025About 6 min

🧩 AtCoder Beginner Contest 409

# Info & Summary

Date: 2025-06-07
Completion Status: A ✅ / B ✅ / C ❌ / D ✅ / E ✅ / F ❌ / G ❌
Problem Type:

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Math	Prefix Sum	🧠
D	String	Constructive	🧠
E	Tree DP	DFS / Tree DP	🧠🛠️
F	DSU	DSU	🌀
G	Math	Fast Fourier Transform	🌀

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 - Conflict

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    string T, A;
    cin >> N >> T >> A;

    for (int i = 0; i < N; i++)
    {
        if (T[i] == 'o' && A[i] == 'o')
        {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;

    return 0;
}

📌 B - Citation

#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);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    int ans = 0;
    for (int x = 0; x <= N; ++x)
    {
        int count = 0;
        for (int i = 0; i < N; ++i)
        {
            if (A[i] >= x)
                count++;
        }
        if (count >= x)
        {
            ans = x;
        }
    }

    cout << ans << endl;

    return 0;
}

📌 C - Equilateral Triangle

Tips

First, we will find the relative positions of point $1$ and point $i$ for each point $i = 1, 2, ..., N$

Let point $1$ 's coordinate be $0$ , and let coordinate $d$ denote the point $d$ units of distance away clockwise from coordinate $0$

Point $i$ is $(d_1 + d_2 + ... + d_{i - 1})$ units away clockwise from point $1$ , so its coordinate $x_i$ is:

x_i = d_1 + d_2 + ... + d_{i - 1}(\bmod L)

By using cumulative sums, we can find $x_1, x_2, ..., x_N$ in a total of $O(N)$ time

Tips

Three points $a, b, c$ form a equilateral triangle if and only if these three points divide the circumference equally. For example, if $x_a < x_b < x_c$ , this condition is represented as:

x_b = x_a + L/3 \text{and} x_c = x_b + L/3

More formally, three points form a equilateral triangle if and only if:

\exist k (0 \le k < L/3) \text{so that} \lbrace x_a, x_b, x_c \rbrace = \lbrace k, k + L/3, k + 2L/3 \rbrace

Therefore, for a frequency array cnt of $x_1, x_2, ..., x_N$ , the answer is:

answer = \sum_{k = 0}^{L/3 - 1}(cnt[k] \times cnt[k + L/3] \times cnt[k + 2L/3])

#include <bits/stdc++.h>

using namespace std;

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

    int N, L;
    cin >> N >> L;

    vector<int> d(N);
    for (int i = 1; i < N; i++)
    {
        cin >> d[i];

        d[i] = (d[i] + d[i - 1]) % L;
    }

    map<int, long long> cnt;
    for (auto x : d)
    {
        cnt[x]++;
    }

    long long ans = 0;
    if (L % 3 == 0)
    {
        for (int i = 0; i < L / 3; i++)
        {
            ans += (cnt[i] * cnt[i + L / 3] * cnt[i + L / 3 * 2]);
        }
    }

    cout << ans << endl;

    return 0;
}

📌 D - String Rotation

Tips

First, we decide the optimal $l$ :

if $S_l > S_{l + 1}$ , then the operation yields a string lexicographically smaller than $S$
if $S_i \le S_{i + 1}$ for all $1 \le i \le N - 1$ , then no operation makes $S$ lexicographically smaller

If any operation does, the earlier a character is made lexicographically smaller, the smaller the entire string becomes lexicographically, so it is optimal to set $l$ to the smallest $1 \le i \le N - 1$ with $S_i > S_{i + 1}$ . If no such $i$ exists, picking $l = r$ is optimal, and the answer is $S$ itself

Next, we decide the optimal $r$ :

It is better to repeatedly defer $S_l$ as long as the next character to $S_l$ is smaller than $S_l$ itself
Thus, the optimal $r$ is the smallest $l + 1 \le j \le N - 1$ with $S_l < S_{j + 1}$ , or $r = N$ is no such $j$ exists

Details

#include <bits/stdc++.h>

using namespace std;

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

    int T;
    cin >> T;

    while (T--)
    {
        int N;
        string S;
        cin >> N >> S;

        string ans = "";
        char t = '.';
        for (auto c : S)
        {
            if (ans.empty())
            {
                ans += c;
            }
            else if (c >= ans.back())
            {
                if (t < c && t != '#' && t != '.')
                {
                    ans += t;
                    t = '#';
                }
                ans += c;
            }
            else
            {
                if (t == '.')
                {
                    t = ans.back();
                    ans.pop_back();
                    // cout << t << endl;
                    ans += c;
                }
                else
                {
                    if (t < c && t != '#')
                    {
                        ans += t;
                        t = '#';
                    }
                    // cout << t << ' ' << c << endl;
                    ans += c;
                }
            }

            // cout << ans << endl;
        }

        if (t != '#' && t != '.')
        {
            ans += t;
        }

        cout << ans << endl;
    }

    return 0;
}

// Better version
#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int N;
    string S;
    cin >> N >> S;

    int i = 0;
    while (i < N - 1 && S[i] <= S[i + 1])
    {
        i++;
    }

    int j = i;
    while (j < N && S[j] <= S[i])
    {
        j++;
    }

    rotate(S.begin() + i, S.begin() + i + 1, S.begin() + j);

    cout << S << endl;
}

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

    int T;
    cin >> T;

    while (T--)
    {
        solve();
    }

    return 0;
}

📌 E - Pair Annihilation

Tips

Let us consider the contribution of edge $j$ to the answer. Without loss of generality, suppose that vertex $u_j$ is the parent of vertex $v_j$

Let $X_j$ be the sum of $x$ over the vertices in the subtree rooted at vertex $v_j$ . No matter how you operate within this subtree, $|X_j|$ particles with remain. To annihilate these particles, we have to move them via edge $j$ to the outside of the subtree, or introduce particles from outside the subtree to pair with them. In any case, at least $|X_j|$ particles need to be moved along edge $j$ , which contributes by at least $|X_j| \times w_j$ to the answer. Thus, the sought answer is at least:

\sum_{j = 1}^{N - 1}(|X_j| \times w_j)

In fact, there exists a procedure that achieves this lower bound:

We inspect the vertices from the leaves, and if the vertex still contains particles, move it toward the parent

Therefore, the optimal solution is $\sum_{j = 1}^{N - 1}(|X_j| \times w_j)$ . $X_j$ can be found with DFS

Details

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

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

    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < N - 1; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;

        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    long long ans = 0;
    vector<bool> vis(N);

    auto dfs = [&](auto &&self, int u) -> long long
    {
        vis[u] = true;
        long long sum = X[u];

        for (auto &[v, w] : adj[u])
        {
            if (!vis[v])
            {
                long long c = self(self, v);
                ans += abs(c) * w;
                sum += c;
            }
        }

        return sum;
    };

    dfs(dfs, 0);

    cout << ans << endl;

    return 0;
}

// Better version
#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

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

    vector<vector<pair<int, long long>>> adj(N);
    for (int i = 0; i < N - 1; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;

        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    long long ans = 0;

    auto dfs = [&](auto &&self, int u, int p) -> void
    {
        for (auto &[v, w] : adj[u])
        {
            if (v == p)
            {
                continue;
            }

            self(self, v, u);
            X[u] += X[v];
            ans += w * abs(X[v]);
        }
    };

    dfs(dfs, 0, -1);

    cout << ans << endl;

    return 0;
}

📌 F - Connecting Points

Tips

This problem can be made easier to solve by, instead of managing the set of pairs of vertices that are disconnected, the pairs that might be disconnected

Prepare a priority queue pq, so that we can retrieve a vertex pair with the minimum distance

Initially, put all vertex pairs $(u, v)$ $(1 \le u < v \le N)$ to pq

Also, prepare a Disjoint Set Union (DSU) of size $N + Q$ so that we can determine the connectivity of vertices fast

Tips

For query 1, add $(1, n), (2, n), ..., (n - 1, n)$ to pq, where $n$ is the number of vertices in $G$

For query 2, perform the following operation while pq is not empty:

Pop $(u, v) \in pq$ $(u, v) \in pq$ with the minimum distance
- do nothing if vertices $u$ and $v$ are connected
- otherwise, make $u$ and $v$ connected in DSU. Let $k = d(u, v)$ . While the vertex pair $(u', v')$ with the minimum distance in pq is equal to $k$ , pop that and make $u'$ and $v'$ connected in the DSU. After this, print $k$ and determine the procedure. If nothing was printed by query 2, then $G$ has exactly one connected component, so print -1

For query 3, determine if vertices $u$ and $v$ are connected using the DSU

The computational complexity is $O((N + Q)^{2} \log (N + Q))$ , where the bottle neck is inserting $O((N + Q)^{2})$ pairs of vertices to pq

#include <bits/stdc++.h>

using namespace std;

struct DSU
{
    vector<int> f, siz;

    DSU() {}
    DSU(int n)
    {
        init(n);
    }

    void init(int n)
    {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x)
    {
        while (x != f[x])
        {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y)
    {
        return find(x) == find(y);
    }

    bool merge(int x, int y)
    {
        x = find(x);
        y = find(y);

        if (x == y)
        {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;

        return true;
    }

    int size(int x)
    {
        return siz[find(x)];
    }
};

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

    int N, Q;
    cin >> N >> Q;

    const int inf = 2e9 + 1;

    vector<int> X(N), Y(N);
    for (int i = 0; i < N; i++)
    {
        cin >> X[i] >> Y[i];
    }

    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < i; j++)
        {
            pq.push({abs(X[j] - X[i]) + abs(Y[j] - Y[i]), j, i});
        }
    }

    DSU dsu(N + Q);
    while (Q--)
    {
        int o;
        cin >> o;

        if (o == 1)
        {
            int nx, ny;
            cin >> nx >> ny;

            for (int i = 0; i < X.size(); i++)
            {
                pq.push({abs(X[i] - nx) + abs(Y[i] - ny), i, (int)X.size()});
            }

            X.push_back(nx);
            Y.push_back(ny);
        }
        else if (o == 2)
        {
            int mind = inf;

            while (!pq.empty())
            {
                auto [d, i, j] = pq.top();
                if (d > mind)
                {
                    break;
                }
                pq.pop();

                if (dsu.same(i, j))
                {
                    continue;
                }

                mind = d;
                dsu.merge(i, j);
            }

            cout << (mind == inf ? -1 : mind) << endl;
        }
        else
        {
            int u, v;
            cin >> u >> v;
            u--;
            v--;

            cout << (dsu.same(u, v) ? "Yes" : "No") << endl;
        }
    }

    return 0;
}

📌 G - Accumulation of Wealth

Warning

Hard Problems to Tackle Later

// TODO