🧩 AtCoder Beginner Contest 399

TayLockMarch 29, 2025About 6 min

🧩 AtCoder Beginner Contest 399

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
C	Graph	DFS/BFS/DSU	⭐🛠️🔥
D	Pairwise Pattern Check with Indexed Constraints	Simulation	⭐
E	String/Graph	DSU	🧠🌀⭐
F	Algebraic Dynamic Programming	DP/Prefix Sum	🌀
G	Tree	Matroid	🧠🌀

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 - Hamming Distance

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    string s, t;
    cin >> n >> s >> t;

    int ans = 0;
    for (int i = 0; i< n; i++)
    {
        ans += (s[i] != t[i]);
    }

    cout << ans << endl;

    return 0;
}

📌 B - Ranking with Ties

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<int> idx(n);
    vector<int> ans(n);
    int r = 1;
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int j)
         { return p[i] > p[j]; });

    for (int i = 0; i < n; i++)
    {
        if (i == 0 || p[idx[i]] != p[idx[i - 1]])
        {
            r = i + 1;
        }
        ans[idx[i]] = r;
    }

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

    return 0;
}

Suppose that the given graph consists of $K$ connected components $C_1, C_2, ..., C_K$ . Then for each $C_i$ we can retain $|C_i| - 1$ edges, which is the maximum possible. Together with $\sum_{i = 1}^{K}(C_i) = N$ , the maximum number of edges that can be retained is:

\sum_{i = 1}^{K}(|C_i| - 1) = \sum_{i = 1}^{K}(|C_i|) - \sum_{i = 1}^{K}(1) = N - K

Therefore, the minimum number of edges required for the original graph to become a forest is:

M - (N - K)

Thus, the problem can be solved if we can find the number of connected components $K$

Tips

The number of connected components $K$ can be counted fast by graph searching algorithns like DFS or BFS, or DSU

BFS version

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<vector<int>> adj(n, vector<int>());
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<bool> vis(n, false);
    queue<int> q;

    int connected_count = 0;

    for (int i = 0; i < n; i++)
    {
        if (vis[i])
        {
            continue;
        }

        connected_count++;
        vis[i] = true;
        q.push(i);

        while (!q.empty())
        {
            int u = q.front();
            q.pop();

            for (auto v : adj[u])
            {
                if (vis[v])
                {
                    continue;
                }

                vis[v] = true;
                q.push(v);
            }
        }
    }

    cout << (m - (n - connected_count)) << endl;

    return 0;
}

DFS + std::function version

Slightly slower (due to internal indirection and type erasure)

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<vector<int>> adj(n, vector<int>());
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> vis(n, false);

    function<void(int)> dfs = [&](int u)
    {
        vis[u] = true;

        for (auto v : adj[u])
        {
            if (!vis[v])
            {
                dfs(v);
            }
        }
    };

    int connected_count = 0;
    for (int i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            connected_count++;
            dfs(i);
        }
    }

    cout << (m - (n - connected_count)) << endl;

    return 0;
}

DFS + auto &self version

Faster (no indirection or type erasure)

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<vector<int>> adj(n, vector<int>());
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> vis(n, false);

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

        for (auto v : adj[u])
        {
            if (!vis[v])
            {
                self(self, v);
            }
        }
    };

    int connected_count = 0;
    for (int i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            connected_count++;
            dfs(dfs, i);
        }
    }

    cout << (m - (n - connected_count)) << endl;

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

struct DSU
{
    vector<int> p, siz;

    DSU(int n) : p(n), siz(n, 1)
    {
        iota(p.begin(), p.end(), 0);
    }

    int find(int x)
    {
        return p[x] == x ? x : p[x] = find(p[x]);
    }

    bool is_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];
        p[y] = x;

        return true;
    }

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

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

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

    DSU dsu(n);
    int connected_count = n;
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        if (dsu.merge(u, v))
        {
            connected_count--;
        }
    }

    cout << (m - (n - connected_count)) << endl;

    return 0;
}

📌 D - Switch Seats

Tips

How is $(a, b)$ placed in the sequence if it is satisfies the conditions in the problem statements?

In fact, it turn out that it is limited to:

..., a, b, ..., a, b, ...

..., a, b, ..., b, a, ...

Let $p_{a, 1}$ , $p_{a, 2}$ be the positions of $a$ in $A$ , and $p_{b, 1}$ , $p_{b, 2}$ be of $b$

Let $v = (v_1, v_2, v_3, v_4)$ be the sequence $(p_{a, 1}, p_{a, 2}, p_{b, 1}, p_{b, 2})$ sorted in ascending order, then $v_1 + 1 = v_2$ and $v_3 + 1 = v_4$

If $(a, b)$ is applicable, then their occurrences should be adjacent too

Thus, we can count all the conforming pairs $(a, b)$ by checking the criteria above for all $(A_i, A_{i + 1})$ with $1 \le i \le 2N - 1$ , $A_i \neq A_{i + 1}$

#include <bits/stdc++.h>

using namespace std;

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

    int t;
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;

        vector<int> A(2 * n);
        for (int i = 0; i < 2 * n; i++)
        {
            cin >> A[i];
        }

        vector<vector<int>> pos(n + 1);
        for (int i = 0; i < 2 * n; i++)
        {
            pos[A[i]].push_back(i);
        }

        set<pair<int, int>> s;
        for (int i = 0; i + 1 < 2 * n; i++)
        {
            int a = A[i], b = A[i + 1];

            if (pos[a][0] + 1 == pos[a][1] || pos[b][0] + 1 == pos[b][1])
            {
                continue;
            }

            vector<int> v = {pos[a][0], pos[a][1], pos[b][0], pos[b][1]};
            sort(v.begin(), v.end());

            if (v[0] + 1 == v[1] && v[2] + 1 == v[3])
            {
                s.emplace(minmax(a, b));
            }
        }

        cout << s.size() << endl;
    }

    return 0;
}

📌 E - Replace

Warning

Hard Problems to Tackle Later

📌 F - Range Power Sum

Tips

Rephrase the problem statement as follows:

There are $N$ boxes arranged from left to right, box $i$ contains $A_i$ balls
How many ways are there to perform the following proceduce?
- Place two indistinguishable partitions between boxes in the sequence
- For each $i = 1, 2, ..., K$ , choose one ball in a box between the two partitions, and put a sticker labeled $i$ . A single ball may have multiple stickers
  :::

Let us inspect the ball from the left, and determine the position of partitions while putting stickers. We will perform the following DP:

dp[i][j][k]: the number of ways to inspect the first $i$ boxes, while inserting $j$ ( $0 \le j \le 2$ ) partitions and putting $k$ ( $0 \le k \le K$ ) stickers

Tips

The transitions are as follows:

$dp[i][j + 1][k] += dp[i][j][k]$ : corresponds to placing a partition
$dp[i + 1][j][k] += dp[i][j][k]$ : advancing to the next box without putting a sticker
$dp[i + 1][1][k + p] += dp[i][1][k] \cdot () \cdot A_{i}^{p}$ $d p [i + 1] [1] [k + p] + = d p [i] [1] [k] \cdot () \cdot A_{i}^{p}$ , when $1 \le p \le K - k$ $1 \leq p \leq K - k$ : corresponds to putting a sticker on the ball in the box currently inspecting, where:
- the variable $c$ corresponds to the number of stickers to put
- the coefficient $$ to the number of ways to choose $p$ stickers out of $K - k$ stickers not attached yet
- the coefficient $A_i^p$ to the number of ways to choose balls to put sticker on for each of the $p$ chosen sticker

Note

Note that the third transition is only limited to $j = 1$ because one can put a sticker on a ball only when it is in a box between the partitions

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

long long mod_pow(long long base, long long exp)
{
    long long result = 1;
    while (exp > 0)
    {
        if (exp % 2 == 1)
        {
            result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }
    return result;
}

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

    int N, K;
    cin >> N >> K;

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

    vector<long long> S(N + 1, 0);
    for (int i = 1; i <= N; i++)
    {
        S[i] = (S[i - 1] + A[i - 1]) % MOD;
    }

    vector<vector<long long>> sum(K + 1, vector<long long>(N + 1, 0));
    for (int m = 0; m <= K; m++)
    {
        sum[m][0] = 0;
        for (int i = 1; i <= N; i++)
        {
            sum[m][i] = (sum[m][i - 1] + mod_pow(S[i - 1], m)) % MOD;
        }
    }

    vector<vector<long long>> C(K + 1, vector<long long>(K + 1, 0));
    C[0][0] = 1;
    for (int n = 1; n <= K; n++)
    {
        C[n][0] = 1;
        for (int k = 1; k <= n; k++)
        {
            C[n][k] = (C[n - 1][k - 1] + C[n - 1][k]) % MOD;
        }
    }

    vector<long long> dp(K + 1, 0);
    long long total = 0;
    for (int r = 1; r <= N; r++)
    {
        for (int k = 0; k <= K; k++)
        {
            dp[k] = 0;
            for (int m = 0; m <= k; m++)
            {
                long long term = (C[k][m] * mod_pow(S[r], k - m)) % MOD;
                term = (term * mod_pow(-1, m)) % MOD;
                term = (term * sum[m][r]) % MOD;
                dp[k] = (dp[k] + term) % MOD;
            }
        }
        total = (total + dp[K]) % MOD;
    }

    cout << (total + MOD) % MOD << endl;
    return 0;
}

📌 G - Colorful Spanning Tree

Warning

Hard Problems to Tackle Later