Skip to main content

🧩 AtCoder Beginner Contest 404

TayLockMay 3, 2025About 6 minAlgorithmAtCoder Beginner ContestDPBitmask

🧩 AtCoder Beginner Contest 404

# Info & Summary

  • Date: 2025-05-03
  • Completion Status: A ✅ / B ✅ / C ✅ / D ✅ / E ❌ / F ❌ / G ❌
  • Problem Type:
ProblemType(s)Data Structure / Algo🔥 Key Insight / Mark
Dbitmask, DPbitmask / DP⭐🔥
EMinimum number of operationsDP🧠🔥
FDPDP🌀
GLinear ProgrammingLinear Programming🌀
Details
EmojiLabelMeaning
⭐ImportantProblem is strategically useful or has reusable patterns
🔥Must masterClassic problem or technique that appears often and is worth mastering
⚠️ReattemptYou attempted but failed; worth reviewing and solving again
🧠New to meIntroduced a new idea, technique, or pattern you hadn’t seen before
🛠️TemplateYou built or improved a code template from solving this problem
🌀Too hard nowBeyond current ability to understand/solve; revisit after more practice

📌 A - Not Found

404A
404A
#include <bits/stdc++.h>

using namespace std;

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

    string S;
    cin >> S;

    vector<int> cnt(26);
    for (auto c : S)
    {
        cnt[c - 'a']++;
    }

    for (int i = 0; i < 26; i++)
    {
        if (cnt[i] == 0)
        {
            cout << char('a' + i) << endl;
            return 0;
        }
    }

    return 0;
}

📌 B - Grid Rotation

404B
404B
#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

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

    auto roate = [&]()
    {
        vector<string> A(N, string(N, '.'));
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                A[j][N - 1 - i] = S[i][j];
            }
        }

        S = A;
    };

    int ans = 1e9;
    for (int k = 0; k < 4; k++)
    {
        int cnt = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                cnt += S[i][j] != T[i][j];
            }
        }

        ans = min(ans, cnt + k);

        roate();
    }

    cout << ans << endl;

    return 0;
}

📌 C - Cycle Graph?

404C
404C

Tips

The given graph is a cycle graph if and only if the following two conditions are met:

  • The degree of every vertex is 2
  • The graph is connected

This can be determined using DFS (Depth-First Search), BFS (Breadth-First Search), or DSU (Disjoint Set Union)

#include <bits/stdc++.h>

using namespace std;

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

    int N, M;
    cin >> N >> M;

    if (M != N)
    {
        cout << "No" << endl;
        return 0;
    }

    vector<vector<int>> adj(N);
    vector<int> deg(N, 0);
    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);

        deg[u]++;
        deg[v]++;
    }

    for (int i = 0; i < N; i++)
    {
        if (deg[i] != 2)
        {
            cout << "No" << endl;
            return 0;
        }
    }

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

    q.push(0);
    vis[0] = true;

    int cnt = 1;

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

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

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

    cout << (cnt == N ? "Yes" : "No") << endl;

    return 0;
}

📌 D - Goin' to the Zoo

404D
404D

Tips

This is a straight-up brute‐force over all ways of visiting each zoo 0, 1 or 2 times (since visiting any zoo more than twice never helps)

Details
#include <bits/stdc++.h>

using namespace std;

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

    int N, M;
    cin >> N >> M;

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

    vector<vector<int>> zoo(M);
    for (int i = 0; i < M; i++)
    {
        int k;
        cin >> k;
        zoo[i].resize(k);

        for (int j = 0; j < k; j++)
        {
            cin >> zoo[i][j];
            zoo[i][j]--;
        }
    }

    long long ans = 1e18;
    vector<int> cnt(N);

    auto dfs = [&](auto &&self, int i) -> void
    {
        if (i == N)
        {
            for (int j = 0; j < M; j++)
            {
                int count = 0;
                for (auto z : zoo[j])
                {
                    count += cnt[z];
                }
                if (count < 2)
                {
                    return;
                }
            }

            long long cost = 0;
            for (int j = 0; j < N; j++)
            {
                cost += C[j] * cnt[j];
            }

            ans = min(ans, cost);
            return;
        }

        cnt[i] = 0;
        self(self, i + 1);

        cnt[i] = 1;
        self(self, i + 1);

        cnt[i] = 2;
        self(self, i + 1);
    };

    dfs(dfs, 0);

    cout << ans << endl;

    return 0;
}

Why base-3?

We need to let each zoo be visited 0,1,20, 1, 2 times—exactly three possibilities—so it’s natural to encode a full assignment (t0,t1,...,tN−1)(t_0, t_1, ..., t_{N - 1}) as a single integer in [0,3N)[0, 3^N) by writing it in base 3:

mask=t0⋅30+t1⋅31+...+tN−1⋅3N−1 mask = t_0 \cdot 3^0 + t_1 \cdot 3^1 + ... + t_{N - 1} \cdot 3 ^{N - 1}

Extracting digit tit_i:

  • Dividing maskmask by 3i3^i shifts you right ii digits in base 33, so the old ii-th digit moves into the units place
  • Taking that result %3\% 3, then picks off exactly that digit (now in the ones place), giving you tit_i
// Better version

#include <bits/stdc++.h>

using namespace std;

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

    int N, M;
    cin >> N >> M;

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

    // Precompute powers of 3
    vector<int> pw(N + 1);
    pw[0] = 1;
    for (int i = 1; i <= N; i++)
    {
        pw[i] = pw[i - 1] * 3;
    }

    vector<vector<int>> A(N);
    for (int i = 0; i < M; i++)
    {
        int k;
        cin >> k;

        for (int j = 0; j < k; j++)
        {
            int x;
            cin >> x;
            x--;

            A[x].push_back(i);
        }
    }

    long long ans = 1E18;
    for (int mask = 0; mask < pw[N]; mask++)
    {
        std::vector<int> cnt(M);
        long long cost = 0;
        for (int i = 0; i < N; i++)
        {
            // how many times we visit zoo i
            int t = (mask / pw[i]) % 3;
            cost += C[i] * t;
            for (int _ = 0; _ < t; _++)
            {
                for (auto a : A[i])
                {
                    cnt[a]++;
                }
            }
        }

        // check that every species is seen at least twice
        if (*std::min_element(cnt.begin(), cnt.end()) >= 2)
        {
            ans = std::min(ans, cost);
        }
    }

    cout << ans << endl;

    return 0;
}

📌 E - Bowls and Beans

404E
404E

Tips

First, we may assume that we always choose the rightmost bowl containing one or more beans

  • if we want to move beans from a bowl and then from another bowl to its right, we may freely swap the order of these operations

Also, when moving beans, we do not need to distribute them to multiple bowls

  • one can freely pick an operation that distributes beans to multiple bowls, and replace it with an operation of moving all the beans into one of the bowls

Tips

First, let us consider how many operations are required to move the leftmost beans to bowl
00. Regarding moving beans, we have the following property:

  • Consider moving a bean consecutively. If we start from bowl rr and perform operations kk times, the bowls that the bean may end up forms a segment
  • More precisely, there exists ll such that the bean may belong to one of bowl l,l+1,...,rl, l + 1, ..., r

Tips

When the leftmost beans are in bowl xx, one can find the minimum number of operations to move them to bowl 00 as follows:

  • Initially, the segment in which the beans may exist is [x,x][x, x]
  • If the segment in which the beans may exist is [l,r][l, r] after kk moves, the segment in which the beans may exist after (k+1)(k + 1) moves is [min⁡i=lr(i−Ci),r][\min_{i = l}^{r}(i - C_i), r]
  • Repeat this until the beans can reach bowl 00

Tips

How can we consider the number of operations required for the other beans?

  • In this case, it is sufficient to move the first bowl to its left with a bean in it, because, once the beans reach the next bowl to the left with a bean, one can consider the beans together as one bean to forget about the beans
Details
#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;
    vector<int> c(n), a(n);
    for (int i = 1; i < n; i++)
    {
        cin >> c[i];
    }
    for (int i = 1; i < n; i++)
    {
        cin >> a[i];
    }

    int ans = 0;
    // the leftmost bowl index we have already “covered” with previous operations
    int pre = 0;

    // process each bowl i that has a bean
    for (int x = 1; x < n; x++)
    {
        // no bean → nothing to do
        if (!a[x])
        {
            continue;
        }

        // we start with the range [l, r] = [x, x]
        int l = x, r = x;

        // we need this range to expand left until it reaches at least pre (so the new bean's path
        // merges into the coverage we already have)
        while (pre < l)
        {
            // perform one more operation (one BFS‐layer)
            ans++;

            // after one operation at every bowl in [l, r], they’ll each push back c[j] steps:
            // so this range extends left to min(j–c[j]) among j∈[l, r]
            int nl = l;
            for (int i = l; i <= r; i++)
            {
                nl = min(nl, i - c[i]);
            }

            l = nl;
        }

        // now [l, r] reaches or passes pre, so this bean’s path is fully covered by res ops
        pre = x;
    }

    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> c(n + 1), a(n + 1);
    for (int i = 1; i < n; i++)
    {
        cin >> c[i];
    }
    for (int i = 1; i < n; i++)
    {
        cin >> a[i];
    }
    // add a dummy “bowl N” that can always reach back to 0
    c[n] = n;

    // dp[j] = minimum number of operations needed so that
    // all beans in bowls ≤ j have been moved into bowl 0 or
    // into some bowl ≤ j
    const int INF = 1e9;
    vector<int> dp(n + 1, INF);
    dp[0] = 0;

    // Forward DP: from each “covered” point i, we try one more operation
    // at some bowl j>i that can pull from i (i.e. j−C[j] ≤ i).
    // Once we hit another bean at j, we stop – that bean will be handled
    // as soon as we reach dp[j].
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            // Can a single op at j cover “back” to i?
            if (j - c[j] <= i)
            {
                dp[j] = min(dp[j], dp[i] + 1);
            }

            // as soon as j has a real bean (A[j]==1), break,
            // because that bean must be “picked up” by dp[j] itself
            if (a[j] == 1)
            {
                break;
            }
        }
    }

    // dp[N] is the number of operations needed to also “collect” the dummy bowl N
    // subtract 1 because the last dummy‐collection isn’t a real bean-pickup
    cout << dp[n] - 1 << endl;

    return 0;
}

📌 F - Lost and Pound

404F
404F

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Specified Range Sums

404G
404G

Warning

Hard Problems to Tackle Later

// TODO
Default footer
Copyright © 2025 TayLock