🧩 AtCoder Beginner Contest 367

# Info & Summary

• Date: 2024-08-17
• Completion Status: A ✅ / B ✅ / C ✅ / D ✅ / E ❌ / F ❌ / G ❌
• Problem Type:

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Prefix Sum	Prefix Sum	⭐🔥
E	Function Exponentiation	Binary Lifting/Doubling	🧠🛠️🌀
F	determine if two sets are equal	Zobrist Hash	🌀
G	Math	XOR convolution & Hadamard transform	🌀

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 - Shout Everyday

367A

#include <bits/stdc++.h>

using namespace std;

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

    int A, B, C;
    cin >> A >> B >> C;

    if (B < C)
    {
        if (B < A && A < C)
        {
            cout << "No" << endl;
        }
        else
        {
            cout << "Yes" << endl;
        }
    }
    else
    {
        if (C < A && A < B)
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }

    return 0;
}

📌 B - Cut .0

367B

#include <bits/stdc++.h>

using namespace std;

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

    string S;
    cin >> S;

    while (S.back() == '0')
    {
        S.pop_back();
    }

    if (S.back() == '.')
    {
        S.pop_back();
    }

    cout << S << endl;

    return 0;
}

📌 C - Enumerate Sequences

367C

#include <bits/stdc++.h>

using namespace std;

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

    int N, K;
    cin >> N >> K;

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

    vector<vector<int>> ans;

    vector<int> v;
    auto dfs = [&](auto &&self, int p, int sum) -> void
    {
        if (p == N)
        {
            if (sum % K == 0)
            {
                ans.push_back(v);
            }
            return ;
        }

        for (int r = 1; r <= R[p]; r++)
        {
            v.push_back(r);
            self(self, p + 1, sum + r);
            v.pop_back();
        }
    };

    dfs(dfs, 0, 0);

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

    return 0;
}

📌 D - Pedometer

367D

Tips

Let:

$$\begin{cases} dist(s \rightarrow t) = \sum_{i = s}^{t - 1}A_i & (s < t) \\ dist(s \rightarrow t) = \sum_{i = s}^{N}A_i + \sum_{i = 1}^{t - 1}A_i & (s > t)\\ \end{cases}$$

We want:

$$dist(s \rightarrow t) \bmod M = 0, s \neq t$$

Tips

Define pre[i]:

pre[i]: the total steps from rest area $1$ up to (but not including) rest area $i + 1$

then we got:

• if $i < j$, then the distance:

  $$dist(s \rightarrow t) = pre[j] - pre[i]$$

• if $i > j$, then the distance:

  $$dist(s \rightarrow t) = (pre[N] - pre[i]) + (pre[j]) = pre[j] - pre[i] + L$$

  where $L = pre[N]$

#include <bits/stdc++.h>

using namespace std;

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];
    }

    map<int, int> cnt;
    long long ans = 0;

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

    const long long L = pre[N];

    for (int i = 0, j = 0; i < N; i++)
    {
        ans += cnt[(pre[i] - L % M + M) % M];
        ans += cnt[pre[i] % M];

        cnt[pre[i] % M]++;
    }

    cout << ans << endl;

    return 0;
}

📌 E - Permute K times

367E

Function Exponentiation

We have:

• A function $f$ on the set $(0, 1, ..., N - 1)$, given by an array $X$ where

  $$f(i) = X[i]$$

• An initial array $A$ of length $N$
• A nonnegative integer $K$, potentially as large as $10^{18}$

We want to compute, for each position $i$, the element:

$$A(f^{K}(i)) = A(f(f(\cdots f(i) \cdots)))$$

where $f$ is applied $K$ times

A native simulation takes $O(NK)$, which is impossible for large $K$

Binary-Lifting to Compute $f^K$ in $O(N \log N)$

Instead, we use binary lifting (sometimes called doubling or function exponentiation) to do it in $O(N \log N)$

Key idea: Decompose K in powers of two

Any integer $K$ can be written in binary:

$$K = \sum_{b = 0}^{L}k_b2^b, k_b \in \lbrace 0, 1 \rbrace$$

Then

$$f^K = f^{\sumk_b2^b} = \prod_{b: k_b = 1}(f^{2^b})$$

So if we can precompute each $2^b$-fold iterate $f^{2^b}$, we can build $f^K$ by selecting only those powers of two that appear in the binary expansion of $K$

Precompute Doubling Table Implicitly

Instead of an explicit 2D table $up[i][b] = f^{2^b}(i)$, we keeps a single array $X$ that it repeatedly square in place:

• Initially, $X[i] = f(i)$
• After one square step, $X[i] = f(f(i)) = f^{2^1}(i)$
• Ans after $b$ squares, $X[i] = f^{2^b}(i)$

Concurrently, we maintain an accumulator array Y[i] that starts as the identity $Y[i] = i$. Whenever the current lowest bit of $K$ is 1, we apply the present $X$ (which equals $f^{2^b}$) to Y

After we processed all $\log_{2}K$ bits in this way, $Y[i] = f^{K}(i)$

Once we know for each index $i$ the value $Y[i] = f^{K}(i)$, the element at position $i$ in the $K$-th iterate of $A$ is simply $A[Y[i]]$

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    long long K;
    cin >> N >> K;

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

    // Initialize the “accumulator” array Y
    // We'll maintain Y[i] = f^{(\text{processed bits of }K)}(i)
    // Initially, Y[i] = i (zero applications)
    vector<int> Y(N);
    iota(Y.begin(), Y.end(), 0);

    // Binary-exponentiate
    while (K > 0)
    {
        // If the current lowest bit of K is 1, apply the current power of X to Y
        if (K % 2 == 1)
        {
            for (int i = 0; i < N; i++)
            {
                Y[i] = X[Y[i]];
            }
        }

        // Square the mapping X ← X ∘ X (so X[i] now equals f(f(i)) for next bit)
        vector<int> tmp(N);
        for (int i = 0; i < N; i++)
        {
            tmp[i] = X[X[i]];
        }
        X = move(tmp);

        // shift out the bit we just handled
        K /= 2;
    }

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

    // Finally, after K applications, position i in the resulting array
    // was originally at A[Y[i]]
    for (int i = 0; i < N; i++)
    {
        cout << A[Y[i]] << " \n"[i == N - 1];
    }

    return 0;
}

📌 F - Rearrange Query

367F

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Sum of (XOR^K or 0)

367G

Warning

Hard Problems to Tackle Later

// TODO