🧩 AtCoder Beginner Contest 381

TayLockNovember 22, 2024About 7 min

🧩 AtCoder Beginner Contest 381

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Constructive	Constructive	⭐🔥
E	Constructive	Binary Search	🧠🌀
F	Bitmask	Bitmask DP	🌀🧠
G	Math	Math	🌀

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 - 11/22 String

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    string S;
    cin >> N >> S;

    if (N % 2 == 0)
    {
        cout << "No" << endl;
        return 0;
    }

    for (int i = 0; i < N / 2; i++)
    {
        if (S[i] != '1')
        {
            cout << "No" << endl;
            return 0;
        }
    }
    for (int i = N / 2 + 1; i < N; i++)
    {
        if (S[i] != '2')
        {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << (S[N / 2] == '/' ? "Yes" : "No") << endl;

    return 0;
}

📌 B - 1122 String

#include <bits/stdc++.h>

using namespace std;

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

    string S;
    cin >> S;

    if (S.size() % 2 == 1)
    {
        cout << "No" << endl;
        return 0;
    }

    set<char> st;
    for (int i = 0; i < S.size() - 1; i += 2)
    {
        if (S[i] != S[i + 1])
        {
            cout << "No" << endl;
            return 0;
        }

        if (st.count(S[i]))
        {
            cout << "No" << endl;
            return 0;
        }

        st.insert(S[i]);
    }

    cout << "Yes" << endl;

    return 0;
}

📌 C - 11/22 Substring

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    string S;
    cin >> N >> S;

    vector<int> l1(N), r2(N);
    for (int i = 0; i < N - 1; i++)
    {
        l1[i + 1] = S[i] == '1' ? 1 + l1[i] : 0;
    }
    for (int i = N - 1; i > 0; i--)
    {
        r2[i - 1] = S[i] == '2' ? 1 + r2[i] : 0;
    }

    int ans = 1;
    for (int i = 0; i < N; i++)
    {
        if (S[i] == '/')
        {
            ans = max(ans, 1 + 2 * min(l1[i], r2[i]));
        }
    }

    cout << ans << endl;

    return 0;
}

📌 D - 1122 Substring

Tips

Consider subarrays starting from the odd-indexed terms of A and the even-indexed terms separately

Tips

An important fact follows:

For $1 \le l < r \le N$ , if $(A_l, A_{l + 1}, ..., A_{r})$ is a 1122 sequence, then the sequence obtained by removing the last two elements, namely $(A_l, A_{l + 1}, ..., A_{r - 2})$ is also a 1122 sequence

Therefore, the problem can be solved with the Sliding Window trick

For an even number $r = 2, 4, ...$ , let $f(r)$ be the smallest odd number $l (1 \le l \le r + 1)$ such that $(A_l, A_{l + 1}, ..., A_{r})$ forms a 1122 sequence

if $l = r + 1$ , then $(A_l, A_{l + 1}, ..., A_{r})$ is an empty sequence, especially a 1122 sequence, so $f(r)$ is always defined
for $r = 2$ $r = 2$ , we have:
- $l = 1$ if $A_1 = A_2$
- $l = 3$ otherwise

The sought value can be represented using $f(r)$ as:

\max_{r = 2, 4, ...}(r - f(r) + 1)

When we know $f(r - 2)$ , we can find $f(r)$ as follows:

if $A_{r - 1} \neq A_r$ , then $f(r) = r + 1$
if $A_{r - 1} = A_r$ , and if no element among $A_{f(r - 2)}, A_{f(r - 2) + 2}, ..., A_{r - 3}$ equals $A_{r - 1}$ , then $f(r) = f(r - 2)$
if $A_{r - 1} = A_r$ , and if there exists $k \in {f(r - 2), f(r - 2) + 2, ..., r - 3}$ such that $A_{r - 1} = A_k$ , then $f(r) = k + 2$

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

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

    int ans = 0;

    auto calc = [&](int l, int r)
    {
        // last[x] records the last index where value x was seen in a pair
        vector<int> last(2e5 + 10, -2);

        for (; (r + 1) < N; r += 2)
        {
            if (A[r] != A[r + 1])
            {
                l = r + 2;
            }
            else
            {
                l = max(l, last[A[r]] + 2);
            }

            ans = max(ans, r + 2 - l);
            last[A[r]] = r;
        }
    };

    // even-index start
    calc(0, 0);
    // odd-index start
    calc(1, 1);

    cout << ans << endl;

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

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

    int ans = 0;

    for (int t = 0; t < 2; t++)
    {
        vector<bool> e(N);
        for (int i = t, j = t; i < N; i += 2)
        {
            if (j < i)
            {
                j = i;
            }
            while (j + 1 < N && A[j + 1] == A[j] && !e[A[j]])
            {
                e[A[j]] = true;
                j += 2;
            }
            if (i < j)
            {
                e[A[i]] = false;
            }

            ans = max(ans, j - i);
        }
    }

    cout << ans << endl;

    return 0;
}

📌 E - 11/22 Subsequence

Tips

Let $n$ be the answer to some $(L, R)$

any 11/22 string of length at most $n$ is contained in the substring from $L$ -th through $R$ -th characters of S as a subsequence
no 11/22 substring of length greater than $n$ is contained as a subsequence

Using this monotonicity, we can come up with the following binary search approach:

Initially, let $l = -1$ , $r = N + 1$
while $r - l \ge 1$ $r - l \geq 1$ , do the following:
- Let $m = \lfloor (l + r) / 2 \rfloor$
- Check if an 11/22 string of length $2m + 1$ exists as a subsequence within the segment
- If it exists, let $l = m$ ; otherwise, let $r = m$
If the final $l = -1$ , there is no 11/22 string as a subsequence of the current segment. Otherwise, there exists an 11/22 string of length $(2l + 1)$ as a subsequence, which is the longest possible

But, we have not figure out how to solve the following subproblem:

Check if an 11/22 string of length $2m + 1$ exists as a subsequence within the segment

Tips

This subproblem can be solved by doing an appropriate precalculation and referring to it appropriately

Specifically, precalculate the following sequences:

$v_1$ : the monotonically increasing sequence consisting of indices $i$ with $S[i] = 1$
$v_2$ : the monotonically increasing sequence consisting of indices $i$ with $S[i] = 2$
$v_3$ : the monotonically increasing sequence consisting of indices $i$ with $S[i] = /$

Then the subproblem can be solved with an appropriate binary search in a total of $O(\log N)$ time

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<int> v1, v2, v3;
    for (int i = 0; i < N; i++)
    {
        (S[i] == '1' ? v1 : S[i] == '2' ? v2
                                        : v3)
            .push_back(i);
    }

    while (Q--)
    {
        int L, R;
        cin >> L >> R;
        L--;

        auto check = [&](int mid) -> bool
        {
            if (mid == 0)
            {
                // find '/'
                auto it = lower_bound(v3.begin(), v3.end(), L);

                return it != v3.end() && *it < R;
            }

            // find '1'
            auto it1 = lower_bound(v1.begin(), v1.end(), L);
            if (distance(it1, v1.end()) < mid)
            {
                return false;
            }
            int pos1_end = *(it1 + mid - 1);

            // find '/'
            auto it_slash = lower_bound(v3.begin(), v3.end(), pos1_end);
            if (it_slash == v3.end())
            {
                return false;
            }
            int slash_pos = *it_slash;

            // find '2'
            auto it2 = lower_bound(v2.begin(), v2.end(), slash_pos);
            if (distance(it2, v2.end()) < mid)
            {
                return false;
            }
            int pos2_end = *(it2 + mid - 1);

            return pos2_end < R;
        };

        int l = -1, r = N + 1;
        while (l + 1 < r)
        {
            int mid = l + (r - l) / 2;
            if (check(mid))
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }

        cout << (l == -1 ? 0 : 2 * l + 1) << endl;
    }

    return 0;
}

// Better version

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<int> p1, p2;
    for (int i = 0; i < N; i++)
    {
        if (S[i] == '1')
        {
            p1.push_back(i);
        }
        else if (S[i] == '2')
        {
            p2.push_back(i);
        }
    }

    // prefix sum
    vector<int> c1(N + 1), c2(N + 1), cs(N + 1);
    for (int i = 0; i < N; i++)
    {
        c1[i + 1] = c1[i] + (S[i] == '1');
        c2[i + 1] = c2[i] + (S[i] == '2');
        cs[i + 1] = cs[i] + (S[i] == '/');
    }

    while (Q--)
    {
        int L, R;
        cin >> L >> R;
        L--;

        // no '/' between (L, R)
        if (cs[R] - cs[L] == 0)
        {
            cout << 0 << endl;
            continue;
        }

        auto check = [&](int mid) -> bool
        {
            if (c1[R] - c1[L] < mid || c2[R] - c2[L] < mid)
            {
                return false;
            }

            int l = p1[c1[L] + mid - 1];
            int r = p2[c2[R] - mid];

            return l < r && cs[r] - cs[l] > 0;
        };

        int ans = 0;

        int l = 1, r = N;
        while (l <= r)
        {
            int mid = l + (r - l) / 2;
            if (check(mid))
            {
                ans = mid;
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }

        // int ans = *std::ranges::partition_point(std::ranges::iota_view(1, N), [&](int x){
        //     if (c1[R] - c1[L] < x)
        //     {
        //         return false;
        //     }
        //     if (c2[R] - c2[L] < x)
        //     {
        //         return false;
        //     }

        //     int l = p1[c1[L] + x - 1];
        //     int r = p2[c2[R] - x];

        //     return l < r && cs[r] - cs[l] > 0;
        // }) - 1;

        ans = ans * 2 + 1;

        cout << ans << endl;
    }

    return 0;
}

📌 F - 1122 Subsequence

Tips

Note that the maximum possible subsequence of $A$ that is a 1122 sequence is $2 \times 20 = 40$ , because $1 \le A_i \le 20$

Thus, the solution can be built using Bitmask Dynamic Programming where each bit represents whether a specific number is included

Tips

Let's define:

dp[mask]: the minimum index $r$ such that a valid 1122 sequence ending before or at $r$ can be formed from the numbers in mask

Each bit in mask corresponds to an integer in the range $[1, 20]$

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

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

    // Determines the number of unique possible values in A,
    // used for bitmask size 1 << M
    int M = *max_element(A.begin(), A.end()) + 1;

    // nxt[i][j] = first index >= j where value i appears in A
    vector<vector<int>> nxt(M, vector<int>(N + 1));
    for (int i = 0; i < M; i++)
    {
        nxt[i][N] = N;
        for (int j = N - 1; j >= 0; j--)
        {
            nxt[i][j] = A[j] == i ? j : nxt[i][j + 1];
        }
    }

    // dp[mask]: the minimum right endpoint you can reach
    // using a valid 1122 sequence for the subset mask (bitmask)
    vector<int> dp(1 << M, N + 1);
    // Start with empty subset
    dp[0] = 0;

    int ans = 0;

    for (int mask = 0; mask < (1 << M); mask++)
    {
        if (dp[mask] > N)
        {
            continue;
        }

        ans = max(ans, __builtin_popcount(mask) * 2);

        // try to extend mask by adding a new number 'i'
        for (int i = 0; i < M; i++)
        {
            // i is already in mask
            if (mask >> i & 1)
            {
                continue;
            }

            // ns: new mask after adding 'i'
            int ns = mask | 1 << i;

            // Start searching from the position right after the end of the sequence for subset
            int nj = dp[mask];
            // Find the first occurrence of value i after position nj
            nj = nxt[i][nj] + 1;

            if (nj > N)
            {
                // If we can't find a valid first occurrence of i
                continue;
            }

            // Find the second occurrence of value i after the first
            nj = nxt[i][nj] + 1;
            // Now, we have found two positions where value i occurs —
            // satisfying the requirement to add i, i to the 1122 sequence

            // Update the smallest position after inserting value i twice
            dp[ns] = min(dp[ns], nj);
        }
    }

    cout << ans << endl;

    return 0;
}

📌 G - Fibonacci Product

Warning

Hard Problems to Tackle Later

// TODO