🧩 AtCoder Beginner Contest 391

TayLockFebruary 1, 2025About 7 min

🧩 AtCoder Beginner Contest 391

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Simulation	Simulation	⭐
E	DP	DP/Group DP	🧠🛠️🌀
F	K-th Largest	Priority_queue	🔥

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 - Lucky Direction

#include <bits/stdc++.h>

using namespace std;

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

    string s;
    cin >> s;

    for (auto &c : s)
    {
        if (c == 'N')
        {
            c = 'S';
        } else if (c == 'E')
        {
            c = 'W';
        } else if (c == 'W')
        {
            c = 'E';
        } else {
            c = 'N';
        }
    }

    cout << s << endl;

    return 0;
}

📌 B - Seek Grid

#include <bits/stdc++.h>

using namespace std;

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

    int n, m;
    cin >> n >> m;

    vector<string> s(n), t(m);
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
    for (int i = 0; i < m; i++)
    {
        cin >> t[i];
    }

    for (int i = 0; i <= n - m; i++)
    {
        for (int j = 0; j <= n - m; j++)
        {
            bool ok = true;
            for (int x = 0; x < m; x++)
            {
                for (int y = 0; y < m; y++)
                {
                    if (s[i + x][j + y] != t[x][y])
                    {
                        ok = false;
                        break;
                    }
                }
            }

            if (ok)
            {
                cout << i + 1 << " " << j + 1 << endl;
                return 0;
            }
        }
    }

    return 0;
}

📌 C - Pigeonhole Query

#include <bits/stdc++.h>

using namespace std;

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

    int n, q;
    cin >> n >> q;

    int ans = 0;

    vector<int> p_to_n(n), cnt(n, 1);
    for (int i = 0; i < n; i++)
    {
        p_to_n[i] = i;
    }

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

        if (a == 1)
        {
            int p, h;
            cin >> p >> h;
            p--;
            h--;

            cnt[h]++;
            cnt[p_to_n[p]]--;

            if (cnt[h] == 2)
            {
                ans++;
            }
            if (cnt[p_to_n[p]] == 1)
            {
                ans--;
            }

            p_to_n[p] = h;
        }
        else
        {
            cout << ans << endl;
        }
    }

    return 0;
}

📌 D - Gravity

Consider determining whether block $A$ exists at time $T$

Suppose that block $A$ is the $c_A$ -th block from the bottom within the $X_A$ -th column. Then, block $A$ disappears when the bottom-row blocks disappear for the $c_A$ -th time

Thus, once we can enumerate the timestamps $d_1 < d_2 < ...$ when the bottom-row blocks vanish, then the problem can be solved by comparing $T$ and $d_{c_A}$

If the block never disappears more than $c_A$ times, left $d_{c_A} = \infty$

$d_c$ is the maximum of the timestamp on which the $c$ -th block from the bottom within each column reaches the bottommost row. If any column does not have $c$ or more blocks, then $d_c = \infty$

$d_1$ can be found as the maximum value of the time when the bottommost block in each column reaches the bottommost row, plus $1$ . If the $c$ -th block from the bottom within the $x$ -th row is initially located at cell $(x, y_{x, c})$ , we have $d_1 = \max{y_{1, 1}, ..., y_{W, 1}}$
For $d_c$ ( $c \ge 2$ ), Consider the time when the $c$ -th block from the bottom within the $x$ -th row reaches the bottommost row. If the block is never obstructed by the block below before reaching the bottommost row, then the block reaches the bottommost row at time $y_{x, c} - 1$ . If it is obstructed, then afterward the $c$ -th block goes down by one cell every time the $(c - 1)$ -th block goes down, and it reaches the bottommost row at time $d_{c - 1}$ , when the $(c - 1)$ -th block vanishes. Thus, $d_c = \max{y_{1, c}, ..., y_{W, c}, d_{c - 1} + 1}$

Therefore, $d$ can be found by the following algorithm:

Initialize $d_1, d_2, ..., d_{N + 1}$ with $0$
For each $x = 1, ..., W$ $x = 1, ..., W$ , do the following:
- Sort the $y$ coordinates of the blocks in the $x$ -th column. Let $y_{x, 1} < y_{x, 2} < ... < y_{x, C}$ be the coordinates
- For each $c = 1, ..., C$ , set $d_c \leftarrow \max{d_c, y_{x, c}}$
- Set $d_{C + 1} \leftarrow \infty$
For each $c = 2, ..., N + 1$ , set $d_c \leftarrow \max{d_c, d_{c - 1} + 1}$

#include <bits/stdc++.h>

using namespace std;

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

    int n, w;
    cin >> n >> w;

    // where each column (x) contains an array of pairs representing the rows (y)
    // of the blocks in that column and their indices
    vector<vector<array<int, 2>>> vec(w);
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        x--;

        vec[x].push_back({y, i});
    }

    // For each column x, we sort the blocks by their row y coordinate
    for (int i = 0; i < w; i++)
    {
        sort(vec[i].begin(), vec[i].end());
    }

    // For each column x, the first s blocks (where s is the minimum number of blocks across all columns)
    // will settle at the bottom-most rows
    // s: how many rows will be completely filled by blocks, and any additional rows will not contain blocks
    int s = n;
    for (int i = 0; i < w; i++)
    {
        s = min(s, int(vec[i].size()));
    }

    // For each y-th position (representing the y-th block in the column), the final position at time
    // T is calculated as the time when all blocks in the column are dropped
    // calculate the latest time when the block reaches its final position
    vector<int> ans(n, 2e9);
    for (int y = 0; y < s; y++)
    {
        // t: the maximum time at which the block in the y-th position of any column will fall
        int t = 0;
        for (int x = 0; x < w; x++)
        {
            // the block in the current column x may be blocked by a block
            // from the previous column or it may fall directly
            t = max(t, vec[x][y][0]);
        }

        // assign this time t to all blocks in the y-th position across columns
        for (int x = 0; x < w; x++)
        {
            ans[vec[x][y][1]] = t;
        }
    }

    int q;
    cin >> q;

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

        cout << (t < ans[a] ? "Yes" : " No") << endl;
    }

    return 0;
}

📌 E - Hierarchical Majority Vote

Dynamic Programming

Let $A^{(k)} = (A_{1}^{(k)}, ..., A_{3^{N - k}}^{(k)})$ be the $k$ -time repetition of $A$ , and $A^{(k)}$ can be obtained by naively performing the operation in the problem statement

Let $f(k, i)$ be the number of elements in $A$ required to alter, in order to flip the value $A_i^{(k)}(i = 1, ..., 3^{N - k})$

The sought answer is $f(N, 1)$

Initially, for $k = 0$ , we clearly have $f(0, i) = 1 (i = 1, ..., 3^{N})$

Now, we consider $k \ge 1$ : $A_i^{(k)}$ is the majority of $A_{3i - 2}^{(k - 1)}, A_{3i - 1}^{(k - 1)}, A_{3i}^{(k - 1)}$

Among $A_{3i - 2}^{(k - 1)}, A_{3i - 1}^{(k - 1)}, A_{3i}^{(k - 1)}$ , there are exactly two or three values equal to $A_i^{(k)}$ :

If three values are the same:
- e.g., $A_i^{(k)} = 1$ and $A_{3i - 2}^{(k - 1)} = 1, A_{3i - 1}^{(k - 1)} = 1, A_{3i}^{(k - 1)} = 1$
- To flip the value $A_i^{(k)}$ , we need to flip least two of $A_{3i - 2}^{(k - 1)}, A_{3i - 1}^{(k - 1)}, A_{3i}^{(k - 1)}$
- Thus, $f(k, i)$ is the sum of smallest two of $f(k - 1, 3i - 2), f(k - 1, 3i - 1), f(k - 1, 3i)$
If two values are the same:
- e.g., $A_i^{(k)} = A_{3i - 2}^{(k - 1)} = A_{3i - 1}^{(k - 1)} = 1$ and $A_{3i}^{(k - 1)} = 0$
- Then, in order to flip the value of $A_i^{(k)}$ , we only need to flip one of $f(k - 1, 3i - 2), f(k - 1, 3i - 1)$
- Thus, $f(k, i) = min(f(k - 1, 3i - 2), f(k - 1, 3i - 1))$

Therefore, by filling the table in ascending order of $k$ , we can find all $f(k, i)$ . The time complexity is $O(3^N)$

#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;

    // array[0]: the cost of changing the value to `0`
    // array[1]: the cost of changing the value to `1`
    auto calc = [&](auto &&self, int l, int r) -> array<int, 2>
    {
        if (r - l == 1)
        {
            if (s[l] == '0')
            {
                // value = 0
                // the cost of `0` -> `0`: 0
                // the cost of `0` -> `1`: 1
                return {0, 1};
            }
            else
            {
                // value = 1
                // the cost of `1` -> `0`: 1
                // the cost of `1` -> `1`: 0
                return {1, 0};
            }
        }

        int len = r - l;
        int m1 = l + len / 3;
        int m2 = r - len / 3;

        auto a = self(self, l, m1);
        auto b = self(self, m1, m2);
        auto c = self(self, m2, r);

        // we only need to change at most two of three to change the value
        return {min({a[0] + b[0], b[0] + c[0], a[0] + c[0]}), min({a[1] + b[1], b[1] + c[1], a[1] + c[1]})};
    };

    auto ans = calc(calc, 0, s.size());

    cout << max(ans[0], ans[1]) << endl;

    return 0;
}

📌 F - K-th Largest Triplet

Tips

First, sort each of $A$ , $B$ , and $C$ in descending order

Then, let $f(i, j, k) = A_iB_j + B_jC_k + C_kA_i$

Then, we have:

f(i, j, k) \ge f(i + 1, j, k)

f(i, j, k) \ge f(i, j + 1, k)

f(i, j, k) \ge f(i, j, k + 1)

This implies that if we enumerate the values in descending order, $f(i, j, k)$ always comes before $f(i + 1, j, k), f(i, j + 1, k), f(i, j, k + 1)$

Thus, the problem can be solved by the following algorithm:

Prepare a queue $Q$ . Insert $(f(0, 0, 0), 0, 0, 0)$ to $Q$
Repeat the following $K$ $K$ times:
- Let $(val, i, j, k)$ be the maximum element in $Q$
- Remove $(val, i, j, k)$
- Insert $(f(i + 1, j, k), i + 1, j, k), (f(i, j + 1, k), i, j + 1, k), (f(i, j, k + 1), i, j, k + 1)$ to $Q$

The time complexity is $O(N\logN + K\logK)$

#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> A(n), B(n), C(n);
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> B[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> C[i];
    }

    sort(A.begin(), A.end(), greater());
    sort(B.begin(), B.end(), greater());
    sort(C.begin(), C.end(), greater());

    // (value, i, j, k)
    using Item = tuple<long long, int, int, int>;
    priority_queue<Item> pq;
    set<tuple<int, int, int>> st;

    auto get = [&](int i, int j, int k)
    {
        return 1ll * A[i] * B[j] + 1ll * B[j] * C[k] + 1ll * C[k] * A[i];
    };

    auto add = [&](int i, int j, int k)
    {
        if (i < n && j < n && k < n && !st.count({i, j, k}))
        {
            st.insert({i, j, k});
            pq.emplace(get(i, j, k), i, j, k);
        }
    };

    add(0, 0, 0);

    for (int i = 0; i < k; i++)
    {
        auto [v, x, y, z] = pq.top();
        pq.pop();

        if (i == k - 1)
        {
            cout << v << endl;
            return 0;
        }

        add(x + 1, y, z);
        add(x, y + 1, z);
        add(x, y, z + 1);
    }

    return 0;
}

I don't fully understand the code below

#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> A(n), B(n), C(n);
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> B[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> C[i];
    }

    sort(A.begin(), A.end(), greater());
    sort(B.begin(), B.end(), greater());
    sort(C.begin(), C.end(), greater());

    using Item = tuple<long long, int, int, int, int>;
    priority_queue<Item> pq;

    auto get = [&](int i, int j, int k)
    {
        return 1ll * A[i] * B[j] + 1ll * B[j] * C[k] + 1ll * C[k] * A[i];
    };
    pq.emplace(get(0, 0, 0), 0, 0, 0, 0);

    for (int i = 0; i < k; i++)
    {
        auto [v, x, y, z, t] = pq.top();
        pq.pop();

        if (i == k - 1)
        {
            cout << v << endl;
            return 0;
        }

        // Why?
        // t == 0: Add (i + 1, j, k), (i, j + 1, k), (i, j, k + 1)
        // t == 1: Add (i, j + 1, k), (i, j, k + 1)
        // t == 2: Add (i, j, k + 1)
        if (t == 0 && x + 1 < n)
        {
            pq.emplace(get(x + 1, y, z), x + 1, y, z, 0);
        }
        if (t <= 1 && y + 1 < n)
        {
            pq.emplace(get(x, y + 1, z), x, y + 1, z, 1);
        }
        if (t <= 2 && z + 1 < n)
        {
            pq.emplace(get(x, y, z + 1), x, y, z + 1, 2);
        }
    }

    return 0;
}

📌 G - Many LCS

Warning

Hard Problems to Tackle Later

// TODO