🧩 AtCoder Beginner Contest 400

TayLockApril 5, 2025About 9 min

🧩 AtCoder Beginner Contest 400

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
C	Binary Search	Binary Search	⭐🛠️🔥
D	0-1 BFS	0-1 BFS	⭐🛠️🔥
E	Linear Sieve	Linear Sieve	⚠️
F	DP	Range DP	🔥
G	DP	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 - ABC400 Party

// TayLock

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    if (400 % n == 0)
    {
        cout << 400 / n << endl;
    }
    else
    {
        cout << -1 << endl;
    }

    return 0;
}

📌 B - Sum of Geometric Series

// TayLock

#include <bits/stdc++.h>

using namespace std;

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

    long long n;
    int m;
    cin >> n >> m;

    long long ans = 0;
    for (int i = 0; i <= m; i++)
    {
        ans += pow(n, i);

        if (ans > 1e9)
        {
            cout << "inf" << endl;
            return 0;
        }
    }

    cout << ans << endl;

    return 0;
}

📌 C - 2^a b^2

Since the function $2^a$ grows very quickly, we can consider enumerating values of $a$ and calculate the valid ranges of $b$ accordingly

So, if we fix a value of $a$ , we can move $2^a$ to the right-hand side:

1 \le b^2 \le \frac{n}{2^a}

As $b^2$ increases with $b$ , we can binary search to find the maximum valid $b$

We can further optimize the step, take the square root on both sides gives:

1 \le b \le \sqrt{\frac{n}{2^a}}

So the number of valid $b$ is:

\left\lfloor \sqrt{\frac{n}{2^a}} \right\rfloor

// TayLock

#include <bits/stdc++.h>

using namespace std;

long long isqrt(long long n)
{
    long long x = sqrt(n);
    if (x * x > n)
    {
        x--;
    }
    return x;
}

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

    long long n;
    cin >> n;

    cout << isqrt(n / 2) + isqrt(n / 4) << endl;

    return 0;
}

📌 D - Takahashi the Wall Breaker

For each coordinate point on the grid, enumerate the positions it can move to:

Move to adjacent position(up, down, left, right) that are within the town and road tiles: for each point, there are at most $4$ such valid positions. Simply brute-force enumerate these points and connect them with edges of weight $0$
Choose one of the four directions(up, down, left, right) and perform a forward kick: for each point, ther are at most $8$ such valid positions. Again, brute-force enumerate these points and connect them with edegs of weight $1$

It is easy to observe that the answer is the shortest path distance from (A, B) to (C, D) on this graph. Since the graph only contains edegs with weight $0$ and $1$ , we can use 0-1 BFS to solve the problem in $O(HW)$ time

Tips

0-1 BFS is basically equivalent to Dijkstra algorithm, except that we use a deque instead of a priority queue by exploiting the property that tentative distances of vertices that are inserted to the deque differ at most by one, enabling us to solving the original problem in a total of $O(HW)$ time

// TayLock

#include <bits/stdc++.h>

using namespace std;

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

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

    int h, w;
    cin >> h >> w;

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

    int a, b, c, d;
    cin >> a >> b >> c >> d;
    a--;
    b--;
    c--;
    d--;

    vector<vector<int>> dis(h, vector<int>(w, 1e9));
    dis[a][b] = 0;

    deque<array<int, 3>> q;
    q.push_back({0, a, b});

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

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

            if (nx < 0 || nx >= h || ny < 0 || ny >= w)
            {
                continue;
            }

            // weight 0
            if (grid[nx][ny] == '.')
            {
                if (dis[nx][ny] > d)
                {
                    dis[nx][ny] = d;
                    q.push_front({d, nx, ny});
                }
            }
            // weight 1
            else
            {
                if (dis[nx][ny] > d + 1)
                {
                    dis[nx][ny] = d + 1;
                    q.push_back({d + 1, nx, ny});
                }
            }

            nx += dx[k];
            ny += dy[k];

            if (nx < 0 || nx >= h || ny < 0 || ny >= w)
            {
                continue;
            }
            // weight 1
            if (dis[nx][ny] > d + 1)
            {
                dis[nx][ny] = d + 1;
                q.push_back({d + 1, nx, ny});
            }
        }
    }

    cout << dis[c][d] << endl;

    return 0;
}

// Better version

#include <bits/stdc++.h>

using namespace std;

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

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

    int h, w;
    cin >> h >> w;

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

    int a, b, c, d;
    cin >> a >> b >> c >> d;
    a--;
    b--;
    c--;
    d--;

    vector<vector<int>> dis(h, vector<int>(w, -1));
    deque<array<int, 3>> q;
    q.push_back({0, a, b});

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

        if (dis[x][y] != -1)
        {
            continue;
        }
        dis[x][y] = d;

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

                if (nx < 0 || nx >= h || ny < 0 || ny >= w)
                {
                    continue;
                }

                // weight 0
                if (s == 1 && grid[nx][ny] == '.')
                {
                    q.push_front({d, nx, ny});
                }
                // weight 1
                else
                {
                    q.push_back({d + 1, nx, ny});
                }
            }
        }
    }

    cout << dis[c][d] << endl;

    return 0;
}

🥇 Why better:

We only process each cell once, and we assign the shortest possible cost to reach that cell
- we might push the same cell multiple times with different costs, which can lead to redundant computation, or even infinite loops in cyclic graphs

    // once you visit a cell with the minimum cost, you never need to revisit it
    // because deque guarantees that any later visit will have equal or worse cost
    if (dis[x][y] != -1)
    {
        continue;
    }

    // sets the minimum cost to reach cell (x, y), we only do this once
    dis[x][y] = d;

📌 E - Ringo's Favorite Numbers 3

The condition for a 400 number is equivalent to that $N$ is a square number

Since there are only $10^6$ square numbers not greater than $10^12$ , so we will check each of them whether it is a 400 number to enumerate 400 numbers

The number of distinct prime factors of $k = 1, 2, 3, ..., 10^6$ can be found in the same manner as Eratosthenes' sieve:

Initialize a sequence $V = (V_1, V_2, ..., V_{10^6})$ with $0$
For each prime $p$ not greater than $10^6$ , add $1$ to $V_i$ for every $i$ that is a multiple of $p$
Then the final $V_i$ is the number of distinct prime factors of $i$

Once we enumerate all the 400 numbers not greater than $10^12$ , one can perform a binary search against the sorted list of the 400 numbers to find the maximum 400 numbers less than or equal to $A$

#include <bits/stdc++.h>

using namespace std;

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

    int A = 1e6 + 1;
    vector<int> v(A);

    // Eratosthenes’ sieve
    // Then the final V_i is the number of distinct prime factors of i
    for (int i = 2; i < A; i++)
    {
        if (v[i] == 0)
        {
            for (int j = i; j < A; j += i)
            {
                v[j]++;
            }
        }
    }

    // generate all valid 400 numbers
    vector<long long> vec;
    for (long long i = 2; i < A; i++)
    {
        if (v[i] == 2)
        {
            vec.push_back(i * i);
        }
    }

    int q;
    cin >> q;

    while (q--)
    {
        long long a;
        cin >> a;

        // binary search
        cout << *prev(upper_bound(vec.begin(), vec.end(), a)) << endl;
    }

    return 0;
}

// Better version

#include <bits/stdc++.h>

using namespace std;

// minp[i]: the smallest prime dividing i
// primes: list of all primes <= n
// np[i]: number of distinct prime factrs f i
// lst[i]: the largest integer <= i that has exactly 2 distinct prime factors
vector<int> minp, primes, np, lst;

// linear sieve
void sieve(int n)
{
    minp.assign(n + 1, 0);
    primes.clear();
    np.assign(n + 1, 0);

    for (int i = 2; i <= n; i++)
    {
        // find a prime
        if (minp[i] == 0)
        {
            // one prime factor: itself
            minp[i] = i;
            np[i] = 1;

            primes.push_back(i);
        }

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

            minp[i * p] = p;

            // muliplying by a repeated prime
            if (p == minp[i])
            {
                np[i * p] = np[i];
            } else {
                // it's a new prime
                np[i * p] = np[i] + 1;
            }

        }
    }

    // prefix max array
    lst.resize(n + 1);
    for (int i = 1; i <= n; i++)
    {
        lst[i] = np[i] == 2 ? i : lst[i - 1];
    }
}

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

    sieve(1e6);

    int q;
    cin >> q;

    while (q--)
    {
        long long a;
        cin >> a;

        a = sqrt(a);
        a = lst[a];
        a *= a;

        cout << a << endl;
    }

    return 0;
}

🥇 Why better:

Linear sieve(sieve function):
- Finds all prime numbers up to $n$
- Computes the number of distinct prime factors of each number $i$ as np[i]
- Builds a lookup array lst[i], which for each $i$ , stores the largest number $\le i$ such that np[i] == 2(i.e., $i$ has exactly $2$ distinct prime factors)

📌 F - Happy Birthday! 3

Considering the operation in reverse order, the problem can be rephrased as follows:

Info

Each piece $i$ is initially painted in color $C_i$ . Find the minimum total cost required to make all pieces to have color 0 by repeating the following operation:

Choose $a, b, c$ such that each of the pieces $a, a + 1, ..., a + b - 1$ have color 0 or c(i.e., we want $C_i \rightarrow 0$ )
Paint the pieces $a, a + 1, ..., a + b - 1$ in color 0 for a cost $b + X_c$

Why no operation can overlap with a previously painted segment?

If we could overlap operations, we could re-paint slices with conflicting colors, causing confusion and making it harder to determine the minimum cost needed to reach the target color configuration

We may assume that piece $a$ and $a + b - 1$ is always painted in color $c$

Tips

Otherwise, the required cost is reduced by shrinking the segment

Understanding the operation cost: the cost of painting a segment of the cake is determined by two factors
- The length $b$ of the segment being painted(i.e., how many slices we affect)
- The coloring cost $X_C$ which is associated with the color we choose for the segment

The key idea is to divide the circular problem into smaller sequential problems using Dynamic Programming (DP). Here's how it works::

Suppose the last operation we performed was on the slices from $a$ to $a + b - 1$ and painted these slices with color $c$ . After this operation, these slices $a, a + 1, ..., a + b - 1$ are locked into color $c$ , meaning that no subsequent operation can affect these slices
Since the slices from $a$ $a$ to $a + b - 1$ $a + b - 1$ are already painted, they do not interfere with the left or right parts. Then we can divide the problem into two independent parts:
- Left side: The slices before $a$ (from slice $1$ to $a - 1$ )
- Right side: The slices after $a + b - 1$ (from slice $a + b$ to $N$ )
- We can use dynamic programming independently compute the minimum cost to color the left and right segments, and then combine the results to get the total cost
The minimum cost to color slices from $a$ $a$ to $a + b − 1$ $a + b - 1$ with color 0 (and the rest of the cake with color 0) can be found as the sum of:
- The minimum cost to color slices $a, a + 1, ..., a + b - 1$ with color 0
- The minimum cost to color all the other slices(i.e., the left and right part) independently

Important

Define dp[l,r] as the minimum cost required to color slices from $l$ to $r - 1$ , such that the last operation involved coloring the slices $l, l + 1, ..., r - 1$ . For each pair of subproblems, we need to compute the minimum cost recursively by considering all possible last positions and dividing the problem

DP transition:

First, suppose that the last operation was performed against pieces $l, l + 1, ..., r - 1$ $l, l + 1, ..., r - 1$
- Let's say the last operation was performed against pieces $l', l' + 1, ..., r' - 1$ , and $l \neq l'$ or $r \neq r'$
- if $l \neq l'$ , then $l, l + 1, ..., l' - 1$ and $l', l' + 1, ..., r - 1$ can be considered independently
- if $r \neq r'$ , then $l, l + 1, ..., r' - 1$ and $r', r' + 1, ..., r - 1$ can be considered independently
- Therefore the minimum cost for this case is the minimum value of $dp_{l, m} + dp_{m, r}$ for $m$ with $l < m < r$
Next, suppose that the last operation was performed against pieces $l, l + 1, ..., r - 1$ $l, l + 1, ..., r - 1$ , the sought cost is the minimum cost required to make each of pieces $l, l + 1, ..., r - 1$ $l, l + 1, ..., r - 1$ color 0 of color $C_l$ $C_{l}$ , plus $r - l + X_{C_l}$ $r - l + X_{C_{l}}$ , note that piece $l$ $l$ remains color $C_l$ $C_{l}$
- make piece $r - 1$ color $0$ : $dp_{l, r} = min(dp_{l, r}, min(dp_{l, m} + dp_{m, r}))$
- make piece $r - 1$ color $C_l$ : $dp_{l, r} = min(dp_{l, r}, dp_{l, r - 1})$ if $C_{r - 1} = C_l$
The final answer can be found as $\min_{0 \le i < N}{dp_{i, N + i}}$

#include <bits/stdc++.h>

using namespace std;

void chmin(long long &a, long long b)
{
    if (a > b)
    {
        a = b;
    }
}

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

    int n;
    cin >> n;

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

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

    vector<vector<long long>> dp(n, vector<long long>(n, LONG_LONG_MAX));
    vector<vector<long long>> f(n, vector<long long>(n, LONG_LONG_MAX));
    for (int len = 1; len <= n; len++)
    {
        for (int l = 0; l < n; l++)
        {
            int r = (l + len - 1) % n;

            // recursively calculate the cost of coloring the left and right subsegments and combine their results to update dp[l][r] with the minimum cost.
            for (int x = 1; x < len; x++)
            {
                int m = (l + x - 1) % n;

                chmin(dp[l][r], dp[l][m] + dp[(m + 1) % n][r]);
            }

            // If we find that the slices `l` and `r` are the same color, we can reuse previously computed results for smaller subproblems (smaller segments) where the endpoints also have the same color.
            if (c[l] == c[r])
            {
                if (len <= 2)
                {
                    f[l][r] = 0;
                }
                else
                {
                    // the color of `l` and `r` are same, do not need to change
                    // then shrink the segment from [l, r] to [l + 1, r - 1]
                    chmin(f[l][r], dp[(l + 1) % n][(r + n - 1) % n]);
                }

                for (int m = l;; m = (m + 1) % n)
                {
                    if (c[l] == c[m])
                    {
                        chmin(f[l][r], f[l][m] + f[m][r]);
                    }
                    if (m == r)
                    {
                        break;
                    }
                }

                chmin(dp[l][r], f[l][r] + len + x[c[l]]);
            }
        }
    }

    long long ans = LONG_LONG_MAX;
    for (int i = 0; i < n; i++)
    {
        chmin(ans, dp[i][(i + n - 1) % n]);
    }

    cout << ans << endl;

    return 0;
}

📌 G - Patisserie ABC 3

Warning

Hard Problems to Tackle Later

// TODO