🧩 AtCoder Beginner Contest 403

TayLockApril 27, 2025About 6 min

🧩 AtCoder Beginner Contest 403

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Maximum Independent Set on a Path	Path DP/DP	⭐🔥
E	Trie	Trie	🌀🧠⭐🔥
F	String Constructive	DP	🌀
G	Dynamic Segment Tree	Dynamic Segment Tree	🌀

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 - Odd Position Sum

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    int ans = 0;

    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num;

        ans += i & 1 ? 0 : num;
    }

    cout << ans << endl;

    return 0;
}

📌 B - Four Hidden

Details

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    int ans = 0;

    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num;

        ans += i & 1 ? 0 : num;
    }

    cout << ans << endl;

    return 0;
}

// Better version
#include <bits/stdc++.h>

using namespace std;

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

    string T, U;
    cin >> T >> U;

    for (int i = 0; i <= T.size() - U.size(); i++)
    {
        bool ok = true;
        for (int j = 0; j < U.size(); j++)
        {
            if (T[i + j] != U[j] && T[i + j] != '?')
            {
                ok = false;
                break;
            }
        }

        if (ok)
        {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;

    return 0;
}

📌 C - 403 Forbidden

#include <bits/stdc++.h>

using namespace std;

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

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

    map<int, set<int>> mp;

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

        if (a == 1)
        {
            int x, y;
            cin >> x >> y;

            mp[x].insert(y);
        }
        else if (a == 2)
        {
            int x;
            cin >> x;

            mp[x].insert(-1);
        }
        else
        {
            int x, y;
            cin >> x >> y;

            if (mp[x].count(-1) == 1 || mp[x].count(y) == 1)
            {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
    }

    return 0;
}

📌 D - Forbidden Difference

If $D = 0$

If $D = 0$ , then $|A_i - A_j| = 0 \iff A_i = A_j$ , so it is sufficient to exclude repeated values in $A$

If $A$ has $X$ distinct values, each of them can be retained only once, so $B$ can have a length of at most $X$ . Thus, at least $(N - X)$ operations are required

Tips

dp0: The maximum number of elements kept if the previous number was NOT selected
dp1: The maximum number of elements kept if the previous number WAS selected

At every number $A[l]$ , we have two options:

Select $A[l]$
Skip $A[l]$

DP Transition

Case 1: abs(A[l] - lst) == 0

Current number and last selected number differ by exactly D -> Conflict happens -> We must skip the current one OR select the current one but skip the last one

long long new_dp0 = max(dp0, dp1);
long long new_dp1 = dp0 + count;
dp0 = new_dp0;
dp1 = new_dp1;

Case 2: abs(A[l] - lst) != D

Current number and last number do NOT differ by D -> No conflict -> We can freely choose to select or not select the current number

dp0 = max(dp0, dp1);
dp1 = dp0 + count;

// Better version
#include <bits/stdc++.h>

using namespace std;

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

    int N, D;
    cin >> N >> D;

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

    // If D = 0, the problem becomes "remove duplicates"
    if (D == 0)
    {
        sort(A.begin(), A.end());
        cout << A.end() - unique(A.begin(), A.end()) << endl;
        return 0;
    }

    // Group numbers by their value modulo D
    // Inside each group, sort numbers by their actual value ascending
    // - Numbers with the same mod D do not conflict
    // - Conflicts happen across different groups, especially adjacent numbers differing exactly by D
    sort(A.begin(), A.end(), [&](int i, int j)
         { return pair(i % D, i) < pair(j % D, j); });

    // dp0 = maximum number of elements kept if the previous number is not selected
    // dp1 = maximum number of elements kept if the previous number is selected
    long long dp0 = 0, dp1 = 0;
    // lst = last processed number (initialized to avoid false conflict at the start)
    int lst = -D - 1;

    for (int l = 0, r = 0; l < N; l = r)
    {
        // Process consecutive blocks of identical numbers [l, r)
        while (r < N && A[l] == A[r])
        {
            r++;
        }

        // r - l = number of times the value A[l] appears
        int count = r - l;

        if (abs(A[l] - lst) == D)
        {
            // Conflict: cannot pick both
            // dp0 = max(dp0, dp1) (skip current)
            // dp1 = dp0 (before skip) + (count of current number) (pick current block)
            long long new_dp0 = max(dp0, dp1);
            long long new_dp1 = dp0 + count;
            dp0 = new_dp0;
            dp1 = new_dp1;
        }
        else
        {
            // No conflict: just a normal transition
            // dp0 = max(dp0, dp1) (best so far without selecting)
            // dp1 = dp0 + (count of current number) (choose current freely)
            dp0 = max(dp0, dp1);
            dp1 = dp0 + count;
        }

        lst = A[l];
    }

    cout << N - max(dp0, dp1) << endl;

    return 0;
}

📌 E - Forbidden Prefix

Warning

Hard Problems to Tackle Later

Tips

This problem is an exercise of trie, which is a data structure that represents a list of strings as a rooted tree. Information stored on each vertex allows us efficient manipulations regarding prefixes

A trie is constructed so that each vertex represents a character, and a path from the root to another vertex corresponds to a string. Strings with common prefixes share a path from the root to some of their ancestor

Each vertex of the trie maintain the following information:

The character represented by the vertex
The list of children of the vertex
The list of strings that is accepted at the vertex; i.e. the list of indices of the original list, that coincides with the string represented by the path from the root to the vertex

We maintain all the given strings $S_i$ in a single trie $T$ , regardless of which of $X$ and $Y$ it will belong to

Also, maintain a set $Z$ , which stores "the strings $S_i$ contained in $Y$ that has an element $S_j$ in $X$ as a prefix"

The sought answer is:

|Y| - |Z|

Processing query 1

If the subtree rooted at the vertex accepting $S_i \in X$ contains a vertex that accepts $S_j \in Y$ , then we add $S_j$ to $Z$

We keep for each vertex $v$ in $T$ , the set of the elements $S_j \in Y$ to be added to $Z$ when an $S_i \in X$ accepted by $v$ is added for the next time. This can be updated by, every time adding $S_j \in Y$ to $T$ , for all the vertex $v$ that accepts a prefix of $S_j$ , adding $S_j$ to $Z_v$ When adding $S_i \in X$ , add all $j \in Z_v$ to $Z$ and empty $Z_v$ , where $v$ is the vertex accepting $S_i$ . Since $Z_v$ can have up to $Q$ elements, so it seems inefficient at a glance, but the total number of times that $S_j$ is taken out of any $Z_v$ is at most $S_j$ times. Therefore, the overall time complexity is $O(\sum_{i = 1}^{Q}(|S_i|\log(Q)))$

Processing query 2

It is sufficient to check if there is a vertex $v$ that accepts a prefix of $S_i \in X$ and also accepts an $S_j \in X$

We maintain a flag $f_v$ for each vertex $v$ in $T$ signifying whether $X$ contains a string that is accepted by that vertex

When adding a string of $X$ to $T$ , we set $f_v = true$ for the vertex $v$ accepting that string

When adding a string of $Y$ to $T$ , we check if there exists an ancestor $v$ of the vertex that accepts its prefix such that $f_v = true$

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 5e5 + 10;

int tot = 1;
// p is node id, trie[p][c] is next node via character c
int trie[N][26];
// number of Type 2 strings passing through this node
int cnt[N];
// whether this node is "blocked" (i.e., a prefix has been inserted by Type 1)
bool vis[N];

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

    int Q;
    cin >> Q;

    int ans = 0;
    for (int i = 0; i < Q; i++)
    {
        int T;
        string S;
        cin >> T >> S;

        // Insert into the Trie and mark nodes `vis`
        // and adjust `cnt` to remove invalid paths
        if (T == 1)
        {
            // insert S into the Trie
            int p = 1;
            for (auto c : S)
            {
                int &q = trie[p][c - 'a'];
                if (!q)
                {
                    tot++;
                    q = tot;
                }
                p = q;

                // If during insertion you reach a node that is already
                // path already blocked
                if (vis[p])
                {
                    break;
                }
            }

            // If the endpoint wasn't already blocked
            if (!vis[p])
            {
                // block the node
                vis[p] = true;

                // Find how many Type 2 strings were passing through here
                int d = cnt[p];
                ans -= d;

                // Then decrement all counts along the prefix by d
                p = 1;
                for (auto c : S)
                {
                    cnt[p] -= d;
                    p = trie[p][c - 'a'];
                }
            }
        }
        // Insert into the Trie normally, increment counters
        // unless the path is blocked by a `vis` node
        else
        {
            // insert S into the Trie
            int p = 1;
            for (auto c : S)
            {
                int &q = trie[p][c - 'a'];
                if (!q)
                {
                    q = ++tot;
                }
                p = q;

                // If during insertion you reach a node that is already
                // path already blocked
                if (vis[p])
                {
                    break;
                }
            }

            // If you reach the end without hitting a blocked node
            if (!vis[p])
            {
                // Increment the answer ans++ because this is a valid new Type 2 string
                ans++;

                // Update counters cnt[p]++ along the path
                p = 1;
                cnt[p]++;
                for (auto c : S)
                {
                    p = trie[p][c - 'a'];
                    cnt[p]++;
                }
            }
        }

        cout << ans << endl;
    }

    return 0;
}

📌 F - Shortest One Formula

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Odd Position Sum Query

Warning

Hard Problems to Tackle Later

// TODO