🧩 AtCoder Beginner Contest 401

TayLockApril 12, 2025About 9 min

🧩 AtCoder Beginner Contest 401

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	String/constructive	Case Discussion/Greedy	⭐
E	Graph connectivity	DSU	⭐🔥🛠️
F	Tree	BFS/Sliding Window	⭐🔥🛠️
G	Bipartite matching	Binary Search/Max flow	🌀

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 - Status Code

// TayLock

#include <bits/stdc++.h>

using namespace std;

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

    int s;
    cin >> s;

    if (200 <= s && s <= 299)
    {
        cout << "Success" << endl;
    } else {
        cout << "Failure" << endl;
    }

    return 0;
}

or we can use:

    if (s / 100 == 2)
    {
        cout << "Success" << endl;
    } else {
        cout << "Failure" << endl;
    }

📌 B - Unauthorized

// TayLock

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    int ans = 0;

    bool logout = true;

    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;

        if (s == "login")
        {
            logout = false;
        }
        else if (s == "logout")
        {
            logout = true;
        }
        else if (s == "private" && logout)
        {
            ans += 1;
        }
    }

    cout << ans << endl;

    return 0;
}

📌 C - K-bonacci

// TayLock

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<long long> nums(n + 1, 0);
    long long win = k;
    long long mod = 1e9;
    for (int i = 0; i <= n; i++)
    {
        if (i < k)
        {
            nums[i] = 1;
        }
        else
        {
            nums[i] = win % mod;

            win += nums[i];
            win %= mod;
            win -= nums[i - k];
            win %= mod;
            win = (win + mod) % mod;
        }
    }

    cout << nums[n] << endl;

    return 0;
}

For each $i >= k$ , we have:

A_{i} = A_{i - K} + A_{i - K + 1} + ... + A_{i - 1}

So,

\begin{align*} A_{i + 1} &= A_{i + 1 - K} + A_{i + 1 - K + 1} + ... + A_{i + 1 - 1} \\ &= A_{i - K + 1} + A_{i - K + 2} + ... + A_{i - 1} + A_{i} \\ &= (A_{i} - A_{i - k}) + A_{i} \\ &= 2 * A_{i} - A_{i - k} \\ \end{align*}

replace $i + 1$ with $i$ , we have:

Tips

A_{i} = 2 * A_{i - 1} - A_{i - k - 1}

// Better version

#include <bits/stdc++.h>

using namespace std;

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

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

    constexpr int mod = 1e9;

    vector<int> a(n + 1, 0);
    for (int i = 0; i <= n; i++)
    {
        if (i < k)
        {
            a[i] = 1;
        }
        else if (i == k)
        {
            a[i] = k;
        }
        else
        {
            // A_{i + 1} = 2 * A_{i} - A_{i - k}
            a[i] = (a[i - 1] * 2ll - a[i - k - 1] + mod) % mod;
        }
    }

    cout << a[n] << endl;

    return 0;
}

📌 D - Logical Filling

This is a problem that requires careful case discussions:

First, replace all ? adjacent to o in S with .
If S contain exactly $K$ $K$ o's:
- The only sought string is obtained by replacing all ? with .
Then, we find a way to fill ? to maximize the number of o as much as possible, without making two o's adjacent. This can be done in a greedy fashion from left to right: for each position, we replace ? with o if it is not next to another o
Let $M$ $M$ be the number of o's obtained by this procedure:
- If $M == K$ $M == K$ :
  - If there is an odd number of ?'s, the way to fill it is unique: o.o.o
  - If there is an even number of ?'s, there are two patterns possible, like o.o. and .o.o
  - Therefore, the answer can be obtained by replacing an odd number of consecutive ?'s with alternating o and ., and keeping an even number of consecutive ?'s
- If $M > K$ : The answer is S itself

#include <bits/stdc++.h>

using namespace std;

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

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

    string s;
    cin >> s;

    // replace all `?` adjacent to `o` in `S` with `.`
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'o')
        {
            if (i)
            {
                s[i - 1] = '.';
            }
            if (i + 1 < n)
            {
                s[i + 1] = '.';
            }
        }
    }

    int max = count(s.begin(), s.end(), 'o');
    // `S` contain exactly $K$ `o`'s
    if (k == max)
    {
        // The only sought string is obtained by replacing all `?` with `.`
        replace(s.begin(), s.end(), '?', '.');
        cout << s << endl;
        return 0;
    }

    // we find a way to fill `?` to maximize the number of `o` as much as possible,
    // without making two `o`'s adjacent
    // greedy
    for (int l = 0; l < n; l++)
    {
        if (s[l] == '?')
        {
            int r = l;
            while (r < n && s[r] == '?')
            {
                r++;
            }
            max += (r - l + 1) / 2;
            l = r;
        }
    }

    if (k == max)
    {
        for (int l = 0; l < n; l++)
        {
            if (s[l] == '?')
            {
                int r = l;
                while (r < n && s[r] == '?')
                {
                    r++;
                }
                // If there is an `odd` number of `?`'s, the way to fill it is unique: `o.o.o`
                if ((r - l) % 2 == 1)
                {
                    for (int i = l; i < r; i++)
                    {
                        s[i] = "o."[(i - l) % 2];
                    }
                }
                l = r;
            }
        }
    }

    cout << s << endl;

    return 0;
}

📌 E - Reachable Set

First, let us consider if the condition can be satisfied for a given $k$ :

If one cannot travel from vertex $1$ to vertex $i$ ( $1 < i \le k$ ) without passing through a vertex greater than $k$ , then the condition cannot be satisfied. This is equivalent to whether vertices $1$ and $i$ belongs to the same connected component when all vertices greater than $k$ are removed
Conversely, if there only one connected component after removing vertices greater than $k$ , then the condition can be satisfied

Tips

This can be checked by using a Disjoint Set Union(DSU)

If we add edges to the DSU in ascending order of the larger of the vertices that each edge connects, the connectivity can be checked at an appropriate moment for each $k$

How to find the minimum number of vertices required to be removed:

Any vertices adjacent to a vertex less than or equal to $k$ must be removed. Conversely, all the vertices may be retained

Tips

Such edges can be managed by maintaining the edges in ascending order of the smaller of the vertices that each edge connects, and flagging the larger vertex

The number of vertices to be removed = the number of uninspected vertices adjacent to a vertex seen so far

#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(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);
    }

    DSU dsu(n);

    int connected_components = 0;
    // Whether it is adjacent to any of the vertex inspected so far
    vector<bool> is_connected(n, false);
    // The number of vertices to be removed
    // = the number of uninspected vertices adjacent to a vertex seen so far
    int ans = 0;

    for (int i = 0; i < n; i++)
    {
        // Add a connected component consisting of vertex i
        connected_components++;
        // If it is adjacent to any vertex inspected so far,
        // the number of vertices to be removed decreases by one
        if (is_connected[i])
        {
            ans--;
        }

        for (auto j : adj[i])
        {
            // If it goes to a vertex seen so far, connect it
            // means $j \in (1, ..., i)$
            if (j < i)
            {
                if (!dsu.same(i, j))
                {
                    dsu.merge(i, j);
                    connected_components--;
                }
            }
            else
            {
                // If it has never become adjacent,
                // this is a new vertex that needs to be removed
                if (!is_connected[j])
                {
                    ans++;
                }
                is_connected[j] = true;
            }
        }

        // If the graph is connected after removing all vertices greater than i
        // it can be achieved by removing all vertices to be removed
        if (connected_components == 1)
        {
            cout << ans << endl;
        }
        else
        {
            cout << -1 << endl;
        }
    }

    return 0;
}

Warning

I don't fully understand the code below

And an important note about the problem, which is for each edge $(u_i, v_i)$ :

1 \le u_i < v_i \le N

Use the current node's outgoing edges to count how many new nodes are newly ‘influenced’ or activated (i.e., the ones that need to be deleted), and use the incoming edges to keep track of connected components using DSU

// Better version
#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(0);

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

    // Keeps track of the in-degree for each node
    vector<int> deg(n);
    // Stores the out-edge of i
    vector<vector<int>> adj(n, vector<int>());
    // Stores the in-edge of i
    vector<vector<int>> adj1(n, vector<int>());
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

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

    DSU dsu(n);
    // the number of nodes that have a in-degree greater than zero
    int ans = 0;

    for (int i = 0; i < n; i++)
    {
        // For every in-edge goes into i, merge i and j
        for (auto j : adj1[i])
        {
            dsu.merge(i, j);
        }

        // if in-degree > 0, means node i is no longer an isolated node
        // means node i is now in the range (0, ..., i), should not be removed any more
        if (deg[i] > 0)
        {
            ans--;
        }

        // each out-edge of node i
        for (auto j : adj[i])
        {
            // It is the first time to meet node j
            // means j must be out of the range (0, ..., i)
            // node j should be removed
            if (deg[j] == 0)
            {
                deg[j]++;
                ans++;
            }
        }

        // node from 0 to i should be all in the same connected component
        if (dsu.size(0) != (i + 1))
        {
            cout << -1 << endl;
        }
        else
        {
            cout << ans << endl;
        }
    }

    return 0;
}

📌 F - Add One Edge 3

First, find the diameter of $G_1$ and $G_2$ , denoted by $d_1$ and $d_2$ , respectively

Tips

We can use BFS to find the diameter of the tree

When an edge between vertices $i$ and $j$ is added to the graph, the diameter either:

remains $\max(d_1, d_2)$
becomes the path that contains the new edge, which consists of three parts:
- The path form vertex $i$ to the furthest vertex from vertex $i$ in $G_1$ , let $A_i$ be the distance of this path
- The added edge, the length is $1$
- The path form vertex $j$ to the furthest vertex from vertex $j$ in $G_2$ , let $B_j$ be the distance of this path

Note

Then the diameter for given $i$ and $j$ is represented as:

\max(\max(d_1, d_2), A_i + B_j + 1)

Tips

When $A_i$ and $B_j$ are sorted in ascending order, the range of values $j$ such that $A_i + 1 + B_j \ge \max(d_1, d_2)$ monotonically shrinks, so we can use the sliding window technique

We move the pointer $j$ from $n2$ down to $0$ , trying to find the largest index $j$ such that the condition f1[i] + f2[j] + 1 ≤ dia holds:

For any $j' < j$ , the diameter is $\max(d_1, d_2)$ , we can add 1ll * j * dia to the answer directly
For ans $j \le j'$ $j \leq j^{'}$ , the diameter is $A_i + 1 + B_j$ $A_{i} + 1 + B_{j}$ , we use sliding window to get the answer
- $A_i + 1$ remains fixed, we add this value $(n2 - j)$ times
- $B_j$ varies with $j$ , so we use a running sum sum to accumulate the total of these values
- then the total contribution from these pairs is: 1ll * (f1[i] + 1) * (n2 - j) + sum, which we add to the final answer

This is essentially a sliding window over sorted eccentricities, allowing us to efficiently compute the sum of all valid pairwise distances

// This loop computes the total distance sum between all node pairs
for (int i = 0, j = n2; i < n1; i++)
{
    // j moves from n2 down to 0
    // trying to find the largest j such that f1[i] + f2[j] + 1 ≤ dia
    while (j && f1[i] + f2[j - 1] + 1 > dia)
    {
        j--;
        sum += f2[j];
    }

    // For j elements that fail the check, add: j * dia
    ans += 1ll * j * dia;
    // For the remaining elements, add: (f1[i] + 1) * cnt + sum
    ans += 1ll * (f1[i] + 1) * (n2 - j) + sum;
}

#include <bits/stdc++.h>

using namespace std;

auto solve()
{
    int n;
    cin >> n;

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

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

    vector<int> dis(n, -1);

    // Find the diameter of the tree
    auto bfs = [&](int s)
    {
        queue<int> q;
        q.push(s);

        dis.assign(n, -1);
        dis[s] = 0;

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

            for (auto v : adj[u])
            {
                if (dis[v] == -1)
                {
                    // updates the `dis` vector to store distances from the source
                    dis[v] = dis[u] + 1;
                    q.push(v);
                }
            }
        }
        // Returns the farthest node from the source
        return max_element(dis.begin(), dis.end()) - dis.begin();
    };

    // a is the furthest from 0
    auto a = bfs(0);
    // now b is the furthest from a ⇒ [a, b] is diameter
    auto b = bfs(a);

    // After `b = bfs(a)`: dis[i] means the distance of node `i` to node `a`
    // After `bfs(b)`: we reuse the vertor `dis`, now, dis[i] means the distance of node `i` to node `b`
    vector<int> f(n);
    f = dis;
    bfs(b);

    for (int i = 0; i < n; i++)
    {
        // f[i] now holds the max distance of node `i` to either endpoint of the diameter
        f[i] = max(f[i], dis[i]);
    }

    return pair(f[b], f);
}

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

    // dia1/dia2: current maximum diameter of either tree
    // f1/f2: max distances from diameter ends
    auto [dia1, f1] = solve();
    auto [dia2, f2] = solve();

    long long ans = 0;
    int n1 = f1.size();
    int n2 = f2.size();

    sort(f1.begin(), f1.end());
    sort(f2.begin(), f2.end());

    // When we add a edge (i, j), the diameter either:
    //  - remains $\max(d_1, d_2)$
    //  - becomes the path that contains the new edge
    int dia = max(dia1, dia2);

    long long sum = 0;

    // This loop computes the total distance sum between all node pairs
    for (int i = 0, j = n2; i < n1; i++)
    {
        // j moves from n2 down to 0
        // trying to find the largest j such that f1[i] + f2[j] + 1 ≤ dia
        while (j && f1[i] + f2[j - 1] + 1 > dia)
        {
            j--;
            sum += f2[j];
        }

        // For j elements that fail the check, add: j * dia
        ans += 1ll * j * dia;
        // For the remaining elements, add: (f1[i] + 1) * cnt + sum
        ans += 1ll * (f1[i] + 1) * (n2 - j) + sum;
    }

    cout << ans << endl;

    return 0;
}

📌 G - Push Simultaneously

Warning

Hard Problems to Tackle Later

// TODO