🧩 AtCoder Beginner Contest 386

TayLockDecember 28, 2024About 2 min

🧩 AtCoder Beginner Contest 386

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
E	XOR	DFS/DP	🧠🛠️🔥
F	LCP	LCP	🌀

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 - Full House 2

#include <bits/stdc++.h>

using namespace std;

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

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

        st.insert(a);
    }

    cout << (st.size() == 2 ? "Yes" : "No") << endl;

    return 0;
}

📌 B - Calculator

#include <bits/stdc++.h>

using namespace std;

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

    string S;
    cin >> S;

    int ans = 0;
    bool pre_zero = false;

    for (auto c : S)
    {
        ans += 1;

        if (c != '0')
        {
            pre_zero = false;
        } else {
            ans -= pre_zero;
            pre_zero = !pre_zero;
        }
    }

    cout << ans << endl;

    return 0;
}

📌 C - Operate 1

#include <bits/stdc++.h>

using namespace std;

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

    int K;
    string S, T;
    cin >> K >> S >> T;

    int n = S.size(), m = T.size();
    if (abs(n - m) > 1)
    {
        cout << "No" << endl;
        return 0;
    }

    if (n == m)
    {
        if (S == T)
        {
            cout << "Yes" << endl;
            return 0;
        }

        bool use = false;
        for (int i = 0; i < n; i++)
        {
            if (S[i] != T[i])
            {
                if (use)
                {
                    cout << "No" << endl;
                    return 0;
                }
                use = true;
            }
        }

        cout << "Yes" << endl;
    }
    else if (n > m)
    {
        bool use = false;
        for (int i = 0; i < n; i++)
        {
            if (S[i] != T[i - use])
            {
                if (use)
                {
                    cout << "No" << endl;
                    return 0;
                }
                use = true;
            }
        }

        cout << "Yes" << endl;
    }
    else
    {
        bool use = false;
        for (int i = 0; i < m; i++)
        {
            if (S[i - use] != T[i])
            {
                if (use)
                {
                    cout << "No" << endl;
                    return 0;
                }
                use = true;
            }
        }

        cout << "Yes" << endl;
    }

    return 0;
}

📌 D - Diagonal Separation

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<tuple<int, int, char>> A;
    for (int i = 0; i < M; i++)
    {
        int x, y;
        char c;
        cin >> x >> y >> c;
        x--;
        y--;

        A.push_back({x, y, c});
    }
    sort(A.begin(), A.end());

    int min_y = 1e9;
    for (auto [x, y, c] : A)
    {
        if (c == 'W')
        {
            min_y = min(min_y, y);
        }
        else
        {
            if (y >= min_y)
            {
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;

    return 0;
}

📌 E - Maximize XOR

Tips

Since it is guaranteed that there are at most $10^6$ ways to choose $K$ distinct elements from $A$ , it is possible to enumerate all such choices with an appropriate algorithm

Tips

To finish the process within the time limit when $K$ is large, one can inspect $(N−K)$ elements that are not chosen, instead of chosen $K$ elements. Specifically, one can do the following branching:

If $K \le N - K$ : we can naively do the exhaustive search
If $K > N - K$ : first find the total XOR of the elements, and exhaustively search the remaining $(N - K)$ elements. This way, we can find the XOR of the chosen $K$ elements fast

#include <bits/stdc++.h>

using namespace std;

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

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

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

    vector<long long> suf(N + 1);
    for (int i = N - 1; i >= 0; i--)
    {
        suf[i] = suf[i + 1] ^ A[i];
    }

    long long ans = 0;

    auto dfs = [&](auto &&self, int i, int k, long long x) -> void
    {
        if (k == 0)
        {
            ans = max(ans, x);
            return;
        }

        if (i + k == N)
        {
            ans = max(ans, x ^ suf[i]);
            return;
        }

        self(self, i + 1, k, x);
        self(self, i + 1, k - 1, x ^ A[i]);
    };

    dfs(dfs, 0, K, 0ll);

    cout << ans << endl;

    return 0;
}

📌 F - Operate K

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Many MST

Warning

Hard Problems to Tackle Later

// TODO