🧩 AtCoder Beginner Contest 378

TayLockNovember 2, 2024About 4 min

🧩 AtCoder Beginner Contest 378

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	DFS	DFS	⭐🔥
E	Math	Fenwick Tree	🧠🛠️🌀
F	Tree/Graph	DP/LCA	🌀
G	Math	Robinson–Schensted correspondence	🌀

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 - Pairing

#include <bits/stdc++.h>

using namespace std;

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

    vector<int> cnt(4);
    for (int i = 0; i < 4; i++)
    {
        int A;
        cin >> A;
        A--;

        cnt[A]++;
    }

    int ans = 0;
    for (int i = 0; i < 4; i++)
    {
        ans += cnt[i] / 2;
    }

    cout << ans << endl;

    return 0;
}

📌 B - Garbage Collection

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    vector<int> q(N), r(N);
    for (int i = 0; i < N; i++)
    {
        cin >> q[i] >> r[i];
    }

    int Q;
    cin >> Q;

    for (int i = 0; i < Q; i++)
    {
        int t, d;
        cin >> t >> d;
        t--;

        cout << d + (r[t] - d % q[t] + q[t]) % q[t] << endl;

    }

    return 0;
}

📌 C - Repeating

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    vector<long long> A(N), B(N, -1);
    map<long long, int> mp;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];

        if (mp.count(A[i]))
        {
            B[i] = mp[A[i]];
        }

        mp[A[i]] = i + 1;
    }

    for (int i = 0; i < N; i++)
    {
        cout << B[i] << " \n"[i == N - 1];
    }

    return 0;
}

📌 D - Count Simple Paths

#include <bits/stdc++.h>

using namespace std;

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

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

    int H, W, K;
    cin >> H >> W >> K;

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

    int ans = 0;

    vector<vector<bool>> vis(H, vector<bool>(W));

    auto dfs = [&](auto &&self, int i, int j, int k) -> void
    {
        if (k == 0)
        {
            ans++;
            return;
        }

        vis[i][j] = true;
        for (int d = 0; d < 4; d++)
        {
            int nx = i + dx[d];
            int ny = j + dy[d];

            if (nx < 0 || ny < 0 || nx >= H || ny >= W)
            {
                continue;
            }
            if (grid[nx][ny] == '#')
            {
                continue;
            }
            if (vis[nx][ny])
            {
                continue;
            }

            self(self, nx, ny, k - 1);
        }
        vis[i][j] = false;
    };

    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            if (grid[i][j] == '.')
            {
                dfs(dfs, i, j, K);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

📌 E - Mod Sigma Problem

Tips

The typical approach to represent subarray sums employs cumulative sums

Let $S_i = (A_1 + A_2 + ... + A_i) \bmod M$ be the cumulative sums (modulo $M$ ) of the sequence $A$

Then the sought value can be:

\sum_{1 \le l \le r \le N}((\sum_{l \le i \le r}A_i) \bmod M) = \sum_{1 \le l \le r \le N}(S_r - S_{l - 1}) \bmod M

Since $0 \le S_{l - 1}, S_r < M$ , we can write as:

(S_r - S_{l - 1}) \bmod M = S_r - S_{l - 1} + \begin{cases} 0 & (S_{l - 1} \le S_r) \\ M & (S_{l - 1} > S_r) \end{cases}

which no longer involves mod

Tips

Let $X_r$ : the number of $l = 1, 2, ..., r$ with $S_{l - 1} > S_r$ and apply the equation above to rewrite the sought value as:

\begin{align*} ans &= \sum_{r = 1}^{N}\sum_{l = 1}^{r}(S_r - S{l - 1}) \bmod M \\ &= \sum_{r = 1}^{N}(S_r \times r - \sum_{l = 1}^{r}S_{l - 1} + M \times X_r) \\ &= \sum_{r = 1}^{N}(S_r \times r) - \sum_{r = 1}^{N}\sum_{l = 1}^{r}S_{l - 1} + \sum_{r = 1}^{N}(M \times X_r) &= \sum_{r = 1}^{N}(S_r \times r) - \sum_{r = 0}^{N - 1}(S_r \times (N - r)) + \sum_{r = 1}^{N}(M \times X_r) \end{align*}

Then $\sum_{l = 1}^{r}S_{l - 1}$ is a cumulative sum of $S$ , which can be evaluated easily

Tips

All that left is to find $X_r$ for $r = 1, 2, ..., N$ fast enough for each $r = 1, 2, ..., N$

$X_r$ can be computed using a Fenwick Tree

Here, if we define $B_x$ as the number of $l$ with $S_{l - 1} = x$ , we can compute $X_r$ by the following algorithm:

Initialize with $B_x = 0$
For each $r = 1, 2, ..., N$ $r = 1, 2, ..., N$ , do the following:
- Compute $X_r = B_{S_r + 1} + B_{S_r + 2} + ... + B_{M - 1}$
- Add $1$ to $B_{S_r}$

The overall complexity is $O(N \log M + M)$

#include <bits/stdc++.h>

using namespace std;

template <typename T>
struct Fenwick
{
    int n;
    vector<T> a;

    Fenwick(int n_ = 0)
    {
        init(n_);
    }

    void init(int n_)
    {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v)
    {
        for (int i = x + 1; i <= n; i += i & -i)
        {
            a[i - 1] = a[i - 1] + v;
        }
    }

    T sum(int x)
    {
        T ans{};
        for (int i = x; i > 0; i -= i & -i)
        {
            ans = ans + a[i - 1];
        }
        return ans;
    }

    T rangeSum(int l, int r)
    {
        return sum(r) - sum(l);
    }

    int select(const T &k)
    {
        int x = 0;
        T cur{};

        for (int i = 1 << __lg(n); i; i /= 2)
        {
            if (x + i <= n && cur + a[x + i - 1] <= k)
            {
                x += i;
                cur = cur + a[x - 1];
            }
        }

        return x;
    }
};

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

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

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

    vector<long long> pre(N + 1);
    for (int i = 0; i < N; i++)
    {
        pre[i + 1] = pre[i] + A[i];
    }

    long long ans = 0;

    for (int i = 0; i <= N; i++)
    {
        pre[i] %= M;

        // \sum_{r = 1}^{N}(S_r \times r)
        ans += pre[i] * i;
        // \sum_{r = 1}^{N}\sum_{l = 1}^{r}S_{l - 1}
        ans -= pre[i] * (N - i);
    }

    // count how many values to the left of index i are greater than pre[i]
    Fenwick<int> fen(N + 1);

    // in descending order
    vector<int> p(N + 1);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int i, int j)
         {
        if (pre[i] != pre[j])
        {
            return pre[i] > pre[j];
        }
        return i > j; });

    // Then we sweep from largest to smallest, using Fenwick tree to count how many j < i have already been added
    for (auto i : p)
    {
        // M \times X_r
        ans += 1ll * fen.sum(i) * M;

        fen.add(i, 1);
    }

    cout << ans << endl;

    return 0;
}

📌 F - Add One Edge 2

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Everlasting LIDS

Warning

Hard Problems to Tackle Later

// TODO