🧩 AtCoder Beginner Contest 405

TayLockMay 10, 2025About 3 min

🧩 AtCoder Beginner Contest 405

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Multi-source BFS	Multi-source BFS	⭐🔥
E	Combination	Combination	🧠🛠️🌀
F	Interval Tree	Lowest Common Ancestor	🌀
G	square-root decomposition	Mo’s algorithm / Segment Tree	🌀

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 - Is it rated?

#include <bits/stdc++.h>

using namespace std;

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

    int R, X;
    cin >> R >> X;

    if (X == 1)
    {
        cout << (1600 <= R && R <= 2999 ? "Yes" : "No") << endl;
    } else {
        cout << (1200 <= R && R <= 2399 ? "Yes" : "No") << endl;
    }

    return 0;
}

📌 B - Not All

#include <bits/stdc++.h>

using namespace std;

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

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

    int ans = N;

    set<int> st;
    for (int i = 0; i < N; i++)
    {
        int a;
        cin >> a;

        if (st.size() < M)
        {
            ans--;
            st.insert(a);

            if (st.size() == M)
            {
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

📌 C - Sum of Product

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    long long sum = 0;
    long long ans = 0;

    for (int i = 0; i < N; i++)
    {
        long long a;
        cin >> a;

        ans += a * sum;

        sum += a;
    }

    cout << ans << endl;

    return 0;
}

📌 D - Escape Route

#include <bits/stdc++.h>

using namespace std;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const char dir[] = {'^', 'v', '<', '>'};

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

    int H, W;
    cin >> H >> W;

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

    queue<tuple<int, int>> q;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            if (grid[i][j] == 'E')
            {
                q.push({i, j});
            }
        }
    }

    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();

        for (int k = 0; k < 4; k++)
        {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (nx < 0 || ny < 0 || nx >= H || ny >= W)
            {
                continue;
            }
            if (grid[nx][ny] != '.')
            {
                continue;
            }

            grid[nx][ny] = dir[k];
            q.push({nx, ny});
        }
    }

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

    return 0;
}

📌 E - Fruit Lineup

Let us count how many ways are there to arrange the fruits to the left and right of the grape, when there are exactly $i$ bananas $(0 \le i \le C)$ to the left of the leftmost grape

(1) to the left of the leftmost grape

The fruits to the left of the leftmost grape are:

$A$ apples, $B$ oranges, and $i$ bananas

Since an apple should come always to the left of a banana, the number of arrangements $(A + B + i)$ fruits turns out to be equal to:

the number of ways to insert oranges to the sequence of $(A + i)$ apples and bananas

Therefore, the sought count is:

\binom{A + B + i}{B}

(2) to the right of the leftmost grape

The fruit to the right of the leftmost grape are:

$(C - i)$ bananas and $(D - 1)$ grape

We may arrange then in arbitrary order, so the sought count is:

\binom{D - 1 + C - i}{D - 1}

By (1) and (2), the number of ways to arrange fruits when there are exactly $i$ bananas $(0 \le i \le C)$ to the left of the leftmost banana is:

\binom{A + B + i}{B} \binom{D - 1 + C - i}{D - 1}

The answer to the original problem is the sum of this value over $i = 0, 1, ..., C$ , that is:

\sum_{i = 0}^{C}\binom{A + B + i}{B} \binom{D - 1 + C - i}{D - 1}

This can be computed in $O(A + B + C + D)$ time after appropriate precalculation of factorials the their inverses

#include <bits/stdc++.h>

using namespace std;

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

    long long A, B, C, D;
    cin >> A >> B >> C >> D;

    const long long mod = 998244353;
    vector<long long> fact, invfact;

    auto modinv = [&](long long a, long long mod)
    {
        if (a < 0)
        {
            a %= mod;
        }
        if (a < 0)
        {
            a += mod;
        }
        if (a >= mod)
        {
            a %= mod;
        }

        assert(a);
        long long x = 0, y = 1, u = 1, v = 0, b = mod;
        while (b != 0)
        {
            long long q = a / b;
            a %= b;
            swap(a, b);
            u -= q * x;
            swap(u, x);
            v -= q * y;
            swap(y, v);
        }
        if (u > 0)
        {
            return u;
        }
        else
        {
            return u + mod;
        }
    };

    auto set_fact = [&](long long n, long long mod)
    {
        fact.resize(n + 1, 1);
        invfact.resize(n + 1, 1);

        for (long long i = 2; i <= n; i++)
        {
            fact[i] = fact[i - 1] * i % mod;
        }

        invfact[n] = modinv(fact[n], mod);
        for (long long i = n - 1; i >= 2; i--)
        {
            invfact[i] = invfact[i + 1] * (i + 1) % mod;
        }
    };
    set_fact(5e6, mod);

    auto comb = [&](long long n, long long k, long long mod) -> long long
    {
        if (k > n || k < 0)
        {
            return 0;
        }
        if (k == n || k == 0)
        {
            return 1;
        }

        return fact[n] * invfact[n - k] % mod * invfact[k] % mod;
    };

    long long ans = 0;

    for (int i = 0; i <= B; i++)
    {
        long long left = comb(A - 1 + B - i, A - 1, mod);
        long long right = comb(C + D + i, C, mod);

        ans += (left * right % mod);
    }

    ans %= mod;

    cout << ans << endl;

    return 0;
}

📌 F - Chord Crossing

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Range Shuffle Query

Warning

Hard Problems to Tackle Later

// TODO