🧩 AtCoder Beginner Contest 368

TayLockAugust 24, 2024About 4 min

🧩 AtCoder Beginner Contest 368

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Tree-pruning	BFS/Tree DP	⭐🔥🧠
E	difference‐constraints	Time‐Sweep	🧠🌀
F	Grundy number	Grundy number(ABC255-G)	🌀
G	Math	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 - Cut

#include <bits/stdc++.h>

using namespace std;

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

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

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

    for (int i = N - K; i < N; i++)
    {
        cout << A[i] << ' ';
    }
    for (int i = 0; i < N - K; i++)
    {
        cout << A[i] << " \n"[i == N - K - 1];
    }

    return 0;
}

📌 B - Decrease 2 max elements

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    vector<int> A(N);
    int ans = 0;

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

    while (true)
    {
        sort(A.rbegin(), A.rend());

        if (A[0] && A[1])
        {
            A[0]--;
            A[1]--;

            ans++;
        }
        else
        {
            break;
        }
    }

    cout << ans << endl;

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    int sum = 0;
    int mx = 0;

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

        sum += A;
        mx = max(mx, A);
    }

    int ans = min(sum / 2, sum - mx);

    cout << ans << endl;

    return 0;
}

📌 C - Triple Attack

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

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

    long long T = 0;
    for (int i = 0; i < N; i++)
    {
        T += H[i] / 5 * 3;
        H[i] %= 5;

        while (H[i] > 0)
        {
            T++;
            if (T % 3 == 0)
            {
                H[i] -= 3;
            }
            else
            {
                H[i] -= 1;
            }
        }
    }

    cout << T << endl;

    return 0;
}

📌 D - Minimum Steiner Tree

Tips

A minimal subtree that spans a given set of vertices in a tree must include:

Every one of the $K$ special vertices themselves, and
Any other vertices that act as "junctions" or "bridges" required to keep those $K$ vertices connected

#include <bits/stdc++.h>

using namespace std;

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

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

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

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // f[v] = 1 marks that node v is one of the required nodes
    // sum[v]: store how many required nodes exist in the subtree rooted at v
    vector<int> f(N), sum(N);
    for (int i = 0; i < K; i++)
    {
        int v;
        cin >> v;
        v--;

        f[v] = 1;
    }

    // the number of edges that will remain in the pruned subtree
    int ans = 0;

    auto dfs = [&](auto &&self, int u, int p) -> void
    {
        sum[u] = f[u];

        // counts how many child branches from this node lead to required nodes
        int ch = 0;

        // If u itself is special, treat that as "two directions" so u is guaranteed to be kept
        if (f[u] == 1)
        {
            ch += 2;
        }

        for (auto v : adj[u])
        {
            if (v == p)
            {
                continue;
            }

            self(self, v, u);
            sum[u] += sum[v];

            // If the child-subtree v contains any special vertex,
            // then "that direction" must be kept, so increment ch
            if (sum[v] > 0)
            {
                ch++;
            }
        }

        // If sum[u] < K, it means not all special vertices are in u's subtree
        // In other words, there must be some special vertex outside of u's subtree
        // so "the direction toward the parent" also needs to be kept
        if (sum[u] < K)
        {
            ch++;
        }

        // If u has 2 or more distinct "directions" that must be kept,
        // then u must remain in the minimal subtree
        if (ch >= 2)
        {
            ans++;
        }
    };

    dfs(dfs, 0, -1);

    cout << ans << endl;

    return 0;
}

Tips

Let us say a tree is applicable if it is obtained by removing zero or more edges and vertices from the original graph and it contains all of vertices $V_1, ..., V_K$

Also, let us say a vertex is bad if its degree is 1 and it is not any of $V_1, ..., V_K$

Then, the sought tree is obtained by, starting from the original tree, repeatedly removing a bad vertex and its adjacent edge as many times as possible. This operation can be done fast enough by managing the vertices directly connected by an edge for each vertex

#include <bits/stdc++.h>

using namespace std;

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

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

    // Build adjacency sets (zero‐based)
    vector<set<int>> adj(N);
    for (int i = 1; i < N; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        adj[u].insert(v);
        adj[v].insert(u);
    }

    // Mark which vertices are special
    vector<bool> isSpecial(N);
    for (int i = 0; i < K; i++)
    {
        int u;
        cin >> u;
        u--;

        isSpecial[u] = true;
    }

    // Compute initial degree of each vertex
    vector<int> deg(N);
    for (int i = 0; i < N; i++)
    {
        deg[i] = adj[i].size();
    }

    // Initialize queue with every leaf that is NOT special
    queue<int> q;
    for (int i = 0; i < N; i++)
    {
        if (deg[i] == 1 && !isSpecial[i])
        {
            q.push(i);
        }
    }

    // ans = how many vertices are currently "in" the pruned tree
    int ans = N;

    // Repeatedly remove bad leaves
    while (!q.empty())
    {
        int u = q.front();
        q.pop();

        // If it has already been removed or is now special, skip
        if (isSpecial[u] || deg[u] != 1)
        {
            continue;
        }

        // Let u be the only neighbor of v
        int v = *adj[u].begin();

        // Remove the edge (v,u) from both adjacency sets
        adj[u].erase(v);
        adj[v].erase(u);

        // We prune away vertex v entirely:
        ans--;

        deg[u] = 0; // v is now "gone"
        deg[v]--;   // u lost one neighbor

        // If v has become a leaf (degree=1) and is not special, enqueue u
        if (deg[v] == 1 && !isSpecial[v])
        {
            q.push(v);
        }
    }

    cout << ans << endl;

    return 0;
}

📌 E - Train Delay

Warning

Hard Problems to Tackle Later

// TODO

📌 F - Dividing Game

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Add and Multiply Queries

Warning

Hard Problems to Tackle Later

// TODO