🧩 AtCoder Beginner Contest 397

# Info & Summary

• Date: 2025-03-15
• Completion Status: A ✅ / B ✅ / C ✅ / D ✅ / E ❌ / F ❌ / G ❌
• Problem Type:

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
C	Distinct elements	Prefix Sum/Suffix Sum	⭐🔥
D	Quadratic formula	Math/Binary Search	⭐
E	Subtree Size	DFS/Tree DP	🔥🛠️
F	Distinct elements	DP/Lazy Segment Tree	🌀🧠🛠️🔥
G	Maximize Distance	Binary Search/Max Flow	🌀

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

397A

// TayLock

#include <bits/stdc++.h>

using namespace std;

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

    double x;
    cin >> x;

    if (x >= 38.0)
    {
        cout << 1 << endl;
    }
    else if (x >= 37.5)
    {
        cout << 2 << endl;
    }
    else
    {
        cout << 3 << endl;
    }

    return 0;
}

📌 B - Ticket Gate Log

397B

// TayLock

#include <bits/stdc++.h>

using namespace std;

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

    string s, t;
    cin >> s;

    int ans = 0;
    char target = 'i';
    for (auto c : s)
    {
        if (c == target)
        {
            target = target == 'i' ? 'o' : 'i';
        } else {
            ans++;
        }
    }

    ans += target == 'o';

    cout << ans << endl;

    return 0;
}

📌 C - Variety Split Easy

397C

// TayLock

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    vector<int> a(n);
    map<int, int> cnt;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        cnt[a[i]]++;
    }

    set<int> s;
    int ans = 0;

    for (auto num : a)
    {
        s.insert(num);
        cnt[num]--;
        if (cnt[num] == 0)
        {
            cnt.erase(num);
        }

        if (!s.empty() && !cnt.empty())
        {
            ans = max(ans, int(s.size() + cnt.size()));
        }
    }

    cout << ans << endl;

    return 0;
}

Tips

• Let $l_i$ be the count of distinct elements in $(A_1, A_2, ..., A_i)$
• Let $R_i$ be the count of distinct elements in $(A_{i + 1}, ..., A_N)$

Then the answer is:

$$\max_{1 \le i \le N - 1}(L_i + R_i)$$

We use Prefix Sum and Suffix Sum to find the $L_i$ and $R_i$

// Better version

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

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

    vector<int> pre(n + 1), suf(n + 1);
    vector<int> cnt(n);
    for (int i = 0; i < n; i++)
    {
        pre[i + 1] = pre[i] + !cnt[A[i]];
        cnt[A[i]]++;
    }
    fill(cnt.begin(), cnt.end(), 0);
    for (int i = n - 1; i >= 0; i--)
    {
        suf[i] = suf[i + 1] + !cnt[A[i]];
        cnt[A[i]]++;
    }

    int ans = 0;
    for (int i = 1; i < n; i++)
    {
        ans = max(ans, pre[i] + suf[i]);
    }

    cout << ans << endl;

    return 0;
}

📌 D - Cubes

397D

Tips

By the constraints, $N > 0$, thus:

$$x^3 - y^3 = N \rightarrow y + 1 \le x \rightarrow (y + 1)^3 - y^3 = 3y^2 + 3y + 1 \le x^3 - y^3 = N \rightarrow y \le \sqrt{N}$$

Therefore, we can bruteforce all integers $k$ between $1$ and $\sqrt{N}$ to check is $k^3 + N$ is a cube number. If it is, then $(x, y) = (\sqrt[3]{k^3 + N}, k)$ is one of the solutions

Tips

Let $x - y = d$, then we have:

$$x^3 - y^3 = (x - y)(x^2 + xy + y^2) = d(x^2 + xy + y^2)$$

Also, since $x^2 + xy + y^2 \ge x^2 - 2xy + y^2 = d^2$, we have:

$$d^3 \le d(x^2 + xy + y^2) = x^3 - y^3 = N$$

Therefore, we have $d \le \sqrt[3]0{N}$

Thus, we can bruteforce all integers $d$ between $1$ and $\sqrt[3]{N}$ to check if there exists an integer $k$ with $(k + d)^3 - k^3 = d^3 = 3d^2k + 3dk^2 = N$. If it exists, then $(x, y) = (k + d, k)$ is one of the solutions

We can use quadratic formula or binary search to check:

$$3d^2k + 3dk^2 - N = 0$$

// Binary Search version
#include <bits/stdc++.h>

using namespace std;

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

    long long n;
    cin >> n;

    auto calc = [&](long long a, long long b, long long c)
    {
        // ax^2 + bx + c = 0
        long long l = 0, r = 6e9 + 1;
        while (r - l > 1)
        {
            long long mid = l + (r - l) / 2;
            if (a * mid * mid + b * mid + c <= 0)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }

        return a * l * l + b * l + c == 0 ? l : -1;
    };

    for (long long d = 1; d * d * d <= n; d++)
    {
        // (k+d)^3 - k^3 = d^3 + 3*d^2k + 3*d*k^2 = n
        if (n % d != 0)
        {
            continue;
        }

        // m = 3*k^2 + 3*dk + d^2
        long long m = n / d;
        long long k = calc(3, 3 * d, d * d - m);

        if (k > 0)
        {
            cout << k + d << " " << k << endl;
            return 0;
        }
    }

    cout << -1 << endl;

    return 0;
}

Details

#include <bits/stdc++.h>

using namespace std;

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

    long long n;
    cin >> n;

    for (long long d = 1; d * d * d <= n; d++)
    {
        if (n % d != 0)
        {
            continue;
        }

        long long p = n / d - d * d;
        if (p % 3 != 0)
        {
            continue;
        }

        p /= 3;

        long long x = (d + sqrt(d * d + 4 * p)) / 2 + 0.5;
        long long y = x - d;
        if (y > 0 && (__int128)(x)*x * x - (__int128)(y)*y * y == n)
        {
            cout << x << " " << y << endl;
            return 0;
        }
    }

    cout << -1 << endl;

    return 0;
}

📌 E - Path Decomposition of a Tree

397E

Tips

A tree T can be decomposed into paths only if every K-vertex subtree of T forms a path. Also, if T can be decomposed into paths, there always exists a K-vertex subtree

Tips

Thus, T can be decomposed into paths of and only if one can remove all the vertices by repeatedly performing the following operation:

• choose an arbitray K-vertex subtree, and remove it if it forms a path

This operation can be done fast with Tree DP. Regarding vertex 1 as the root, inspect the vertices from leaves, while managing the number of vertices $s_v$ in the subtree $T_v$ rooted at vertex $v$. First, compute $s_v$ as the sum of the values $s$ for the children of $v$, plus $1$. Then, we divide into cases:

• If $s_v < K$: it always hold that $v \neq 1$. As $s_v < K$, any subtree containing $v$ always contains entire $T_v$ and the parent of $v$.
  • If $c_v > 2$, then the degree of $v$ is $3$ or greater, so it can never form a path.
  • Thus, if $c_v \ge 2$, print No and terminate the program
• If $s_v > K$: there is no K-vertex subtree in $T_v$, so one cannot extract a path from $T_v$. Thus, print No ans terminate the program
• If $s_v = K$: $T_v$ must form a path.
  • If $c_v \ge 3$, then this is not a path, print No and terminate the program.
  • If $c_v \le 2$, then this subtree forms a path. Let $s_v \leftarrow 0$ to remove this subtree

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

    // store the size of the subtree rooted at each node
    vector<int> size(N * K, 1);
    // (node, parent, state)
    // node: current node
    // parent: parent node of the current node
    // state: whether the node is being visited for the first time (state == 0)
    // or after its children have been processed(state == 1)
    stack<tuple<int, int, int>> st;
    st.push({0, -1, 0});

    while (!st.empty())
    {
        auto [v, p, t] = st.top();
        st.pop();

        // being visited for the first time
        if (t == 0)
        {
            st.push({v, p, 1});
            for (int u : adj[v])
            {
                if (u != p)
                {
                    st.push({u, v, 0});
                }
            }
        }
        // after its children have been processed
        else
        {
            // cnt: tracks how many children have a non-zero size
            int cnt = 0;

            for (int u : adj[v])
            {
                if (u != p)
                {
                    // calculate the size of the subtree rooted at v
                    size[v] += size[u];
                    if (size[u] > 0)
                    {
                        cnt++;
                    }
                }
            }

            if (size[v] > K || cnt >= 3)
            {
                cout << "No" << endl;
                return 0;
            }
            if (size[v] < K && cnt >= 2)
            {
                cout << "No" << endl;
                return 0;
            }
            if (size[v] == K)
            {
                // indicating the subtree is complete
                size[v] = 0;
            }
        }
    }

    cout << "Yes" << endl;

    return 0;
}

Details

// Better version
#include <bits/stdc++.h>

using namespace std;

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

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

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

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

    auto dfs = [&](auto &&self, int u, int p = -1) -> int
    {
        int sum = 0;
        int cnt = 0;
        for (auto v : adj[u])
        {
            if (v == p)
            {
                continue;
            }
            int t = self(self, v, u);
            if (t == -1)
            {
                return -1;
            }
            if (t > 0)
            {
                cnt++;
                sum += t;
            }
        }

        if (cnt > 2)
        {
            return -1;
        }
        if (sum == K - 1)
        {
            return 0;
        }
        else if (cnt == 2)
        {
            return -1;
        }
        else
        {
            return sum + 1;
        }
    };

    if (dfs(dfs, 0) == 0)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

📌 F - Variety Split Hard

397F

Warning

Hard Problems to Tackle Later

#include <bits/stdc++.h>

using namespace std;

template <class Info, class Tag>
struct LazySegmentTree
{
    int n;
    // stores the information for each node: sum, maximum, minimum, etc
    vector<Info> info;
    // the pending updates for each segment
    // this could be an integer for addition or multiplication
    vector<Tag> tag;

    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info())
    {
        init(n_, v_);
    }

    template <class T>
    LazySegmentTree(vector<T> init_)
    {
        init(init_);
    }

    void init(int n_, Info v_ = Info())
    {
        init(vector(n_, v_));
    }

    template <class T>
    void init(vector<T> init_)
    {
        n = init_.size();
        info.assign(4 << __lg(n), Info());
        tag.assign(4 << __lg(n), Tag());

        // constructs the segment tree by recursively dividing the range
        // into subranges until it reaches individual elements
        function<void(int, int, int)> build = [&](int p, int l, int r)
        {
            if (r - l == 1)
            {
                info[p] = init_[l];
                return;
            }

            int mid = (l + r) / 2;
            build(2 * p, l, mid);
            build(2 * p + 1, mid, r);
            pull(p);
        };

        build(1, 0, n);
    }

    void pull(int p)
    {
        info[p] = info[2 * p] + info[2 * p + 1];
    }

    // applies the lazy update (represented by `Tag`) to a node and its children
    void apply(int p, const Tag &v)
    {
        info[p].apply(v);
        tag[p].apply(v);
    }

    // Propagates the pending updates down to its children
    // Once updates are pushed, it clears the lazy tag for the node
    void push(int p)
    {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }

    // modifies an element in the segment tree
    // It traverses down to the leaf and updates the node
    // It also propagates the modifications to the parent nodes after the update
    void modify(int p, int l, int r, int x, const Info &v)
    {
        if (r - l == 1)
        {
            info[p] = v;
            return;
        }

        int mid = (l + r) / 2;
        push(p);

        if (x < mid)
        {
            modify(2 * p, l, mid, x, v);
        }
        else
        {
            modify(2 * p + 1, mid, r, x, v);
        }
        pull(p);
    }

    void modify(int p, const Info &v)
    {
        modify(1, 0, n, p, v);
    }

    // queries the range [x, y) and returns the information (e.g., sum, max) for that range
    Info rangeQuery(int p, int l, int r, int x, int y)
    {
        if (l >= y || r <= x)
        {
            return Info();
        }
        if (l >= x && r <= y)
        {
            return info[p];
        }

        int mid = (l + r) / 2;
        push(p);

        return rangeQuery(2 * p, l, mid, x, y) + rangeQuery(2 * p + 1, mid, r, x, y);
    }

    Info rangeQuery(int l, int r)
    {
        return rangeQuery(1, 0, n, l, r);
    }

    // applies the update to a range of elements
    // It uses lazy propagation to apply updates efficiently across
    // large ranges, reducing redundant operations
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v)
    {
        if (l >= y || r <= x)
        {
            return;
        }
        if (l >= x && r <= y)
        {
            apply(p, v);
            return;
        }

        int mid = (l + r) / 2;
        push(p);

        rangeApply(2 * p, l, mid, x, y, v);
        rangeApply(2 * p + 1, mid, r, x, y, v);

        pull(p);
    }

    void rangeApply(int l, int r, const Tag &v)
    {
        return rangeApply(1, 0, n, l, r, v);
    }

    // find the first index that satisfies a condition (a predicate)
    template <class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred)
    {
        if (l >= y || r <= x)
        {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p]))
        {
            return -1;
        }
        if (r - l == 1)
        {
            return l;
        }

        int mid = (l + r) / 2;
        push(p);

        int res = findFirst(2 * p, l, mid, x, y, pred);
        if (res == -1)
        {
            res = findFirst(2 * p + 1, mid, r, x, y, pred);
        }

        return res;
    }

    template <class F>
    int findFirst(int l, int r, F &&pred)
    {
        return findFirst(1, 0, n, l, r, pred);
    }

    // find the last index that satisfies a condition (a predicate)
    template <class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred)
    {
        if (l >= y || r <= x)
        {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p]))
        {
            return -1;
        }
        if (r - l == 1)
        {
            return l;
        }

        int mid = (l + r) / 2;
        push(p);

        int res = findLast(2 * p + 1, mid, r, x, y, pred);
        if (res == -1)
        {
            res = findLast(2 * p, l, mid, x, y, pred);
        }

        return res;
    }

    template <class F>
    int findLast(int l, int r, F &&pred)
    {
        return findLast(1, 0, n, l, r, pred);
    }
};

// Represents an addition operation
struct Add
{
    int v = 0;
    void apply(const Add &a)
    {
        v += a.v;
    }
};

// Represents a maximum value operation
struct Max
{
    int v = 0;
    void apply(const Add &a)
    {
        v += a.v;
    }
};

// Operator Overloading
Max operator+(const Max &a, const Max &b)
{
    return {max(a.v, b.v)};
}

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

    int n;
    cin >> n;

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

    vector<int> pre(n + 1), suf(n + 1);
    vector<int> cnt(n);
    for (int i = 0; i < n; i++)
    {
        pre[i + 1] = pre[i] + !cnt[A[i]];
        cnt[A[i]]++;
    }
    fill(cnt.begin(), cnt.end(), 0);
    for (int i = n - 1; i >= 0; i--)
    {
        suf[i] = suf[i + 1] + !cnt[A[i]];
        cnt[A[i]]++;
    }

    vector<int> nxt(n, n);

    LazySegmentTree<Max, Add> seg(n + 1);

    int ans = 0;
    for (int l = n - 1; l >= 0; l--)
    {
        seg.modify(l, {suf[l]});
        seg.rangeApply(l + 1, nxt[A[l]] + 1, {1});
        nxt[A[l]] = l;

        ans = max(ans, pre[l] + seg.rangeQuery(0, n + 1).v);
    }

    cout << ans << endl;

    return 0;
}

📌 G - Maximize Distance

397G

Warning

Hard Problems to Tackle Later

// TODO