🧩 AtCoder Beginner Contest 385

TayLockDecember 21, 2024About 3 min

🧩 AtCoder Beginner Contest 385

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
E	Max‐Coverage	Greedy	🧠
F	Math	Math	🌀
G	combinatorics on permutations	Insertion DP	🌀

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 - Equally

#include <bits/stdc++.h>

using namespace std;

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

    vector<int> A(3);
    for (int i = 0; i < 3; i++)
    {
        cin >> A[i];
    }
    sort(A.begin(), A.end());

    if (A[0] + A[1] == A[2] || (A[0] == A[1] && A[1] == A[2]))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

📌 B - Santa Claus 1

#include <bits/stdc++.h>

using namespace std;

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

    int H, W, X, Y;
    cin >> H >> W >> X >> Y;
    X--;
    Y--;

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

    string T;
    cin >> T;

    int ans = 0;
    for (auto c : T)
    {
        // cout << X + 1 << " " << Y + 1 << endl;
        int nx = X, ny = Y;
        if (c == 'U')
        {
            nx = X - 1;
        }
        else if (c == 'D')
        {
            nx = X + 1;
        }
        else if (c == 'L')
        {
            ny = Y - 1;
        }
        else
        {
            ny = Y + 1;
        }

        if (grid[nx][ny] != '#')
        {
            ans += grid[nx][ny] == '@';
            grid[nx][ny] = '.';
            X = nx;
            Y = ny;
        }
    }

    cout << X + 1 << " " << Y + 1 << " " << ans << endl;

    return 0;
}

📌 C - Illuminate Buildings

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

    int ans = 1;

    for (int d = 1; d < N; d++)
    {
        for (int i = 0; i < d; i++)
        {
            int cnt = 0, pre = -1;
            for (int j = i; j < N; j+=d)
            {
                if (pre != A[j])
                {
                    cnt = 1;
                    pre = A[j];
                } else {
                    cnt++;
                }

                ans = max(ans, cnt);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

📌 D - Santa Claus 2

#include <bits/stdc++.h>

using namespace std;

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

    int N, M;
    long long X, Y;
    cin >> N >> M >> X >> Y;

    map<int, set<long long>> mpx, mpy;
    for (int i = 0; i < N; i++)
    {
        long long x, y;
        cin >> x >> y;

        mpx[x].insert(y);
        mpy[y].insert(x);
    }

    int ans = 0;

    for (int i = 0; i < M; i++)
    {
        char d;
        long long c;
        cin >> d >> c;

        long long nX = X, nY = Y;

        if (d == 'U')
        {
            nY = Y + c;
            auto it = mpx[X].lower_bound(Y);
            while (it != mpx[X].end() && *it <= nY)
            {
                ans++;
                mpy[*it].erase(X);
                it = mpx[X].erase(it);
            }
        }
        else if (d == 'D')
        {
            nY = Y - c;
            auto it = mpx[X].lower_bound(nY);
            while (it != mpx[X].end() && *it <= Y)
            {
                ans++;
                mpy[*it].erase(X);
                it = mpx[X].erase(it);
            }
        }
        else if (d == 'L')
        {
            nX = X - c;
            auto it = mpy[Y].lower_bound(nX);
            while (it != mpy[Y].end() && *it <= X)
            {
                ans++;
                mpx[*it].erase(Y);
                it = mpy[Y].erase(it);
            }
        }
        else
        {
            nX = X + c;
            auto it = mpy[Y].lower_bound(X);
            while (it != mpy[Y].end() && *it <= nX)
            {
                ans++;
                mpx[*it].erase(Y);
                it = mpy[Y].erase(it);
            }
        }

        X = nX;
        Y = nY;
    }

    cout << X << " " << Y << " " << ans << endl;
    return 0;
}

📌 E - Snowflake Tree

Tips

In the construction of a Snowflake Tree, let us:

call the vertex prepared in step 2 the center
call the $x$ vertices prepared in step 3 the first layer
call $d_v$ the degree of the vertex $v$ in tree $T$

Fix a vertex $u$ to become the center, and the number of first-layer vertices $x$ . If vertices $v_1, v_2, ..., v_x$ are chosen for the first layer, the maximum value that can be chosen for $y$ is $\max{d_{v_1}, d_{v_2}, ..., d_{v_x}} - 1$

Thus, among the vertices adjacent to $u$ , it is optimal to choose the $x$ vertices with the largest degrees:

$d_{v_1} \ge d_{v_2} \ge ... \ge d_{v_{d_u}}$
once $x$ is fixed, a Snowflake Tree with $(1 + x + xy)$ vertices can be constructed, where $y = d_{v_x} - 1$
$N - (1 + x + xy)$ vertices need to be removed

The problem can be solved by iterating through $u$ and $x$ exhaustively, counting the number of vertices to be removed, and finding their minimum value

The time complexity is $O(N\logN)$ , where sorting is the bottleneck

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

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

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

        deg[u]++;
        deg[v]++;
    }

    int ans = N;

    for (int u = 0; u < N; u++)
    {
        sort(adj[u].begin(), adj[u].end(), [&](int i, int j){ return deg[i] > deg[j]; });

        int x = 0, y = 0;
        for (auto v : adj[u])
        {
            x += 1;
            y = deg[v] - 1;

            ans = min(ans, N - (1 + x + x * y));
        }

    }

    cout << ans << endl;

    return 0;
}

📌 F - Visible Buildings

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Counting Buildings

Warning

Hard Problems to Tackle Later

// TODO