🧩 AtCoder Beginner Contest 379

TayLockNovember 9, 2024About 3 min

🧩 AtCoder Beginner Contest 379

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
C	Math	Constructive	🧠
D	Simulation	Simulation	🧠
E	Math	Column Addition	🧠🛠️
F	Math	Fenwick tree	🌀
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 - Cyclic

#include <bits/stdc++.h>

using namespace std;

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

    string s;
    cin >> s;

    cout << s[1] << s[2] << s[0] << ' ' << s[2] << s[0] << s[1] << endl;

    return 0;
}

📌 B - Strawberries

#include <bits/stdc++.h>

using namespace std;

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

    int N, K;
    string S;
    cin >> N >> K >> S;

    int ans = 0;
    int cnt = 0;

    for (auto c : S)
    {
        if (c == 'X')
        {
            cnt = 0;
        } else {
            cnt += 1;

            if (cnt == K)
            {
                ans += 1;
                cnt = 0;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

📌 C - Sowing Stones

Tips

Condition that every cell can end up having one stone:

First, $\sum_{i = 1}^{M}A_i = N$ is necessary
Then the necessary and sufficient condition is that cells $1, 2, ..., i$ have a total of $i$ or more stones

Checking the condition for all $i$ is a bit difficult because $N$ can be up to $2 \times 10^9$ , but there are only $M$ indices $i$ such that the total number of stones in cells $1, 2, ..., i$ changes, namely indices $X_1, X_2, ..., X_M$ , so it is sufficient to scan only $i = X_1 - 1, X_2 - 1, ..., X_M - 1$

How to find the minimum number of operations required?

Since a stone can only move right (i.e., from smaller index to larger index), every time you move a stone from $i$ to $j$ , it costs $j - i$

So, for each stone:

cost = (its \; final \; position) - (its \; starting \; position)

Hence:

\begin{align*} Total \; cost &= \sum_{all \; stones}(its \; final \; position) - (its \; starting \; position) \\ &= sum \; of \; final \; positions - sum \; of \; initial \; positions \end{align*}

Thus, the minimum number of operations is:

\frac{N(N + 1)}{2} - \sum_{i = 1}^{M}X_i \times A_i

$\frac{N(N + 1)}{2}$ : the ideal total sum of final positions (1-based, each position gets 1 stone)
$\sum_{i = 1}^{M}X_i \times A_i$ : the total sum of initial positions of all stones

#include <bits/stdc++.h>

using namespace std;

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

    long long N, M;
    cin >> N >> M;

    vector<pair<int, long long>> A(M);
    for (int i = 0; i < M; i++)
    {
        cin >> A[i].first;
    }
    for (int i = 0; i < M; i++)
    {
        cin >> A[i].second;
    }
    sort(A.begin(), A.end());

    long long sum = 0, idx = 0;
    for (auto p : A)
    {
        if (sum < p.first - 1)
        {
            cout << -1 << endl;
            return 0;
        }

        sum += p.second;
        idx += p.second * p.first;
    }

    cout << (sum != N ? -1 : N * (N + 1) / 2 - idx) << endl;

    return 0;
}

📌 D - Home Garden

Type 1: Plant a seed

a.push_back(-t);

Because this plant's actual height when we evaluate later will be:

current \; height = t + a[i]

At planting time: $height = t + (-t) = 0$

This trick avoids needing to store separate timestamps

#include <bits/stdc++.h>

using namespace std;

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

    int Q;
    cin >> Q;

    // a: Stores offsets for each planted plant
    vector<long long> a;
    // s: Index pointer to the first unharvested plant
    int s = 0;
    // t: Cumulative total of growth (from all type-2 operations)
    long long t = 0;

    for (int i = 0; i < Q; i++)
    {
        int o;
        cin >> o;

        if (o == 1)
        {
            a.push_back(-t);
        }
        else if (o == 2)
        {
            int T;
            cin >> T;

            t += T;
        }
        else
        {
            int H;
            cin >> H;

            int ans = 0;
            // compute actual height as a[s] + t
            while (s < a.size() && a[s] + t >= H)
            {
                s++;
                ans++;
            }

            cout << ans << endl;
        }
    }

    return 0;
}

📌 E - Sum of All Substrings

Base-10 column addition

First, consider how the answer can be represented when $N$ is small

When $N = 3$ , the answer is as follows:

\begin{align*} ans &= f(1, 1) + f(1, 2) + f(1, 3) + f(2, 2) + f(2, 3) + f(3, 3) \\ &= (S_1) + (10S_1 + S_2) + (100S_1 + 10S_2 + S_3) + (S_2) + (10S_2 + S_3) + (S_3) \\ &= 10^2(S_1) + 10^1(S_1 + 2S_2) + 10^0(S_1 + 2S_2 + 3S_3) \end{align*}

More generally, for $A_i = \sum_{j = 1}^{i} j \times S_j$ , the answer is:

\sum_{i = 1}^{N} 10^{N - i}A_i

This means: every digit appears in multiple substrings, and its contribution is weighted by its place in the string and the number of substrings that include it

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    string S;
    cin >> S;

    // Build A_i
    vector<long long> a(N);
    long long sum = 0;
    for (int i = 0; i < N; i++)
    {
        // \sum_{j = 1}^{i} j \times S_j
        sum += (S[i] - '0') * (i + 1);

        // reverses the index to line up with 10^i
        a[N - 1 - i] = sum;
    }

    // Perform base-10 column addition (manual carry propagation)
    // This manually handles large digit values by propagating carries like elementary addition
    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] >= 10)
        {
            if (i + 1 >= a.size())
            {
                a.resize(i + 2); // make space for carry
            }

            a[i + 1] += a[i] / 10; // carry to next digit
            a[i] %= 10;            // keep remainder in this digit
        }
    }

    // Digits are stored with least significant digit first, so we reverse them before printing
    reverse(a.begin(), a.end());
    for (auto x : a)
    {
        cout << x;
    }
    cout << endl;

    return 0;
}

📌 F - Buildings 2

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Count Grid 3-coloring

Warning

Hard Problems to Tackle Later

// TODO