🧩 AtCoder Beginner Contest 395

TayLockMarch 1, 2025About 4 min

🧩 AtCoder Beginner Contest 395

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
E	Shortest distance	Extended Dijkstra	🧠🔥
F	Binary Search	Binary Search	🔥

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 - Strictly Increasing?

#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);
    bool ans = true;
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];

        if (i >= 1 && A[i - 1] >= A[i])
        {
            ans = false;
        }
    }

    cout << (ans ? "Yes" : "No") << endl;

    return 0;
}

📌 B - Make Target

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    vector<string> grid(n, string(n, '#'));

    for (int i = 0; i < n; i++)
    {
        int j = n - 1 - i;

        if (i <= j)
        {
            for (int x = i; x <= j; x++)
            {
                for (int y = i; y <= j; y++)
                {
                    grid[x][y] = (i & 1) ? '.' : '#';
                }
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        cout << grid[i] << endl;
    }

    return 0;
}

📌 C - Shortest Duplicate Subarray

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    map<int, int> mp;
    int ans = n + 1;
    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num;

        if (mp.count(num))
        {
            ans = min(ans, i - mp[num] + 1);
        }
        else
        {
            mp[num] = i;
        }
    }

    cout << (ans == n + 1 ? -1 : ans) << endl;

    return 0;
}

📌 D - Pigeon Swap

#include <bits/stdc++.h>

using namespace std;

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

    int n, q;
    cin >> n >> q;

    vector<int> box_to_label(n), label_to_box(n), pigeon_to_box(n);
    iota(box_to_label.begin(), box_to_label.end(), 0);
    iota(label_to_box.begin(), label_to_box.end(), 0);
    iota(pigeon_to_box.begin(), pigeon_to_box.end(), 0);

    while (q--)
    {
        int op;
        cin >> op;

        if (op == 1)
        {
            int a, b;
            cin >> a >> b;
            a--;
            b--;

            pigeon_to_box[a] = label_to_box[b];
        }
        else if (op == 2)
        {
            int a, b;
            cin >> a >> b;
            a--;
            b--;

            swap(label_to_box[a], label_to_box[b]);
            swap(box_to_label[label_to_box[a]], box_to_label[label_to_box[b]]);
        }
        else
        {
            int a;
            cin >> a;
            a--;

            cout << box_to_label[pigeon_to_box[a]] + 1 << endl;
        }
    }

    return 0;
}

📌 E - Flip Edge

Extended Dijkstra

This problem can be solved by transforming the given graph into another graph, and finding the shortest distance on the new graph.

Consider a weighted directed graph with $2N$ vertices and $N + 2M$ edges specified as follows:

Correspongding to each edge $(u, v)$ in the given graph, there are an edge $(u, v)$ of weight 1 and edge $(v + N, u + N)$ of weight 1
There are an edge $(u, u + N)$ of weight $X$ and an edge $(u + N, v)$ of weight $X$
There are no other edges

The answer is the shortest distance from vertex $1$ to vertex $N$ or from vertex $1$ to vertex $2N$ , whichever is smaller

The vertices of this graph can be seen as representing the pairs(current vertex, the parity of the number of times the edges were flipped)

The problem can be solved fast enough by performing Dijkstra algorithm on it.

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<vector<pair<int, int>>> edges(2 * N);

    for (int i = 0; i < N; i++)
    {
        edges[i].push_back({i + N, X});
        edges[i + N].push_back({i, X});
    }

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

        edges[u].push_back({v, 1});
        edges[v + N].push_back({u + N, 1});
    }

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    pq.emplace(0, 0);

    vector<long long> dis(2 * N, 1e18);

    while (!pq.empty())
    {
        auto [distance, u] = pq.top();
        pq.pop();

        if (dis[u] < distance)
        {
            continue;
        }

        for (auto [v, cost] : edges[u])
        {
            if (dis[v] > distance + cost)
            {
                dis[v] = distance + cost;
                pq.emplace(dis[v], v);
            }
        }
    }

    cout << min(dis[N - 1], dis[2 * N - 1]) << endl;

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

    int n, m;
    long long X;
    cin >> n >> m >> X;

    vector<vector<int>> g0(n), g1(n);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        g0[u].push_back(v); // original graph
        g1[v].push_back(u); // reversed graph
    }

    vector<vector<long long>> dist(n, vector<long long>(2, 1e18));
    dist[0][0] = 0;

    // tuple<long long, int, int>: (cost, node, state)
    priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<>> pq;
    pq.emplace(0, 0, 0); // cost, node, state (0 = normal, 1 = reversed)

    while (!pq.empty())
    {
        auto [d, u, rev] = pq.top();
        pq.pop();

        if (d > dist[u][rev])
        {
            continue;
        }

        // traverse edges
        for (int v : (rev == 0 ? g0[u] : g1[u]))
        {
            if (dist[v][rev] > d + 1)
            {
                dist[v][rev] = d + 1;
                pq.emplace(dist[v][rev], v, rev);
            }
        }

        // flip state
        if (dist[u][rev ^ 1] > d + X)
        {
            dist[u][rev ^ 1] = d + X;
            pq.emplace(dist[u][rev ^ 1], u, rev ^ 1);
        }
    }

    long long ans = min(dist[n - 1][0], dist[n - 1][1]);

    cout << (ans == 1e18 ? -1 : ans) << '\n';

    return 0;
}

📌 F - Smooth Occlusion

Tips

When the final sum of the heights of upper and lower teeth $H$ is fixed, the total cost is $\sum_{i = 1}^{N}(U_i + D_i) - NH$ , independent of how the teeth are ground

Therefore, it's sufficient to find the maximum feasible $H$

Tips

If an $H$ is feasible, then any $H'$ with $H' < H$ is always feasible:

This can be achieved by starting from the state with the height sum $H$ , grinding the lower teeth as much as possible, and once it becomes impossible, grinding the upper teeth

Thus, if one can determine fast enough if a given $H$ is feasible, the problem can be solved by binary search

And note that an upper bound on $H$ is $H \le \min_i(U_i + D_i)$

check function

Now, let's implement the check function for a fixed $H$

Let $U_i'$ represent the final length of the upper tooth at position $i$ . There are two constraints that could apply for each $U_i'$ :

$\max(0, H - D_i) \le U_i' \le \min(H, U_i)$
$|U_{i - 1}' - U_i'| \le X$ , where ( $1 < i \le N$ )

If we let $l_i$ and $r_i$ represent the lower and upper bounds on $U_i'$ , it can be seen that:

$l_i = \max(0, H - D_i, l_{i - 1} - X)$
$r_i = \min(H, U_i, r_{i - 1} + X)$

Thus, the check function should accept $H$ if and only if $l_i \le r_i$ for all $i$

#include <bits/stdc++.h>

using namespace std;

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

    long long N, X;
    cin >> N >> X;

    vector<pair<long long, long long>> teeth(N);
    long long l = 0, r = 1e18;
    long long sum = 0;
    for (int i = 0; i < N; i++)
    {
        long long u, d;
        cin >> u >> d;

        sum += u + d;

        r = min(r, u + d);
        teeth[i] = {u, d};
    }

    r += 1;

    auto check = [&](long long H) -> bool
    {
        long long low = 0, high = H;

        for (auto [u, d] : teeth)
        {
            low = max(low - X, max(H - d, 0ll));
            high = min(high + X, min(H, u));
            if (low > high)
            {
                return false;
            }
        }

        return true;
    };

    while (l + 1 < r)
    {
        long long mid = l + (r - l) / 2;
        if (check(mid))
        {
            l = mid;
        }
        else
        {
            r = mid;
        }
    }

    cout << (sum - 1ll * N * l) << endl;

    return 0;
}

📌 G - Minimum Steiner Tree 2

Warning

Hard Problems to Tackle Later

// TODO