🧩 AtCoder Beginner Contest 380

TayLockNovember 16, 2024About 3 min

🧩 AtCoder Beginner Contest 380

# Info & Summary

Date: 2024-11-16
Completion Status: A ✅ / B ✅ / C ✅ / D ✅ / E ❌ / F ❌ / G ❌
Problem Type:

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Math	Math	🧠
E	Simulation	DSU	🧠🛠️🌀
F	Simulation	Simulation	🌀
G	segment-sum queries	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 - 123233

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    map<int, int> mp;
    while (N)
    {
        mp[N % 10]++;
        N /= 10;
    }

    cout << (mp[1] == 1 && mp[2] == 2 && mp[3] == 3 ? "Yes" : "No") << endl;

    return 0;
}

📌 B - Hurdle Parsing

#include <bits/stdc++.h>

using namespace std;

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

    string S;
    cin >> S;

    vector<int> ans;
    int cnt = 0;
    for (auto c : S)
    {
        if (c == '|')
        {
            ans.push_back(cnt);
            cnt = 0;
        } else {
            cnt += 1;
        }
    }

    for (int i = 1; i < ans.size(); i++)
    {
        cout << ans[i] << " \n"[i == ans.size() - 1];
    }

    return 0;
}

📌 C - Move Segment

#include <bits/stdc++.h>

using namespace std;

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

    int N, K;
    cin >> N >> K;

    string S;
    cin >> S;

    vector<pair<char, string>> v;
    for (auto c : S)
    {
        if (v.empty() || c != v.back().first)
        {
            string t = "";
            t += c;
            v.push_back({c, t});
        }
        else
        {
            v.back().second += c;
        }
    }

    // cout << v.size() << endl;
    // for (auto p : v)
    // {
    //     cout << p.first << " " << p.second << endl;
    // }

    string ans = "";

    int cnt = 0;
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i].first == '1')
        {
            cnt += 1;

            if (cnt == K - 1)
            {
                swap(v[i + 1], v[i + 2]);
            }
        }

        ans += v[i].second;
    }

    cout << ans << endl;

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

    int N, K;
    cin >> N >> K;

    string S;
    cin >> S;

    int x = 0, c = 0;
    for (int l = 0, r = 0; l < N; l = r)
    {
        while (r < N && S[l] == S[r])
        {
            r++;
        }

        if (S[l] == '1')
        {
            c++;

            if (c == K)
            {
                rotate(S.begin() + x, S.begin() + l, S.begin() + r);
                break;
            }

            x = r;
        }
    }

    cout << S << endl;

    return 0;
}

📌 D - Strange Mirroring

Tips

Starting from one block solely forming S, the operation repeatedly append the string itself after flipping the case. After repeating it $k$ times, there will be $2^k$ blocks

Therefore, we have the following fact:

Suppose that we want to determine a character in the $B$ -th block. In the binary representation of B, if the most significant digit 1 is at the $2^k$ 's place, then block B equals block $(B - 2^k)$ with the case flipped

We can follow this step until we reach $B = 0$ to get the correct answer, but we can also come to the following conclusion:

If the number of digits 1 in the binary representation of B is even, then the block B is S itself
If the number of digits 1 in the binary representation of B is odd, then the block B is S with case flipped

Hence, the problem can be answered by determining which block the $K_i$ -th character belongs to and the position of that character in the block, and finding how many digits 1 are there in the binary representation of the block number

#include <bits/stdc++.h>

using namespace std;

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

    string S;
    cin >> S;

    int q;
    cin >> q;

    while (q--)
    {
        unsigned long long k;
        cin >> k;
        k--;

        auto flip = [&](char c) -> char
        {
            if ('a' <= c && c <= 'z')
            {
                return 'A' + (c - 'a');
            }
            else
            {
                return 'a' + (c - 'A');
            }
        };

        char c = S[k % S.size()];
        k /= S.size();

        if (__builtin_parityll(k))
        {
            cout << flip(c) << " \n"[q == 0];
        }
        else
        {
            cout << c << " \n"[q == 0];
        }
    }

    return 0;
}

📌 E - 1D Bucket Tool

Tips

Maintain the following two data structures and update them for each query:

an array cnt[c] storing the number of cells with each color c
an array col[i] maintaining the color of the DSU component rooted at i
a DSU that manages the connected components

#include <bits/stdc++.h>

using namespace std;

struct DSU
{
    vector<int> f, siz;

    DSU() {}
    DSU(int n)
    {
        init(n);
    }

    void init(int n)
    {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x)
    {
        while (x != f[x])
        {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y)
    {
        return find(x) == find(y);
    }

    bool merge(int x, int y)
    {
        x = find(x);
        y = find(y);

        if (x == y)
        {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;

        return true;
    }

    int size(int x)
    {
        return siz[find(x)];
    }
};

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

    int N, Q;
    cin >> N >> Q;

    DSU dsu(N);

    // col[i]: color of the DSU component rooted at i
    // cnt[c]: how many total cells are painted with color c
    vector<int> cnt(N, 1), col(N);
    iota(col.begin(), col.end(), 0);

    for (int i = 0; i < Q; i++)
    {
        int o;
        cin >> o;

        if (o == 1)
        {
            int x, c;
            cin >> x >> c;
            x--;
            c--;

            // Change the color of the entire segment containing x to color c
            x = dsu.find(x);
            cnt[col[x]] -= dsu.size(x);
            col[x] = c;
            cnt[col[x]] += dsu.size(x);

            // try merging with left adjacent segments
            if (x && col[dsu.find(x - 1)] == c)
            {
                dsu.merge(x - 1, x);
            }

            // try merging with right adjacent segments
            x = dsu.find(x);
            if (x + dsu.size(x) < N && col[x + dsu.size(x)] == c)
            {
                dsu.merge(x, x + dsu.size(x));
            }
        }
        else
        {
            int c;
            cin >> c;
            c--;

            cout << cnt[c] << endl;
        }
    }

    return 0;
}

📌 F - Exchange Game

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Another Shuffle Window

Warning

Hard Problems to Tackle Later

// TODO