🧩 AtCoder Beginner Contest 370

# Info & Summary

• Date: 2024-09-07
• Completion Status: A ✅ / B ✅ / C ✅ / D ✅ / E ❌ / F ❌ / G ❌
• Problem Type:

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
E	DP	DP & Dynamic ModInt	🧠🛠️🌀
F	Binary Search	Binary Search	🌀
G	multiplicative function	Lucy DP	🌀

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 - Raise Both Hands

370A

#include <bits/stdc++.h>

using namespace std;

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

    int l, r;
    cin >> l >> r;

    if (l == 1 && r == 0)
    {
        cout << "Yes" << endl;
    } else if (l == r)
    {
        cout << "Invalid" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

📌 B - Binary Alchemy

370B

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    vector<vector<int>> A(N + 1, vector<int>(N + 1));
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            cin >> A[i][j];
        }
    }

    int ans = 1;
    for (int i = 1; i <= N; i++)
    {
        if (ans >= i)
        {
            ans = A[ans][i];
        } else {
            ans = A[i][ans];
        }
        // cout << ans << endl;
    }

    cout << ans << endl;

    return 0;
}

📌 C - Word Ladder

370C

#include <bits/stdc++.h>

using namespace std;

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

    string S, T;
    cin >> S >> T;

    int N = S.size();

    vector<string> ans;

    // -------------- answerr 1 -----------------
    // while (S != T)
    // {
    //     int rst = -1;
    //     bool change = false;
    //     for (int i = 0; i < N; i++)
    //     {
    //         if (S[i] < T[i])
    //         {
    //             rst = i;
    //         } else if (S[i] > T[i])
    //         {
    //             S[i] = T[i];
    //             ans.push_back(S);
    //             change = true;
    //             break;
    //         }
    //     }

    //     if (!change)
    //     {
    //         S[rst] = T[rst];
    //         ans.push_back(S);
    //     }
    // }

    // -------------- answerr 2 -----------------
    for (int i = 0; i < N; i++)
    {
        if (S[i] > T[i])
        {
            S[i] = T[i];
            ans.push_back(S);
        }
    }
    for (int i = N - 1; i >= 0; i--)
    {
        if (S[i] < T[i])
        {
            S[i] = T[i];
            ans.push_back(S);
        }
    }

    cout << ans.size() << endl;
    for (auto s : ans)
    {
        cout << s << endl;
    }

    return 0;
}

📌 D - Cross Explosion

370D

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<set<int>> r(H), c(W);
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            r[i].insert(j);
            c[j].insert(i);
        }
    }

    int ans = H * W;

    for (int i = 0; i < Q; i++)
    {
        int R, C;
        cin >> R >> C;
        R--;
        C--;

        if (r[R].count(C))
        {
            r[R].erase(C);
            c[C].erase(R);

            ans--;
        }
        else
        {
            // up
            auto it = r[R].lower_bound(C);
            if (it != r[R].begin())
            {
                int t = *prev(it);
                r[R].erase(t);
                c[t].erase(R);

                ans--;
            }
            if (it != r[R].end())
            {
                int t = *it;
                r[R].erase(t);
                c[t].erase(R);

                ans--;
            }

            it = c[C].lower_bound(R);
            if (it != c[C].begin())
            {
                int t = *prev(it);
                r[t].erase(C);
                c[C].erase(t);

                ans--;
            }
            if (it != c[C].end())
            {
                int t = *it;
                r[t].erase(C);
                c[C].erase(t);

                ans--;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

📌 E - Avoid K Partition

370E

Tips

For explanation, let us rephrase the problem as follows:

There are points $1, 2, ..., N + 1$ arranged in this order. How many ways, modulo $998244353$, are there to choose some points to put partitions on them, so that:

• points $1$ and $N + 1$ always have a partition, and
• if points $i$ and $j$ have a partition but not at any points between them, then $\sum_{k = i}^{j - 1}A_k$ never equals $K$

Tips

This new version allows us an $O(N^2)$ DP. Specifically, we can define:

$dp[i]$: the number of ways to choose points from point $1$ through $i$, while always choosing point $i$

The transition:

• The initial state is $dp[1] = 1$
• The answer is $dp[N + 1]$
• The transition being:

$$dp[n] = \sum_{1 \le m < n}\begin{cases} 0, & \sum_{k = m}^{n - 1}A_i = K \\ dp[m],& else \end{cases}$$

We try to optimize this DP

Define the cumulative sum table of $A$ as:

$$B_i = \sum_{j = 1}^{i}A_j$$

then the transition above turns into:

$$\begin{align*} dp[n] &= \sum_{1 \le m < n}\begin{cases} 0, & \sum_{k = m}^{n - 1}A_i = K \\ dp[m],& else \end{cases} \\ &= \sum_{1 \le m < n} \begin{cases} 0 & B_{n - } - B_{m - 1} = K\\ dp[m], & else \end{cases}\\ &= \sum_{1 \le m < n, B_{m - 1} \neq B_{n - 1} - K}dp[m] \end{align*}$$

Tips

In other words, whether $dp[m]$ contributes to $dp[n]$ is solely dependent on the value of $B_{m - 1}$

So, we manage the DP table is an associative array (std::map in C++). Define an associative array $M$ by:

$M[x]$: the sum of $dp[m]$ over $m$ with $B_{m - 1} = x$

Also, manage the sum of $dp[m]$ in a variable all. Then the transition of the DP can be written as:

$$dp[n] = all - M[B_{n - 1} - K]$$

📌 F - Cake Division

370F

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Divisible by 3

370G

Warning

Hard Problems to Tackle Later

// TODO