🧩 AtCoder Beginner Contest 377

TayLockOctober 26, 2024About 3 min

🧩 AtCoder Beginner Contest 377

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Coverage Check	Math	⭐🔥
E	Graph	Math/Modular exponentiation	🧠🌀
F	Math	Math	🌀
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 - Rearranging ABC

#include <bits/stdc++.h>

using namespace std;

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

    string S;
    cin >> S;

    sort(S.begin(), S.end());

    cout << (S == "ABC" ? "Yes" : "No") << endl;

    return 0;
}

📌 B - Avoid Rook Attack

#include <bits/stdc++.h>

using namespace std;

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

    set<int> col, row;
    for (int i = 0; i < 8; i++)
    {
        string s;
        cin >> s;

        for (int j = 0; j < 8; j++)
        {
            if (s[j] == '#')
            {
                row.insert(i);
                col.insert(j);
            }
        }
    }

    cout << (8 - row.size()) * (8 - col.size()) << endl;

    return 0;
}

📌 C - Avoid Knight Attack

#include <bits/stdc++.h>

using namespace std;

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

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

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

    set<pair<long long, long long>> s;

    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;

        s.insert({a, b});

        for (int k = 0; k < 8; k++)
        {
            long long nx = a + dx[k];
            long long ny = b + dy[k];

            if (nx < 0 || ny < 0 || nx >= N || ny >= N)
            {
                continue;
            }

            s.insert({nx, ny});
        }
    }

    cout << N * N - s.size() << endl;

    return 0;
}

📌 D - Many Segments 2

Tips

An important fact is that, if an integer pair $(l, r)$ satisfies the conditions, then so does $(l + 1, r)$

Thus, there exists $d_r$ such that:

For a fixed $r$ , a pair $(l, r)$ satisfies the conditions if and only if $l$ is an integer between $d_r$ and $r$ , inclusive

Suppose that we already know $d_{r - 1}$ and now we want to find $d_r$ :

If there is no $i$ with $R_i = r$ , then there are no new constraints, so $d_r = d_{r - 1}$
If there exists such $i$ , we have $d_r = \max(d_{r - 1}, L_{max} + 1)$ , where $L_{max}$ is the maximum $L_i$ for $i$ with $R_i = r$

Then, the sought answer can be found as $\sum_{r = 1}^{M}(r - d_r + 1)$

#include <bits/stdc++.h>

using namespace std;

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

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

    // f[i] will eventually represent the smallest r such that [i,r] is not invalid
    vector<int> f(M, M);
    for (int i = 0; i < N; i++)
    {
        int L, R;
        cin >> L >> R;
        L--;
        R--;

        // starting from l = L_i, no r ≥ R_i should be valid
        // So we store the earliest invalid r for each L_i
        f[L] = min(f[L], R);
    }

    for (int i = M - 2; i >= 0; i--)
    {
        // for any l, we know the smallest invalid r for any interval starting at or after l
        // So the valid range for r is: r∈[l,f[l]−1]
        f[i] = min(f[i], f[i + 1]);
    }

    long long ans = 0;
    for (int i = 0; i < M; i++)
    {
        ans += f[i] - i;
    }

    cout << ans << endl;

    return 0;
}

📌 E - Permute K times 2

Tips

Consider a directed graph with vertices $1, 2, ..., N$ with $N$ edges $i \rightarrow P_i$

In this graph, let us denote by $P_i^k$ the vertex we reach by advancing from $i$ , $k$ times

The sought answer is $(P_i^{2^k})$

Tips

The directed graph can be decomposed into cycles. The answer can be obtained by finding the remainder when dividing $2^K$ by the length of the cycle

#include <bits/stdc++.h>

using namespace std;

// Modular exponentiation: a^b \bmod p
int power(int a, long long b, int p)
{
    int res = 1;
    for (; b; b /= 2, a = 1ll * a * a % p)
    {
        if (b & 1)
        {
            res = 1ll * res * a % p;
        }
    }

    return res;
}

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

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

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

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

        // For each unvisited node i, we explore its path until we return to a visited node
        // this always finds a cycle, which is stored in vertor a
        int j = i;
        vector<int> a;
        while (!vis[j])
        {
            vis[j] = true;
            a.push_back(j);
            j = P[j];
        }

        // Compute 2^K modulo cycle length
        // ompute how many steps to rotate within the cycle
        long long d = power(2, K, a.size());

        // Rotate the cycle
        for (int x = 0; x < a.size(); x++)
        {
            P[a[x]] = a[(x + d) % a.size()];
        }
    }

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

    return 0;
}

📌 F - Avoid Queen Attack

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Edit to Match

Warning

Hard Problems to Tackle Later

// TODO