🧩 AtCoder Beginner Contest 383

TayLockDecember 7, 2024About 6 min

🧩 AtCoder Beginner Contest 383

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Math	linear sieve	🧠
E	Graph	DSU	🧠🌀
F	DP	DP	🌀
G	Divide and Conquer	Divide and Conquer & 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 - Humidifier 1

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    int ans = 0;
    int pre = 0;
    for (int i = 0; i < N; i++)
    {
        int t, v;
        cin >> t >> v;

        int d = t - pre;

        ans -= min(d, ans);
        ans += v;

        pre = t;
    }

    cout << ans << endl;

    return 0;
}

📌 B - Humidifier 2

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int h, w, d;
    cin >> h >> w >> d;

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

    int ans = 0;

    for (int i1 = 0; i1 < h; ++i1)
    {
        for (int j1 = 0; j1 < w; ++j1)
        {
            if (s[i1][j1] == '#')
                continue; // not a floor cell
            for (int i2 = 0; i2 < h; ++i2)
            {
                for (int j2 = 0; j2 < w; ++j2)
                {
                    if (s[i2][j2] == '#' || (i1 == i2 && j1 == j2))
                        continue; // non-floor cell, or coincides with one of the cells with humidifiers
                    int tmp = 0;
                    for (int i = 0; i < h; ++i)
                    {
                        for (int j = 0; j < w; ++j)
                        {
                            if (s[i][j] == '.' && (abs(i - i1) + abs(j - j1) <= d || abs(i - i2) + abs(j - j2) <= d))
                            {
                                tmp++; // humidified
                            }
                        }
                    }
                    ans = max(ans, tmp);
                }
            }
        }
    }

    cout << ans << endl;
}

📌 C - Humidifier 3

#include <bits/stdc++.h>

using namespace std;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

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

    int H, W, D;
    cin >> H >> W >> D;

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

    queue<tuple<int, int, int>> q;
    int ans = 0;

    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            if (grid[i][j] == 'H')
            {
                q.push({i, j, 0});
                grid[i][j] = '#';

                ans += 1;
            }
        }
    }

    while (!q.empty())
    {
        auto [x, y, d] = q.front();
        q.pop();

        for (int k = 0; k < 4; k++)
        {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (nx < 0 || ny < 0 || nx >= H || ny >= W)
            {
                continue;
            }
            if (grid[nx][ny] == '#')
            {
                continue;
            }
            if (d >= D)
            {
                continue;
            }

            q.push({nx, ny, d + 1});
            grid[nx][ny] = '#';

            ans += 1;
        }
    }

    cout << ans << endl;

    return 0;
}

📌 D - 9 Divisors

#include <bits/stdc++.h>

using namespace std;

// smallest prime factor
vector<int> minp;
// the list of all primes
vector<int> primes;
vector<int> pi;

bool isprime(int n)
{
    return minp[n] == n;
}

// linear sieve
// recording for every n its smallest prime factor minp[n], and collecting the list of all primes into primes
void sieve(int n)
{
    minp.assign(n + 1, 0);
    primes.clear();

    for (int i = 2; i <= n; i++)
    {
        if (minp[i] == 0)
        {
            minp[i] = i;
            primes.push_back(i);
        }

        for (auto p : primes)
        {
            if (i * p > n)
            {
                break;
            }

            minp[i * p] = p;
            if (p == minp[i])
            {
                break;
            }
        }
    }

    // prefix array
    // how many primes <= x ?
    pi.resize(n + 1);
    for (int i = 1; i <= n; i++)
    {
        pi[i] = pi[i - 1] + isprime(i);
    }
}

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

    long long N;
    cin >> N;

    sieve(2e6);

    long long ans = 0;
    long long sqrtn = sqrt(N);
    for (long long x : primes)
    {
        if (x * x > sqrtn)
        {
            break;
        }

        if (x * x * x * x <= sqrtn)
        {
            ans++;
        }

        ans += pi[sqrtn / x] - pi[x];
    }

    cout << ans << endl;

    return 0;
}

📌 E - Sum of Max Matching

Tips

$f(x, y)$ equals the minimum $w$ such that vertices $x$ and $y$ are connected in the subgraph consisting of the edges with weights less than or equal to $w$

Thus, for three distinct vertices $x, y, z$ , if $f(x, y) \le f(x, z)$ , then $f(x, z) = f(y, z)$

This This implies that if two vertices $x$ and $y$ are connected via edges of weight no greater than $w$ , then any vertex $z$ that is disconnected in the graph satisfies $f(x, z) = f(y, z)$

Tips

Also, instead of rearranging B, this problem can be considered as a matching problem between the elements in A and the elements in B

Assume that the edges are sorted in ascending order of their weights, satisfying $w_1 \le w_2 \le ... \le w_M$

Initially, there is a graph with $N$ vertices and no edges. We manage whether each vertex is contained in A, and whether it is in B
For each $i = 1, 2, ..., M$ $i = 1, 2, ..., M$ in order, do the following:
- If vertices $u_i$ and $v_i$ are disconnected, add edge ${u_i, v_i}$ to the graph. If it is connected, go to the next edge
- If the addition made two different connected components connected, repeatedly match the vertices of A contained in one connected component with the vertices of B contained in the other as many times as possible
- Add $w_i$ the number of new matches
- Update the vertices of A and B remaining in that connected component

#include <bits/stdc++.h>

using namespace std;

// DSU - Compact Version
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, M, K;
    cin >> N >> M >> K;

    // current weight at which this component was formed
    vector<long long> wt(N);
    vector<tuple<int, int, int>> edges(M);

    for (int i = 0; i < M; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;

        edges[i] = {w, --u, --v};
    }

    sort(edges.begin(), edges.end());

    // net surplus of unmatched A/B in the component
    vector<int> c(N);
    for (int i = 0; i < K; i++)
    {
        int A;
        cin >> A;
        A--;

        c[A]++;
    }
    for (int i = 0; i < K; i++)
    {
        int B;
        cin >> B;
        B--;

        c[B]--;
    }

    DSU dsu(N);
    long long ans = 0;

    for (auto [w, u, v] : edges)
    {
        u = dsu.find(u);
        v = dsu.find(v);

        if (u != v)
        {
            ans += 1ll * abs(c[u]) * (w - wt[u]);
            ans += 1ll * abs(c[v]) * (w - wt[v]);

            wt[u] = w;
            c[u] += c[v];

            dsu.merge(u, v);
        }
    }

    ans /= 2;

    cout << ans << endl;

    return 0;
}

📌 F - Diversity

Tips

Define dp[c][p] the maximum satisfaction when buying products with color $c$ or less for $p$ yen or less

The final answer is the maximum value among $dp[N][0], dp[N][1], ..., dp[N][X]$

Tips

When we already know $dp[c - 1]$ and want to find $dp[c]$ , we inspect the products of color $c$ one by one to update $dp[c]$ as follows:

When inspecting product $j$ , we set $dp[c][p] = max({dp[c - 1][p - P_j] + U_j + K, dp[c][p - P_j] + U_j, dp[c][p]})$ for each $p = X, X - 1, ..., P_j$ in this order
When these updates are done for all products of color $c$ , we have $dp[c][i]$ the maximum satisfaction when buying products with color $c$ or less for $p$ yen or less, where at least one product of color $c$ is chosen
Finally, we set $dp[c][p] = max(dp[c][i], dp[c - 1][p])$ , so that $dp[c][p]$ stores the maximum satisfaction when buying products with color $c$ or less for $p$ yen or less

#include <bits/stdc++.h>

using namespace std;

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

    int n, x, k;
    cin >> n >> x >> k;

    vector<int> p(n);
    vector<long long> u(n), c(n);
    for (int i = 0; i < n; i++)
    {
        cin >> p[i] >> u[i] >> c[i];
    }

    vector<vector<int>> id(n);
    for (int i = 0; i < n; i++)
    {
        id[c[i] - 1].push_back(i);
    }

    vector<vector<long long>> dp(n + 1, vector
    <long long>(x + 1, -2e18));
    dp[0][0] = 0;

    for (int i = 0; i < n; i++)
    {
        for (auto idx : id[i])
        {
            for (int j = x; j >= p[idx]; j--)
            {
                if (dp[i][j - p[idx]] != -2e18)
                {
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - p[idx]] + u[idx] + k);
                }
                if (dp[i + 1][j - p[idx]] != -2e18)
                {
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i + 1][j - p[idx]] + u[idx]);
                }
            }
        }

        for (int j = 0; j <= x; j++)
        {
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
        }
    }

    cout << *max_element(dp[n].begin(), dp[n].end()) << endl;

    return 0;
}

// Better version

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<array<int, 3>> item(N);
    for (int i = 0; i < N; i++)
    {
        int p, u, c;
        cin >> p >> u >> c;

        item[i] = {c, p, u};
    }
    // grouped by color
    sort(item.begin(), item.end());

    // f[p]: dp from the previous color group
    // g[p]: dp for the current color group
    vector<long long> f(X + 1), g(X + 1);
    int lst = -1;

    for (auto [c, p, u] : item)
    {
        // a new color group
        if (c != lst)
        {
            f = g;
        }

        // When processing color group c, for each item j in this group
        for (int i = X; i >= p; i--)
        {
            g[i] = max({g[i],               // Don't take this item
                        g[i - p] + u,       // Take this item normally (same color group)
                        f[i - p] + u + K}); // First item from this color group — get bonus!

            lst = c;
        }
    }

    cout << max(f[X], g[X]) << endl;

    return 0;
}

📌 G - Bar Cover

Warning

Hard Problems to Tackle Later

// TODO