🧩 AtCoder Beginner Contest 390

TayLockJanuary 25, 2025About 6 min

🧩 AtCoder Beginner Contest 390

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Bell Number	DFS/Bell Number	⭐🔥🧠
E	DP	DP/Binary Search	🔥

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 - 12435

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<int> ans = {1, 2, 3, 4, 5};

    for (int i = 0; i < 4; i++)
    {
        vector<int> B = A;
        swap(B[i], B[i + 1]);

        if (B == ans)
        {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;

    return 0;
}

📌 B - Geometric Sequence

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

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

    for (int i = 1; i < n - 1; i++)
    {
        if (A[i - 1] * A[i + 1] != A[i] * A[i])
        {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}

📌 C - Paint to make a rectangle

#include <bits/stdc++.h>

using namespace std;

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

    int h, w;
    cin >> h >> w;

    vector<string> grid(h);
    int minx = h, miny = w;
    int maxx = 0, maxy = 0;
    for (int i = 0; i < h; i++)
    {
        cin >> grid[i];

        for (int j = 0; j < w; j++)
        {
            if (grid[i][j] == '#')
            {
                minx = min(minx, i);
                miny = min(miny, j);
                maxx = max(maxx, i);
                maxy = max(maxy, j);
            }
        }
    }

    for (int i = minx; i <= maxx; i++)
    {
        for (int j = miny; j <= maxy; j++)
        {
            if (grid[i][j] == '.')
            {
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;

    return 0;
}

📌 D - Stone XOR

Tips

Considering which bags’ stones merge into one in the final state, we find that the answer to the problem is equal to that to the following:

consider dividing bags $1$ , bags $2$ , ..., and bags $N$ into several groups, and finding the total number of stones in the bags in each group. How many distinct integers can be the XOR (exclusive logical sum) of the counts?

Tips

The number of ways to divide $N$ items into groups (where the items and groups are indistinguishable) is known as the Bell number $B(N)$ . The Bell number increases as $N$ increases, and $B(12) = 4213597(~4 \times 10^6)$ for $N = 12$ , so we can exhaustively enumerate them under the constraints ( $2 \le N \le 12$ ) of this problem

There are several ways for the exhaustive search; one is a DFS (Depth-First Search) based approach as follows. Starting from the state with depth $1$ and $0$ groups, we perform the following operation:

Tips

When the current depth $d$ and there are $k$ groups, perform the following operation for each $11 \le i \le K + 1$ in order:

Let bag $d$ $d$ belong to group $i$ $i$
- Here, if $i = K + 1$ , it means we create a new group consisting only of bag $d$
If $d = N$ , record the XOR of the (group-wise) total numbers of stones in each group
IF $d < N$ $d < N$ , advance to the nex depth $d + 1$ $d + 1$
- Note that the number of groups has increased if $i = k + 1$

After searching for all $i$ , go back to the previous depth $d - 1$ . If $d = 1$ , stop the search

After the search ends, the sought answer is the number of distinct recorded integers

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

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

    // keep track of the number of stones in each group at each step
    vector<long long> cnt(n, 0);
    // A set to store distinct XOR results
    unordered_set<long long> st;

    // The current XOR value
    long long val = 0;

    // idx: The current index of the bag being considered
    // sz: The number of groups formed so far
    auto dfs = [&](auto &&self, int idx, int sz) -> void
    {
        // For each group, we recursively decide whether to add the current bag to an existing group or create a new group
        for (int i = 0; i <= sz; i++)
        {
            val ^= cnt[i];    // XOR out the current value of the group
            cnt[i] += A[idx]; // Add the current bag to the group
            val ^= cnt[i];    // XOR in the new value of the group

            if (idx == n - 1)
            {
                // If it's the last bag, insert the XOR result into the set
                st.insert(val);
            }
            else if (i < sz)
            {
                // If we're not adding a new group, continue exploring
                self(self, idx + 1, sz);
            }
            else
            {
                // Otherwise, create a new group
                self(self, idx + 1, sz + 1);
            }

            val ^= cnt[i];    // Backtrack: XOR out the current value of the group
            cnt[i] -= A[idx]; // Remove the current bag from the group
            val ^= cnt[i];    // XOR in the old value
        }
    };

    // start with the first bag and an empty set of groups
    dfs(dfs, 0, 0);

    cout << (int)st.size() << endl;

    return 0;
}

📌 E - Vitamin Balance

Tips

For each vitamin $i$ ( $i \le i \le 3$ ), precalcaulte the maximum intake of vitamin $i$ (ignoring the other vitamin) to that the total calorie consumption does not exceed $j$ ( $0 \le j \le X$ ), using Dynamic Programming

Let $dp_i[k][j]$ $(1 \le i \le 3, 0 \le j \le X, 0 \le k \le N)$ represent the maximum intake of vitamin $i$ when choosing foods from the $1$ -st through $k$ -th, so that the total calorie consumption is exactly $j$ (or $-\infty$ if it is impossible):

First, we have $dp_i[0][0] = 0$ and $dp_i[0][j] = -1$ , where $(1 \le j \le X)$
Next, for each food $i$ $i$
- if food $k$ ( $1 \le k \le N$ ) does not contain vitamin $i$ , then $dp_i[k][j] = dp_i[k - 1][j]$
- if it does, considering whether to eat or not: $dp_i[k][j] = \max(dp_i[k - 1][j], dp_i[k - 1][j - C_k] + A_k)$ where $C_k \le j$ , for $j \le C_k$ , we have $dp_i[k][j] = dp_i[k - 1][j]$
The sought value is the resulting $dp_i[N][j]$

Next, we consider $M_{i, j}$ , the maximum intake of vitamin $i$ so that the total calorie consumption does not exceed $j$ ( $0 \le j \le X$ , which satisfies $M_{i, j} = \max_{0 \le j' \le j}(dp_i[N][j'])$ . This can be computed incrementally as $M_{i, 0} = dp_i[N][0]$ ans $M_{i, j} = \max(M_{i, j - 1}, dp_[N][j])$ )

Finally, when the total calorie consumption of the food to intake vitamin $i$ ( $1 \le i \le 3$ ) is $s_i$ , the minimum intake among vitamin $1$ , $2$ and $3$ is given as $\min(M_{1, s_1}, M_{2, s_2}, M_{3, s_3})$ , so the sought value is:

\max_{s_1 + s_2 + s_3 = X} \min (M_{1, s_1}, M_{2, s_2}, M_{3, s_3})

#include <bits/stdc++.h>

using namespace std;

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

    int n, x;
    cin >> n >> x;

    vector<vector<pair<int, int>>> food(3);
    for (int i = 0; i < n; i++)
    {
        int v, a, c;
        cin >> v >> a >> c;
        v--;

        food[v].push_back({a, c});
    }

    auto solve = [&](vector<pair<int, int>> ac) -> vector<int>
    {
        vector<int> dp(x + 1);
        for (auto [a, c] : ac)
        {
            for (int i = x; i >= c; i--)
            {
                dp[i] = max(dp[i], dp[i - c] + a);
            }
        }

        return dp;
    };

    auto f = solve(food[0]);
    auto g = solve(food[1]);
    auto h = solve(food[2]);

    int ans = 0;
    for (int i = 0; i <= x; i++)
    {
        for (int j = 0; i + j <= x; j++)
        {
            ans = max(ans, min({f[i], g[j], h[x - i - j]}));
        }
    }

    cout << ans << endl;

    return 0;
}

Binary Search

The goal is to find the largest satisfaction value mid such that the total number of items selected across all categories does not exceed the budget $X$

Details

#include <bits/stdc++.h>

using namespace std;

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

    int n, x;
    cin >> n >> x;

    vector<vector<pair<int, int>>> food(3);
    for (int i = 0; i < n; i++)
    {
        int v, a, c;
        cin >> v >> a >> c;
        v--;

        food[v].push_back({a, c});
    }

    auto solve = [&](vector<pair<int, int>> ac) -> vector<int>
    {
        vector<int> dp(x + 1);
        for (auto [a, c] : ac)
        {
            for (int i = x; i >= c; i--)
            {
                dp[i] = max(dp[i], dp[i - c] + a);
            }
        }

        return dp;
    };

    auto f = solve(food[0]);
    auto g = solve(food[1]);
    auto h = solve(food[2]);

    auto check = [&](long long mid) -> bool
    {
        long long sum = 0;
        sum += lower_bound(f.begin(), f.end(), mid) - f.begin();
        sum += lower_bound(g.begin(), g.end(), mid) - g.begin();
        sum += lower_bound(h.begin(), h.end(), mid) - h.begin();

        return sum <= x;
    };

    long long l = 0, r = 1e10;
    while (r - l > 1)
    {
        long long mid = l + (r - l) / 2;
        if (check(mid))
        {
            l = mid;
        } else {
            r = mid;
        }
    }

    cout << l << endl;

    return 0;
}

📌 F - Double Sum 3

Warning

Hard Problems to Tackle Later

Tips

When the blackboard has some integers, it is optimal to pick $l$ and $r$ to maximize $r - l$ in order to minimize the number of operations

That is, we can pick $(l, r)$ such that:

$l - 1$ is not written on the blackboard
all integers from $l$ through $r$ are written on the blackboard, and
$r + 1$ is not written on the blackboard

and remove them

// TODO

📌 G - Permutation Concatenation

Warning

Hard Problems to Tackle Later

// TODO