🧩 AtCoder Beginner Contest 394

TayLockFebruary 22, 2025About 5 min

🧩 AtCoder Beginner Contest 394

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
E	Shortest Path	BFS	🧠🔥
F	Tree DP	Tree DP/DFS	🔥

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 - 22222

#include <bits/stdc++.h>

using namespace std;

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

    string s;
    cin >> s;

    string ans = "";
    for (auto c : s)
    {
        if (c == '2')
        {
            ans += c;
        }
    }

    cout << ans << endl;

    return 0;
}

📌 B - cat

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

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

    sort(s.begin(), s.end(), [&](string i, string j){
        return i.size() < j.size();
    });

    string ans = "";
    for (auto a : s)
    {
        ans += a;
    }

    cout << ans << endl;

    return 0;
}

📌 C - Debug

#include <bits/stdc++.h>

using namespace std;

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

    string s;
    cin >> s;

    int n = s.size();

    for (int i = 0; i < n - 1; i++)
    {
        if (s[i] == 'W' && s[i + 1] == 'A')
        {
            s[i] = 'A';
            s[i + 1] = 'C';

            int l = i;
            while (l - 1 >= 0 && s[l - 1] == 'W')
            {
                s[l - 1] = 'A';
                s[l] = 'C';

                l--;
            }
        }
    }

    cout << s << endl;

    return 0;
}

📌 D - Colorful Bracket Sequence

#include <bits/stdc++.h>

using namespace std;

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

    string s;
    cin >> s;

    stack<char> st;
    for (auto c : s)
    {
        if (!st.empty() && ((st.top() == '(' && c == ')') || (st.top() == '[' && c == ']') || (st.top() == '<' && c == '>')))
        {
            st.pop();
        } else {
            st.push(c);
        }
    }

    cout << (st.empty() ? "Yes" : "No") << endl;

    return 0;
}

📌 E - Palindromic Shortest Path

Tips

For a lowercase English letter $c$ and a palindrome $S$ , the string obtained by concatenating $c$ , $S$ , and $c$ in this order forms a palindrome

Conversely, a string of length at least two is a palindrome if and only if the first and the last characters are the same, and the string obtained by removing the first and last characters still forms a palindrome

Let $G$ be a graph with $N^2$ vertices ${(1, 1), (1, 2), ..., (1, N), (2, 1), ..., (N, N)}$ . We will decide the edges so that vertex $(i, j)$ corresponds to a path from vertex $i$ to vertex $j$ in the graph given in the problem statement

For convenience, add another vertex $S$ to $G$ for it to have $N^2 + 1$ . Then the answer to the original problem for an integer pair $(i, j)$ is the length of a shortest path from $S$ to $(i, j)$ in the graph with edges added as follows:

An edge from $S$ to $(i, j)$ of weight $0$ for each $i$
An edge from $S$ to $(i, j)$ for each $(i, j)$ with $C_{i, j} \ne '-'$
An edge from $(i, j)$ $(i, j)$ to $(k, l)$ $(k, l)$ of weight $2$ $2$ for each $(i, j, k, l)$ $(i, j, k, l)$ with $C_{k, i} \ne '-'$ $C_{k, i} \neq =^{'} -^{'}$ , $C_{j, l} \ne '-'$ $C_{j, l} \neq =^{'} -^{'}$ , $C_{k, i} = C_{j, l}$ $C_{k, i} = C_{j, l}$
- means a new path: $k \rightarrow i \rightarrow j \rightarrow l$
- correspond to adding the same character at the beginning and the end of a palindrome to obtain a new palindrome with the length increased by two

$G$ has $O(N^2)$ vertices, each of degree $O(N^2)$ , so it has $O(N^4)$ edges, allowing $O(N^4)$ -time BFS to find the answer

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    vector<vector<char>> c(n, vector<char>(n));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> c[i][j];
        }
    }

    vector<vector<int>> dist(n, vector<int>(n, 1e9));
    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++)
    {
        q.push({i, i});
        dist[i][i] = 0;
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j || c[i][j] == '-')
            {
                continue;
            }

            q.push({i, j});
            dist[i][j] = 1;
        }
    }

    while (!q.empty())
    {
        auto p = q.front();
        q.pop();

        int i = p.first, j = p.second;

        for (int k = 0; k < n; k++)
        {
            for (int l = 0; l < n; l++)
            {
                // There is no edge from k->i or j->l
                if (c[k][i] == '-' || c[j][l] == '-')
                {
                    continue;
                }
                // The characters at both ends of the edges do not match
                if (c[k][i] != c[j][l])
                {
                    continue;
                }
                // adding characters from both sides of the path
                if (dist[i][j] + 2 <= dist[k][l])
                {
                    dist[k][l] = dist[i][j] + 2;
                    q.push({k, l});
                }
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << (dist[i][j] == 1e9 ? -1 : dist[i][j]) << " \n"[j == n - 1];
        }
    }

    return 0;
}

📌 F - Alkane

Note

Since the subgraph of the tree must form another tree, once the vertex subset is fixed, the edge set is unique (if any). Thus we will identify a subgraph that forms a tree and its vertex set (that yields a tree by choosing edges appropriately)

Tips

A graph is an alkane if and only if the graph has $5$ or more vertices and is a general alkane, so it is sufficient to find the maximum vertices in a general alkane

We call a graph (with one or more vertices) general alkane if and only if:

the graph is an undirected tree
every vertex has a degree $1$ or $4$

Tips

For a non-root vertex $v$ , let $dp[v]$ be the maximum number of vertices in a subtree consisting of ancestors of $v$ (possibly including $v$ itself) such that adding $v$ results in a general alkane

Suppose that we have already evaluated all the ancestors of $v$ (except for $v$ )

How can we compute $dp[v]$ :

Case 1: if $v$ $v$ 's degree is $1$ $1$
- only $v$ 's parent is adjacent to $v$ , so the number of vertices is $1$
- then the maximum number of vertices is $dp[u] + 1$ , where $u$ is the vertex adjacent to $v$
Case 2: if $v$ $v$ 's degree is $4$ $4$
- then the vertices adjacent to $v$ is $v$ 's parent and three children of $v$ , so $v$ must have at least $3$ children
- if i does, we can pick children $u_1, u_2, u_3$ together with, for each children, a vertex set to which adding the parent $v$ of the child forms a general alkane
- by maximizing the number of vertices in those vertex set by picking three children $u$ with largest values of $dp[u]$ , we can obtain a conforming vertex set with $dp[u_1] + dp[u_2] + dp[u_3] + 1$ vertices

A more understandable version

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    vector<vector<int>> adj(n, vector<int>());
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int ans = -1;

    vector<vector<int>> dp(n, vector<int>(5, -1e8));

    auto dfs = [&](auto &&self, int u, int p) -> void
    {
        for (auto v : adj[u])
        {
            if (v == p)
            {
                continue;
            }

            self(self, v, u);
        }

        dp[u][0] = 1;
        vector<int> child;
        for (auto v : adj[u])
        {
            if (v == p)
            {
                continue;
            }

            ans = max(ans, dp[v][3] + 1);
            child.push_back(dp[v][3]);
        }

        sort(child.rbegin(), child.rend());

        int k = child.size();
        if (k >= 4)
        {
            ans = max(ans, child[0] + child[1] + child[2] + child[3] + 1);
            ans = max(ans, child[0] + child[1] + child[2] + 2);
            ans = max(ans, child[0] + child[1] + 3);
            ans = max(ans, child[0] + 4);
            ans = max(ans, 5);
        }
        if (k >= 1)
        {
            ans = max(ans, child[0] + 1);
        }
        if (k >= 3)
        {
            dp[u][3] = max(dp[u][3], child[0] + child[1] + child[2] + 1);
            dp[u][3] = max(dp[u][3], child[0] + child[1] + 2);
            dp[u][3] = max(dp[u][3], child[0] + 3);
            dp[u][3] = max(dp[u][3], 4);
        }
    };

    dfs(dfs, 0, -1);

    cout << ans << endl;

    return 0;
}

// Better version

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    vector<vector<int>> adj(n, vector<int>());
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int ans = -1;

    auto dfs = [&](auto &&self, int u, int p) -> int
    {
        vector<int> child;
        for (auto v : adj[u])
        {
            if (v == p)
            {
                continue;
            }

            child.push_back(self(self, v, u));
        }

        sort(child.rbegin(), child.rend());

        int k = child.size();
        if (k >= 1 && child[0] > 1)
        {
            ans = max(ans, child[0] + 1);
        }
        if (k >= 4)
        {
            ans = max(ans, child[0] + child[1] + child[2] + child[3] + 1);
        }

        return k < 3 ? 1 : child[0] + child[1] + child[2] + 1;
    };

    dfs(dfs, 0, -1);

    cout << ans << endl;

    return 0;
}

📌 G - Dense Buildings

Warning

Hard Problems to Tackle Later

// TODO