🧩 AtCoder Beginner Contest 374

TayLockOctober 5, 2024About 5 min

🧩 AtCoder Beginner Contest 374

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	bitmask	DFS	⭐🔥
E	maximize the minimum value	Binary Search	🧠
F	DP	DP	🌀
G	Graph		🌀

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 - Takahashi san 2

#include <bits/stdc++.h>

using namespace std;

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

    string S;
    cin >> S;

    cout << (S.substr(S.size() - 3, 3) == "san" ? "Yes" : "No") << endl;

    return 0;
}

📌 B - Unvarnished Report

#include <bits/stdc++.h>

using namespace std;

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

    string S, T;
    cin >> S >> T;

    if (S == T)
    {
        cout << 0 << endl;
        return 0;
    }

    if (S.size() > T.size())
    {
        swap(S, T);
    }

    int N = S.size();
    for (int i = 0; i < N; i++)
    {
        if (S[i] != T[i])
        {
            cout << i + 1 << endl;
            return 0;
        }
    }

    cout << N + 1 << endl;

    return 0;
}

📌 C - Separated Lunch

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    vector<long long> K(N);
    long long sum = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> K[i];

        sum += K[i];
    }

    long long ans = 1e18;

    for (int mask = 0; mask < 1 << N; mask++)
    {
        long long a = 0;

        for (int i = 0; i < N; i++)
        {
            if (mask & 1 << i)
            {
                a += K[i];
            }
        }

        ans = min(ans, max(a, sum - a));
    }

    cout << ans << endl;

    return 0;
}

📌 D - Laser Marking

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    int S, T;
    cin >> S >> T;

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

    vector<bool> vis(N);
    double ans = 1e9;

    auto dfs = [&](auto &&self, int x, int y, double sum, int c) -> void
    {
        if (c == N)
        {
            ans = min(ans, sum);
            return;
        }

        for (int i = 0; i < N; i++)
        {
            if (vis[i])
            {
                continue;
            }

            double d1 = hypot(A[i] - x, B[i] - y);
            double d2 = hypot(C[i] - x, D[i] - y);
            double d0 = hypot(A[i] - C[i], B[i] - D[i]);

            vis[i] = true;
            self(self, A[i], B[i], sum + d2 / S + d0 / T, c + 1);
            self(self, C[i], D[i], sum + d1 / S + d0 / T, c + 1);
            vis[i] = false;
        }
    };

    dfs(dfs, 0, 0, 0.0, 0);

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

    return 0;
}

📌 E - Sensor Optimization Dilemma 2

Tips

This problem can be solved with the binary search approach. Consider the following decision problem:

If the budget is $w$ yen, can we achieve a production capacity of at least $w$ ?

To solve this problem, it is sufficient to find the minimum amount of money to have $W_i \ge w$ for all $i$ . From now on, we will consider the following problem:

How much money is required to process at least $w$ products in process $i$ ?

Tips

Actually, we have the following fact:

For a way to buy machine with minimum amount of money to process at least $w$ $w$ products in process $i$ $i$ , at least one of the following is true:
- $S_i$ is introduced $A_i$ products or less
- $T_i$ is introduced $B_i$ products or less

Proof: The conjecture is equivalent to:

In an optimal solution, at least one of the machine $S_i$ or $T_i$ has a capacity to process $A_iB_i$ products or less

$B_i$ instances of machine $S_i$ and $A_i$ instances of machine $T_i$ are both capable of processing $A_iB_i$ products. Since they are interchangeable, we may repeatedly substitute one set for another, whichever is cheaper, as many times as possible

Based on this fact, one can brute-force the number of machine $S_i$ up to $B_i$ , and the number of machine $T_i$ up to $A_i$ to solve it in $O(A_i + B_i)$ time

Tips

Let us go back to the original problem, which can be solved in the following outline:

Do binary search over the answer $w$ $w$ to this problem
- For each $i = 1, 2, ..., N$ , find the minimum amount of money required to have $W_i \ge w$
- It their sum does not exceed $X$ , the answer if $w$ or greater; otherwise, the answer is less than $w$

The time complexity is $O(N(A_i + B_i) \log (X(A_i + B_i)))$

ceiling division trick

A classic ceiling division trick used in integer arithmetic to compute the minimum number of machines required to cover a certain number of products

if (need > 0)
{
    // a classic "ceiling division" trick
    cur += 1ll * (need + A[i] - 1) / A[i] * P[i];
}

We need:

\lceil \frac{need}{A[i]} \rceil

// integer division truncates (floor division), we can't write:
need / A[i]

// Instead, we use:
(need + A[i] - 1) / A[i]

Then multiply by $P[i]$ tp compute the cost of the $S_i$ machines needed to cover the remaining need products

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<int> A(N), B(N), P(N), Q(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i] >> P[i] >> B[i] >> Q[i];

        if (A[i] * Q[i] < B[i] * P[i])
        {
            swap(A[i], B[i]);
            swap(P[i], Q[i]);
        }
    }

    auto check = [&](int mid) -> bool
    {
        long long cost = 0;

        for (int i = 0; i < N; i++)
        {
            long long c = 1e18;

            for (int j = 0; j <= 100; j++)
            {
                // the cost of j machines of type T
                long long cur = j * Q[i];
                // Remaining products are cocurered using type S
                int need = mid - j * B[i];

                if (need > 0)
                {
                    // a classic "ceiling division" trick
                    cur += 1ll * (need + A[i] - 1) / A[i] * P[i];
                }

                // find the minimum amount of money required to have $W_i \ge w$
                c = min(c, cur);
            }

            cost += c;
        }

        return cost <= X;
    };

    int lo = 0, hi = 1e9;
    while (lo < hi)
    {
        int mid = (lo + hi + 1) / 2;
        if (check(mid))
        {
            lo = mid;
        }
        else
        {
            hi = mid - 1;
        }
    }

    cout << lo << endl;

    return 0;
}

📌 F - Shipping

Tips

Since $T_N \le 10^12$ (the calendar is huge), we cannot get the correct answer by naively managing daily transitions

In fact, days of shipment can be limited to:

Day $T_i$ , where $1 \le i \le N$
Day $T_i + kX$ , where $1 \le i \le N$ and $1 \le k \le N$

Brief proof: for a set of orders to be shipped simultaneously, one of the following two always happens:

they are shipped when the last one is ready
$X$ days after the last shipment, all the orders are ready, so ship them immediately on that day

The former can be represented as day $T_i$ for some $i$ , and the latter as $X$ days after a shipment

Now the number of days to inspect has been reduced to $O(N^2)$

Tips

Let us call the days to focus as event $1, 2, ...$

Define dp[event][j]: the minimum dissatisfaction if we process the first $j$ orders and the last shipment was made at event

event: the index of a shipping day (in our reduced event list)
j: the number of processed orders so far

The transitions are as follows:

Do nothing on this event

dp[event + 1][j] = \min(dp[event + 1][j], dp[event][j])

Ship orders $j$ $j$ to $j + m$ $j + m$ (up to $K$ $K$ orders) on this day
- Choose $m = 1, ..., K$ orders
- Compute dissatisfaction:

\sum_{i = j}^{j + m - 1}(D - T_i)

Let $d$ be the next event after $current_day + X$ , then:

dp[d][j + m] = \min(dp[d][j + m], dp[event][j] + cost)

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<long long> T(N);
    for (int i = 0; i < N; i++)
    {
        cin >> T[i];
    }

    vector<long long> cand;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            // These are the only meaningful days we need to consider for shipment
            cand.push_back(T[i] + j * X);
        }
    }
    sort(cand.begin(), cand.end());
    cand.erase(unique(cand.begin(), cand.end()), cand.end());

    // dp[i][j]: min dissatisfaction when j orders are shipped, and last shipping was on cand[i]
    vector<vector<long long>> dp(cand.size(), vector<long long>(N + 1, 1e18));

    // f[j]: best possible dissatisfaction for j orders up to previous event
    vector<long long> f(N + 1, 1e18);
    f[0] = 0;

    long long ans = 1e18;

    for (int i = 0, j = 0; i < cand.size(); i++)
    {
        long long d = cand[i];

        // This updates f to include all past valid shipment days (cand[j])
        // that are at least X days before current day d
        while (cand[j] + X <= d)
        {
            for (int k = 0; k <= N; k++)
            {
                f[k] = min(f[k], dp[j][k]);
            }
            j++;
        }

        int s = 0;
        while (s < N && T[s] <= d)
        {
            s++;
        }

        // Then, for each j (number of shipped orders so far)
        // ship up to K new orders (as many as possible by current day d)
        for (int j = 0; j <= s; j++)
        {
            int nj = min(s, j + K);
            dp[i][nj] = min(dp[i][nj], f[j] + (nj - j) * d);
        }

        ans = min(ans, dp[i][N]);
    }

    ans -= accumulate(T.begin(), T.end(), 0ll);

    cout << ans << endl;

    return 0;
}

📌 G - Only One Product Name

Warning

Hard Problems to Tackle Later

// TODO