🧩 AtCoder Beginner Contest 392

TayLockFebruary 8, 2025About 5 min

🧩 AtCoder Beginner Contest 392

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Math	Math	⭐
E	Connected component	DSU/DFS/BFS	🔥🛠️
F	Constructive	Fenwick 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 - Shuffled Equation

#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());

    cout << (a[0] * a[1] == a[2] ? "Yes" : "No") << endl;

    return 0;
}

📌 B - Who is Missing?

#include <bits/stdc++.h>

using namespace std;

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

    int n, m;
    cin >> n >> m;

    set<int> s;
    for (int i = 1; i <= n; i++)
    {
        s.insert(i);
    }

    for (int i = 0; i < m; i++)
    {
        int a;
        cin >> a;

        s.erase(a);
    }

    cout << s.size() << endl;

    for (auto a : s)
    {
        cout << a << " ";
    }

    return 0;
}

📌 C - Bib

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

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

    vector<int> ans(n);
    for (int i = 0; i < n; i++)
    {
        ans[q[i]] = q[p[i]];
    }

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

    return 0;
}

📌 D - Doubles

Let $S = \sum_{i}K_i$

First, prepare the following associative array for each die $i$ :

$Cnt_i[X]$ : the number of faces on die $i$ with $X$ written on them

How can we find the probability that two dice $i$ and $j$ show the same value?

It is sufficient to find for each face value $X$ of die $i$ , how many faces with $X$ die $j$ has. Thus, the associative array $Cnt_j$ enables us to find it in $O(K_i \log (K_j))$ time

Thus, by enumerating all pairs of dice, the answer can be found in a total of $\sum_{i, j}O(K_i \log(K_j)) = O(NS \log (S))$ time

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    vector<vector<int>> A(n);

    for (int i = 0; i < n; i++)
    {
        int k;
        cin >> k;
        A[i].resize(k);

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

    double ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            // two dice $i$ and $j$ show the same value
            long long cnt = 0;
            for (int x = 0, l = 0, r = 0; x < A[i].size(); x++)
            {
                while (l < A[j].size() && A[j][l] < A[i][x])
                {
                    l++;
                }
                while (r < A[j].size() && A[j][r] <= A[i][x])
                {
                    r++;
                }

                cnt += r - l;
            }

            ans = max(ans, 1.0 * cnt / (A[i].size() * A[j].size()));
        }
    }

    cout << fixed << setprecision(15) << ans << endl;

    return 0;
}

📌 E - Cables and Servers

Tips

Consider the graph where the servers are the vertices and the cables are the edges

For each connected component, find the vertices that belongs to it, and the “excessive” edges:

This can be done with DFS (Depth-First Search) or BFS (Breadth-First Search), or a data structure like DSU (Disjoint Set Union)

Modifying one end of an “excessive” edge always reduces the number of connected components. Conversely, no matter how the edges are modified, the number of connected component changes by at most one

Thus, repeating this modification minimizes the number of operations required

#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;
    cin >> n >> m;

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

    DSU dsu(n);

    // track which edges are already used in connecting components
    vector<bool> vis(m, false);
    // the minimum number of operations required to connect all components
    // a connected graph has exactly `n-1` edges
    int ans = n - 1;

    for (int i = 0; i < m; i++)
    {
        if (dsu.merge(A[i], B[i]))
        {
            vis[i] = true;
            ans--;
        }
    }

    cout << ans << endl;
    for (int i = 0, j = 0; i < m && ans > 0; i++)
    {
        // After processing all edges, some edges may still not have been used
        // (i.e., vis[i] = false)
        if (!vis[i])
        {
            // find the next available server j
            while (dsu.same(j, A[i]))
            {
                j++;
            }

            // connect it using the current edge (A[i], j)
            cout << i + 1 << " " << B[i] + 1 << " " << j + 1 << endl;
            dsu.merge(A[i], j);

            ans--;
        }
    }

    return 0;
}

📌 F - Insert

Considering the operations in reverse order works

Problem *:

For $i = N, N - 1, ..., 1$ $i = N, N - 1, ..., 1$ in order, perform the following operation against $A' = (1, 2, ..., N)$ $A^{'} = (1, 2, ..., N)$
- Operation: remove the $P_i$ -th element from $A'$ to obtain a new array shorter than one element
Find $B_i$ : the number removed in each step

Define: $T[i] = 1$ if $i$ is contained in $A'$ and $0$ otherwise

Since $A'$ is always monotonically increasing throughout the procedure, so the $p$ -th element of $A'$ is the smallest $x$ with $\sum_{i = 1} ^{x}(T[i] = p)$ . Thus, it can be found fast if we can perform binary search over the cumulative sums of $T$

Removing the value $i$ from $A'$ corresponds to setting $T[i]$ to $0$

Tips

It can be solved fast with a data structure that supports element-wise update and segment-wise sum retrieval - which is realized with a Fenwick Tree or Segment Tree

Thus, the problem can be solved in a total of $O(N\log(N))$ time

Let $A = (A_1, A_2, ..., A_N)$ be the answer to the original problem, that is, the sequence after the procedure

Tips

$B_i$ intuitively represents the final position of the number inserted for the $i$ -th time in the original problem

This implies $A_{B_i} = i$ , so once Problem * is solved, the answer can be found in $O(N)$ time

#include <bits/stdc++.h>

using namespace std;

template <typename T>
struct Fenwick
{
    int n;
    vector<T> a;

    Fenwick(int n_ = 0)
    {
        init(n_);
    }

    void init(int n_)
    {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v)
    {
        for (int i = x + 1; i <= n; i += i & -i)
        {
            a[i - 1] = a[i - 1] + v;
        }
    }

    T sum(int x)
    {
        T ans{};
        for (int i = x; i > 0; i -= i & -i)
        {
            ans = ans + a[i - 1];
        }
        return ans;
    }

    T rangeSum(int l, int r)
    {

        return sum(r) - sum(l);
    }

    int select(const T &k)
    {

        int x = 0;

        T cur{};

        for (int i = 1 << __lg(n); i; i /= 2)
        {
            if (x + i <= n && cur + a[x + i - 1] <= k)
            {
                x += i;
                cur = cur + a[x - 1];
            }
        }

        return x;
    }
};

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

    int n;
    cin >> n;

    Fenwick<int> fen(n);
    for (int i = 0; i < n; i++)
    {
        // Initialize Fenwick Tree with 1's (all positions available)
        fen.add(i, 1);
    }

    vector<int> P(n);
    for (int i = 0; i < n; i++)
    {
        cin >> P[i];
        P[i]--;
    }

    vector<int> A(n);
    for (int i = n - 1; i >= 0; i--)
    {
        // Select the P[i]-th available position and assign the current number
        int x = fen.select(P[i]);
        A[x] = i; // Store the current number at the found position

        // Mark the position as filled in the Fenwick Tree
        fen.add(x, -1);
    }
    for (int i = 0; i < n; i++)
    {
        cout << A[i] + 1 << " \n"[i == n - 1];
    }

    return 0;
}

📌 G - Fine Triplets

Warning

Hard Problems to Tackle Later

// TODO