🧩 AtCoder Beginner Contest 406

TayLockMay 17, 2025About 4 min

🧩 AtCoder Beginner Contest 406

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
C	String	Brute Force	🌀
E	Digit DP	Digit DP	🌀
F	Tree	DFS & Fenwick Tree	🌀
G	DP	DP/Fenwick 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 - Not Acceptable

#include <bits/stdc++.h>

using namespace std;

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

    int a, b, c, d;
    cin >> a >> b >> c >> d;

    if (a * 60 + b >= c * 60 + d)
    {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

📌 B - Product Calculator

#include <bits/stdc++.h>

using namespace std;

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

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

    __int128 limit = 1;
    for (int i = 0; i < k; i++)
    {
        limit *= 10;
    }

    __int128 num = 1;
    for (int i = 0; i < n; i++)
    {
        long long a;
        cin >> a;

        num *= a;

        if (num >= limit)
        {
            num = 1;
        }
    }

    unsigned long long ans = (unsigned long long)num;
    cout << ans << endl;

    return 0;
}

📌 C - ~

Tips

Define a string S of length $(N - 1)$ that represents orderings of adjacent elements of $P$ as follows:

$S_i = '<'$ if $P_i < P_{i + 1}$
$S_i = '>'$ if $P_i > P_{i + 1}$

Then, a sequence $(P_l, P_{l + 1}, ..., P_{r})$ is tilde-shaped if and only if $S_lS_{l + 1}...S_{r - 1}$ is a concatenation of one or more <, one or more >, and one or more <, in this order

Now, consider the run-length compression of S. For example, applying the run-length compression against S = ><<>><<<<> yields a sequence (>1, <2, >2, <4, >1)

The one or more > part corresponds to an element of the result of the run-length compression (representing repeated >)

This motivates us to brute-force over the one or more > part
When this part is fixed, let $a$ be the number of < to its left, and $b$ be the number of < to its right
Then the number of left < in the resulting string can be one of $1, 2, ..., a$ , and that for right can be $1, 2, ..., b$ , so there are $ab$ applicable strings

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

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

    vector<pair<char, long long>> v;
    for (int i = 0; i < n - 1; i++)
    {
        if (p[i] < p[i + 1])
        {
            if (v.empty() || v.back().first == '>')
            {
                v.push_back({'<', 1});
            } else {
                v.back().second++;
            }
        } else {
            if (v.empty() || v.back().first == '<')
            {
                v.push_back({'>', 1});
            } else {
                v.back().second++;
            }
        }
    }

    long long ans = 0;

    for (int i = 1; i < v.size() - 1; i++)
    {
        if (v[i].first == '>')
        {
            ans += v[i - 1].second * v[i + 1].second;
        }
    }

    cout << ans << endl;

    return 0;
}

📌 D - Garbage Removal

#include <bits/stdc++.h>

using namespace std;

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

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

    map<int, set<int>> row, col;
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;

        row[x].insert(y);
        col[y].insert(x);
    }

    int q;
    cin >> q;

    while (q--)
    {
        int a;
        cin >> a;

        if (a == 1)
        {
            int x;
            cin >> x;

            cout << row[x].size() << endl;
            for (auto y : row[x])
            {
                col[y].erase(x);
            }
            row[x].clear();
        } else {
            int y;
            cin >> y;

            cout << col[y].size() << endl;
            for (auto x : col[y])
            {
                row[x].erase(y);
            }
            col[y].clear();
        }
    }

    return 0;
}

📌 E - Popcount Sum 3

I can not fully understand this code

Tips

We write $N$ in binary, then DP over bit-positions, tracking how many 1’s remain to place and whether we’re still on the tight prefix

We accumulate both the count of valid completions and the sum of the numbers they form

Tips

Define dp[pos][ones_left][tight] = (count, sum)

count: the number of ways to choose bits pos, ..., L - 1 so that exactly ones_left ones remain
sum: the sum of all those resulting integer values (mod $998244353$ )

#include <bits/stdc++.h>

using namespace std;

static const int MOD = 998244353;

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

    // fast exponentiation mod
    auto modpow = [&](long long a, int e)
    {
        long long r = 1;
        while (e)
        {
            if (e & 1)
                r = (r * a) % MOD;
            a = (a * a) % MOD;
            e >>= 1;
        }
        return r;
    };

    // Stores 2^i mod MOD, used to compute value of bits when building numbers
    vector<long long> pow2(60);
    // precompute powers of two mod
    for (int i = 0; i < 60; i++)
    {
        pow2[i] = modpow(2, i);
    }

    int T;
    cin >> T;

    while (T--)
    {
        unsigned long long N;
        int K;
        cin >> N >> K;

        // build binary repr of N, then strip leading zeros
        // Stores the binary representation of N, as a vector of bits from most significant to least significant.
        vector<int> bits;
        for (int i = 63; i >= 0; --i)
        {
            bits.push_back((N >> i) & 1ULL);
        }
        while (!bits.empty() && bits.front() == 0)
        {
            bits.erase(bits.begin());
        }

        if (bits.empty())
        {
            bits.push_back(0);
        }
        int L = bits.size();

        // dp[pos][ones_left][tight] = (count, sum)
        vector<vector<vector<pair<long long, long long>>>> dp_memo(64, vector<vector<pair<long long, long long>>>(64, vector<pair<long long, long long>>(2)));
        vector<vector<vector<bool>>> dp_vis(64, vector(64, vector(2, false)));

        // pos: current bit position (from left to right)
        // ones_left: how many 1s are still allowed to use
        // tight: whether current number is still equal to prefix of N
        //      tight == 1: we can only use bits <= corresponding bit in N
        //      tight == 0: we can use any bits
        auto dfs = [&](auto &&self, int pos, int ones_left, int tight) -> pair<long long, long long>
        {
            // pos in [0..L], ones_left ≥ 0, tight ∈ {0,1}
            if (ones_left < 0)
            {
                return {0, 0};
            }
            if (pos == L)
            {
                // at end: valid iff we've used exactly K ones
                if (ones_left == 0)
                {
                    return {1, 0};
                }
                else
                {
                    return {0, 0};
                }
            }
            if (dp_vis[pos][ones_left][tight])
            {
                return dp_memo[pos][ones_left][tight];
            }

            long long ways = 0, ssum = 0;
            int limit = tight ? bits[pos] : 1;

            // bit at this position: 0 or 1
            for (int b = 0; b <= limit; b++)
            {
                int nt = tight && (b == limit);

                auto sub = self(self, pos + 1, ones_left - b, nt);
                long long c = sub.first;
                long long sm = sub.second;

                // if we place a 1 here, we add its weight * count
                if (b)
                {
                    // weight of this bit = 2^(L - 1 - pos)
                    long long w = pow2[L - 1 - pos];
                    sm = (sm + w * c) % MOD;
                }

                ways = (ways + c) % MOD;
                ssum = (ssum + sm) % MOD;
            }
            dp_vis[pos][ones_left][tight] = true;

            // Stores intermediate results in dp_memo to avoid recomputation
            return dp_memo[pos][ones_left][tight] = make_pair(ways, ssum);
        };

        // launch DP
        auto ans = dfs(dfs, 0, K, 1).second;

        cout << ans << "\n";
    }

    return 0;
}

:::

Warning

Hard Problems to Tackle Later

// TODO

📌 F - Compare Tree Weights

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Travelling Salesman Problem

Warning

Hard Problems to Tackle Later

// TODO