🧩 AtCoder Beginner Contest 389

TayLockJanuary 18, 2025About 3 min

🧩 AtCoder Beginner Contest 389

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
E	cheap-first strategy	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 - 9x9

#include <bits/stdc++.h>

using namespace std;

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

    string s;
    cin >> s;

    cout << (s[0] - '0') * (s[2] - '0') << endl;

    return 0;
}

📌 B - tcaF

#include <bits/stdc++.h>

using namespace std;

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

    long long x;
    cin >> x;

    int ans = 0;
    long long cur = 1;

    while (cur != x)
    {
        ans++;
        cur *= ans;
    }

    cout << ans << endl;

    return 0;
}

📌 C - Snake Queue

#include <bits/stdc++.h>

using namespace std;

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

    int q;
    cin >> q;

    vector<long long> snake(q + 10, 0);
    int left = 1, right = 0;

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

        if (a == 1)
        {
            int l;
            cin >> l;

            right++;
            snake[right] = l + snake[right - 1];
        }
        else if (a == 2)
        {
            left++;
        }
        else
        {
            int k;
            cin >> k;
            k--;

            cout << snake[left + k - 1] - snake[left - 1] << endl;
        }
    }

    return 0;
}

📌 D - Squares in Circle

Tips

Let $(0, 0)$ be the center of the circle

Among the conforming pairs $(i, j)$ , we can easily count those with $i = 0$ or $j = 0$ ; there are $4(R - 1) + 1$ of them, where one is on the origin and the others are in one of the four directions
Next, for $i \ne 0$ and $j \ne 0$ , by symmetry, it is sufficient to count those with $i > 0$ and $j > 0$ , and multiply the count by $4$

We enumerate $i$ for $1, 2, ..., R - 1$ in order, then, the maximum integer $j$ with $(i + 0.5)^2 + (j + 0.5)^2 \le R^2$ decreases monotonically

Thus, by managing the maximum $j$ in the manner of the sliding window trick, we obtain a solution with time complexity $O(R)$

Tips

Note that while we may using decimals for this problem, in general it is vulnerable to precision errors, so it is a good idea to stick to integers whenever possible

(i + 0.5)^2 + (j + 0.5)^2 \le R^2 \iff (2i + 1)^2 + (2j + 1)^2 \le 4R^2

#include <bits/stdc++.h>

using namespace std;

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

    long long r;
    cin >> r;

    auto calc = [&](long long a, long long b)
    {
        return (2 * a + 1) * (2 * a + 1) + (2 * b + 1) * (2 * b + 1) <= 4 * r * r;
    };

    long long res = 0;
    long long j = r - 1;
    for (long long i = 1; calc(i, 1); i++)
    {
        while (!calc(i, j))
        {
            j--;
        }

        res += j;
    }

    long long ans = (r - 1) * 4 + 1;
    ans += res * 4;

    cout << ans << endl;

    return 0;
}

📌 E - Square Price

Tips

That buying $k$ instances of the $i$ -th product cost $k^2P_i$ yen means:

each instance of the $i$ -th product has a different price
the $j$ -th ( $1$ -based indexing) cheapest instance costs $(2j - 1)P_i$ yen

Now, we know the prices of the $N \times 10^100$ items, where we can maximize the number of items to buy by picking from the cheapest, but of course, we cannot enumerate all the prices of the items and sort them

Tips

Herem the cheap-first strategy has the following property:

there exists an integer $x$ such that we buy all the items with price at most $x$ , as well as as many items of price $x + 1$ as possible

This $x$ can be found with Binary Search

Once we find this $x$ , the maximum number of items that can be bought is also found

#include <bits/stdc++.h>

using namespace std;
using i128 = __int128_t;

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

    long long n, m;
    cin >> n >> m;

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

    auto check = [&](long long mid) -> pair<i128, i128>
    {
        i128 cost = 0, cnt = 0;
        for (int i = 0; i < n; i++)
        {
            if (mid < P[i])
            {
                continue;
            }

            long long upper = mid / P[i];
            long long k = (upper + 1) / 2;

            cnt += k;
            cost += i128(P[i]) * k * k;

            if (cost > m)
            {
                break;
            }
        }

        return {cost, cnt};
    };

    long long l = 0, r = m + 1;
    while (r - l > 1)
    {
        long long mid = l + (r - l) / 2;
        (check(mid).first <= m ? l : r) = mid;
    }

    auto [cost, cnt] = check(l);
    long long ans = cnt + (m - cost) / r;
    cout << ans << endl;

    return 0;
}

📌 F - Rated Range

Tips

A naive solution is to simulate the $N$ contests one by one for each initial rating $X$ given in a query. This approach costs $O(NQ)$ time, which is not fast enough this time

Here, instead of simulating the contests for each query, consider precalculating the answers for $X = 1, 2, ..., 5 \times 10^5$ before processing the queries, and respond the queries based on these precalculated values

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Odd Even Graph

Warning

Hard Problems to Tackle Later

// TODO