🧩 AtCoder Beginner Contest 376

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Shortest distance	BFS	⭐🔥
E	Math	Math	🧠🌀
F	DP	DP	🌀
G	Math	01 on 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 - Candy Button

376A

#include <bits/stdc++.h>

using namespace std;

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

    int N, C;
    cin >> N >> C;

    int ans = 0;
    int lst = -1;

    for (int i = 0; i < N; i++)
    {
        int T;
        cin >> T;

        if (lst == -1 || T - lst >= C)
        {
            ans += 1;
            lst = T;
        }
    }

    cout << ans << endl;

    return 0;
}

📌 B - Hands on Ring (Easy)

376B

#include <bits/stdc++.h>

using namespace std;

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

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

    int ans = 0;

    int L = 0, R = 1;

    for (int i = 0; i < Q; i++)
    {
        char H;
        int T;
        cin >> H >> T;
        T--;

        if (H == 'L')
        {
            if ((L < R && R < T) || (T < R && R < L))
            {
                ans += N - abs(T - L);
            }
            else
            {
                ans += abs(T - L);
            }

            L = T;
        }
        else
        {
            if ((R < L && L < T) || (T < L && L < R))
            {
                ans += N - abs(T - R);
            }
            else
            {
                ans += abs(T - R);
            }

            R = T;
        }
    }

    cout << ans << endl;

    return 0;
}

📌 C - Prepare Another Box

376C

#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), B(N - 1);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    for (int i = 0; i < N - 1; i++)
    {
        cin >> B[i];
    }

    sort(A.begin(), A.end(), greater());
    sort(B.begin(), B.end(), greater());

    int i = 0;
    while (i < N - 1 && A[i] <= B[i])
    {
        i++;
    }

    for (int j = i; j < N - 1; j++)
    {
        if (B[j] < A[j + 1])
        {
            cout << -1 << endl;
            return 0;
        }
    }

    cout << A[i] << endl;

    return 0;
}

📌 D - Cycle

376D

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        adj[u].push_back(v);
    }

    vector<int> dis(N, -1);
    dis[0] = 0;

    queue<int> q;
    q.push(0);

    int ans = N + 1;

    while (!q.empty())
    {
        auto u = q.front();
        q.pop();

        for (auto v : adj[u])
        {
            if (v == 0)
            {
                ans = min(ans, dis[u] + 1);
            }

            if (dis[v] == -1)
            {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }

    cout << (ans == N + 1 ? -1 : ans) << endl;

    return 0;
}

📌 E - Max × Sum

376E

Tips

Sort $A$ ascendingly, so $A_1 \le A_2 \le ... \le A_N$

For each position $r$, we only need to choose $K - 1$ items from ${1, ..., r - 1}$ to put into $S$

And, $\max_{i \in S}A_i \equiv A_r$ regardless of our choice

So the new objective function becomes:

$$\begin{align*} Cost(S) &= \max_{i \in S}A_i \times \sum_{i \in S}B_i \\ &= A_r \times (B_r + \sum_{i \in S ans i \neq r}B_i) \end{align*}$$

Tips

For all $r = K, K + 1, ..., N$, how to compute the sum of the smallest $K - 1$ values in $B_1, ..., B_{r - 1}$?

To do this efficiently, we use:

• A max-heap (priority queue) to track the $K−1$ smallest values among current prefix
• If size exceeds $K - 1$, remove the largest(i.e., worst)

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int N, K;
    cin >> N >> K;

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

    long long ans = 1e18;

    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int j)
         { return A[i] < A[j]; });

    priority_queue<long long> pq;
    long long sum = 0;

    for (auto i : idx)
    {
        sum += B[i];
        pq.push(B[i]);

        while (pq.size() > K)
        {
            sum -= pq.top();
            pq.pop();
        }

        if (pq.size() == K)
        {
            ans = min(ans, sum * A[i]);
        }
    }

    cout << ans << endl;
}

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

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }

    return 0;
}

📌 F - Hands on Ring (Hard)

376F

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Treasure Hunting

376G

Warning

Hard Problems to Tackle Later

// TODO