🧩 AtCoder Beginner Contest 398

TayLockMarch 22, 2025About 8 min

🧩 AtCoder Beginner Contest 398

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
E	Bipartite graph	BFS	⭐🔥🛠️
F	Palindrome	Manacher's Algorithm	⭐🔥🛠️
G	Graph/Bipartite Graph	Simulation	🌀

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 - Doors in the Center

If N is even:
- The sought string looks like ----==----
- Place == in the middle
- Place $(N - 2)$ -'s to their left and right
If N is odd:
- The sought string looks like ----=----
- Place = in the middle
- Place $(N - 1)$ -'s to their left and right

// TayLock

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    string res = string(n, '-');
    if (N % 2 == 1) {
        res[N / 2] = '=';
    } else {
        res[N / 2 - 1] = '=';
        res[N / 2] = '=';
    }

    cout << res << endl;

    return 0;
}

// New version

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    string res(n, '-');
    res[n / 2] = '=';
    res[(n - 1) / 2] = '=';

    cout << res << endl;

    return 0;
}

Key Features:

math trick: $n / 2$ and $(n - 1) / 2$ automatically choose the correct center positions for both odd and even values of n, ensuring only $1$ or $2$ adjacent =
are placed

📌 B - Full House 3

Rephrase the condition, first, count how many cards with each integer there are, then a full house can be formed if and only if:

there are at least $3$ cards with an integer $x$ written on it
there are at least $2$ cards with an integer $y$ with $x \neq y$ written on it

// TayLock

#include <bits/stdc++.h>

using namespace std;

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

    vector<int> card(13, 0);
    for (int i = 0; i < 7; i++)
    {
        int c;
        cin >> c;
        c--;

        card[c] += 1;
    }

    // the condition can be checked by sorting the cards by frequencies
    sort(card.rbegin(), card.rend());
    // and check the most frequent cards and the second most frequent cards
    if (card[0] >= 3 && card[1] >= 2)
    {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

📌 C - Uniqueness

// TayLock

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    // `key` - person's integer, `value` - `{frequency, person's label}`
    map<long long, pair<int, int>> mp;
    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num;

        if (mp.count(num))
        {
            int c = mp[num].first;
            mp[num] = make_pair(c + 1, i + 1);
        } else {
            mp[num] = make_pair(1, i + 1);
        }
    }

    long long curMax = -1;
    int res = -1;
    for (auto p : mp)
    {
        // satisfy the condition "None of the other N−1 people has the same integer as themselves,"
        if (p.second.first == 1)
        {
            if (p.first > curMax)
            {
                curMax = p.first;
                res = p.second.second;
            }
        }
    }

    cout << res << endl;

    return 0;
}

// New version

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    map<int, int> cnt;

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

    int res = -1;
    for (int i = 0; i < n; i++)
    {
        if (cnt[nums[i]] == 1)
        {
            if (res == -1 || nums[i] > nums[res - 1])
            {
                res = i + 1;
            }
        }
    }

    cout << res << endl;

    return 0;
}

Key Features:

cnt[nums[i]] == 1: None of the other N−1 people has the same integer as themselves
res == -1 || nums[i] > nums[res - 1]: find the one with the greatest integer, and print that person's label

📌 D - Bonfire

If we move the smoke according to the wind, advancing time $t$ costs a time complexity of $O(t)$ , for a total cost of $O(t^2)$ , which does not meet the execution time limit

So, we can fix the smoke at the position that it appears, and move the fire and the Takahashi according to the wind(the opposite direction, of course)

we need follow these steps:

First, generate smoke at cell $(0,0)$
Initialize the position of the first at $(0,0)$ and Takahashi's position at $(R,C)$
For each time $t = 1, 2, ..., N$ $t = 1, 2, ..., N$ , repeat the following rule:
- Move the fire and Takahashi according to the following rule:
  - If $S_i$ == N, move from $(r,c)$ to $(r + 1, c)$
  - If $S_i$ == W, move from $(r,c)$ to $(r, c + 1)$
  - If $S_i$ == S, move from $(r,c)$ to $(r - 1, c)$
  - If $S_i$ == E, move from $(r,c)$ to $(r, c - 1)$
- Generate smoke at the current position of the fire, and manage the set of the positions of the generated smoke in a data structure like set
- Print 1 if the current Takahashi's position has smoke, and 0 otherwise, using function .find()

So that we only need to move Two objects, and the time complexity is reduced

// TayLock

#include <bits/stdc++.h>

using namespace std;

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

    long long n, x1, y1;
    cin >> n >> x1 >> y1;
    string s;
    cin >> s;

    long long x0 = 0, y0 = 0;

    set<pair<long long, long long>> smoke;
    smoke.insert(make_pair(x0, y0));
    for (auto c : s)
    {
        switch (c)
        {
        case 'N':
            x0 += 1;
            x1 += 1;
            break;
        case 'S':
            x0 -= 1;
            x1 -= 1;
            break;
        case 'W':
            y0 += 1;
            y1 += 1;
            break;
        case 'E':
            y0 -= 1;
            y1 -= 1;
            break;
        }

        smoke.insert(make_pair(x0, y0));

        if (smoke.find(make_pair(x1, y1)) != smoke.end())
        {
            cout << 1;
        }
        else
        {
            cout << 0;
        }
    }

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

    int N, R, C;
    cin >> N >> R >> C;
    string S;
    cin >> S;

    set<pair<int, int>> smoke;
    // the position of the fire
    int x = 0, y = 0;
    smoke.insert({x, y});

    for (int i = 0; i < N; i++)
    {
        // move the fire in the opposite direction than the wind
        switch (S[i])
        {
        case 'N':
            x++;
            break;
        case 'W':
            y++;
            break;
        case 'S':
            x--;
            break;
        case 'E':
            y--;
            break;
        default:
            break;
        }

        // Generate new smoke at the current position of fire
        smoke.insert({x, y});

        // Check if Takahashi's position has smoke
        cout << (smoke.count({R + x, C + y}));
    }

    cout << "\n";

    return 0;
}

What I got from this question:

the relative coordinates: the relative coordinates between the fire and Takahashi is fixed, so we only need to update the current position $(x, y)$ of the fire, and use $(R + x, C + y)$ to get the position of Takahashi
c++:
- The find() function is used to find the position of an element in a set. It returns an iterator pointing to the element if it is found, or an iterator to the end of the set if the element is not found
- The count() function is used to check if an element exists in the set and returns the number of occurrences of the element. Since a set only allows unique elements, the return value is always 0 or 1

📌 E - Tree Game

For this question, a tree is a bipartite graph:

If the partite sets have sizes $A$ and $B$ , then one can add at most $AB - (N - 1)$ edges
The order of adding edges does not affect to whether one can add an edge

So, this question is equivalent to:

alternately choosing one option from $AB - (N - 1)$ $A B - (N - 1)$ choices, and the one who are unable to choose loses
- If $AB - (N - 1)$ is odd, the player who makes the move first wins
- If $AB - (N - 1)$ is even, the player who makes the move second wins

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;

    // adjacency list for the tree
    vector<vector<int>> adj(n);
    // adjacency matrix for quick edge existence checks
    vector<vector<bool>> is_connected(n, vector<bool>(n, false));

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

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

        is_connected[u][v] = is_connected[v][u] = true;
    }

    vector<int> visited(n, -1);
    queue<int> q;
    visited[0] = 0;
    q.push(0);

    // Perform BFS to 2-color the tree (color 0 or 1)
    while (!q.empty())
    {
        int u = q.front();
        q.pop();

        for (auto v : adj[u])
        {
            if (visited[v] == -1)
            {
                visited[v] = visited[u] ^ 1;
                q.push(v);
            }
        }
    }

    // If the partite sets have sizes $A$ and $B$, then one can add at most $AB - (N - 1)$ edges
    int cur = 0;
    int A = count(visited.begin(), visited.end(), 0);
    int B = count(visited.begin(), visited.end(), 1);

    // If $AB - (N - 1)$ is odd, the player who makes the move first wins
    // If $AB - (N - 1)$ is even, the player who makes the move second wins
    if ((A * B - (n - 1)) % 2 == 0)
    {
        cout << "Second" << endl;
        cur = 1;
    }
    else
    {
        cout << "First" << endl;
        cur = 0;
    }

    // Game Simulation
    int x = 1, y = 0;
    while (true)
    {
        // Player alternates making legal moves.
        if (cur == 0)
        {
            // Find the first pair of vertices that are not connected and have different colors
            // brute-force
            while (is_connected[x][y] || visited[x] == visited[y])
            {
                y++;
                if (y == x)
                {
                    x++;
                    y = 0;
                }
            }
            is_connected[x][y] = is_connected[y][x] = true;
            cout << y + 1 << " " << x + 1 << endl;
        }
        else
        {
            int u, v;
            cin >> u >> v;

            // Game ends
            if (u == -1)
            {
                break;
            }

            u--;
            v--;

            is_connected[u][v] = is_connected[v][u] = true;
        }

        cur ^= 1;
    }

    return 0;
}

What I got from this question:

The bipartite graph: a graph without an odd cycle
- This is equivalent to one can paint vertices in two colors so that no edge connects vertices of the same color
- For such a graph, one can partition the vertex set into two sets by the color(called partite sets or simply parts)
- The partite sets of a connected bipartite graph are unique, and they can be found by performing DFS or BFS from an arbitrary vertex, as shown in the code

Possible Optimizations:

Instead of scanning all $O(N^2)$ pairs, we could pre-compute candidate edges

// pre-compute candidate edges
set<pair<int, int>> moves;

for (int i = 0; i < n; i++)
{
    for (int j = i + 1; j < n; j++)
    {
        if (visited[i] != visited[j])
        {
            if (moves.find(make_pair(i, j)) != moves.end())
            {
                moves.insert(make_pair(i, j));
            }
        }
    }
}

📌 F - ABCBA

The concatenation of S and reversed S is obviously a palindrome, so the length of a sought string is at most $2 \times |S|$

Consider the property of a palindrome $S_1S_2...S_{|S|}T_1T_2...T_k$ of length $|S| + k(0 \le k \le |S|)$ that has a prefix of S, by definition of palindrome, we obtain the following equations:

$S_1 = T_k$
$S_2 = T_{k - 1}$
...
$S_k = T_1$
$S*{k + 1} = S*{|S|}$
...
$S_{\lfloor {(|S| + k + 1) / 2} \rfloor} = S_{\lfloor {(|S| + k + 2 / 2)} \rfloor}$

In other words, the last $(|S| - k)$ characters of S must form a palindrome, and $T_1 \, T_2 \, ..., T_k$ are uniquely determined by S

Now the problem has been boiled down to the following:

Find the longest suffix of S that is a palindrome
There are various ways to solve this question:
- Manacher's Algorithm
- Z Algorithm

// Manacher's Algorithm

#include <bits/stdc++.h>

using namespace std;

vector<int> manacher(string s)
{
    string t = "#";
    for (auto c : s)
    {
        t += c;
        t += '#';
    }

    int n = t.size();
    vector<int> r(n, 0);

    for (int i = 0, j = 0; i < n; i++)
    {
        if (2 * j - i >= 0 && j + r[j] > i)
        {
            r[i] = min(r[2 * j - i], j + r[j] - i);
        }

        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]])
        {
            r[i]++;
        }

        if (i + r[i] > j + r[j])
        {
            j = i;
        }
    }

    return r;
}

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

    string s;
    cin >> s;

    auto r = manacher(s);

    int n = s.size();
    int l = 0;
    while (r[l + n] < n - l + 1)
    {
        l++;
    }

    auto ans = s, t = s.substr(0, l);
    reverse(t.begin(), t.end());
    copy(t.begin(), t.end(), back_inserter(ans));

    cout << ans << endl;

    return 0;
}

📌 G - Not Only Tree Game

Since the given graph does not contain an odd cycle, each connected component forms a bipartite graph. Now consider the following $5$ characteristic values of the graph:

$x$ : the number of edges that can be added without changing the connectivity while preserving the bipartiteness
$ee$ : the number of connected components where the number of vertices in both parts are both even
$oe$ : the number of connected components where the number of vertices in both parts are both odd
$eo$ : the number of connected components with two or more vertices, where the number of vertices in one part is even and the other is odd
$iso$ : the number of connected components with one vertex

Then the winner can be determined as follows:

If $N$ is odd: the first player wins if $oo + x$ is odd, and the second does if it is even
If $N$ is even and $eo = 0$ : the first player wins if $iso / 2 + x$ is odd, and the second does if it is even
If $N$ is even and $1 \le eo \le 2$ : the first player always wins
If $N$ is even and $eo \ge 3$ : the first player wins if $oo + x$ is odd, and the second does if it is even

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

    if (n % 2 == 1)
    {
        if (m % 2 == 0)
        {
            cout << "Takahashi" << endl;
        }
        else
        {
            cout << "Aoki" << endl;
        }
        return 0;
    }

    int cnt_odd = 0;
    int cnt_even = 0;
    int cnt_single = 0;
    int pariry = 0;
    vector<int> f(n, -1);
    for (int s = 0; s < n; s++)
    {
        if (f[s] != -1)
        {
            continue;
        }

        queue<int> q;
        f[s] = 0;
        q.push(s);

        vector<int> cnt(2, 0);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();

            cnt[f[u]]++;

            for (auto v : adj[u])
            {
                if (f[v] == -1)
                {
                    f[v] = f[u] ^ 1;
                    q.push(v);
                }
            }
        }

        if (cnt[0] + cnt[1] == n)
        {
            if ((1ll * cnt[0] * cnt[1] - m) % 2 == 0)
            {
                cout << "Takahashi" << endl;
            }
            else
            {
                cout << "Aoki" << endl;
            }
            return 0;
        }

        if ((cnt[0] + cnt[1]) % 2 == 1)
        {
            cnt_odd++;
        }
        else
        {
            cnt_even++;
            pariry ^= cnt[0] % 2;
        }

        if (cnt[0] + cnt[1] == 1)
        {
            cnt_single++;
        }
    }

    if (cnt_odd == 0)
    {
        if (m % 2 == pariry)
        {
            cout << "Takahashi" << endl;
        }
        else
        {
            cout << "Aoki" << endl;
        }
        return 0;
    }

    if (cnt_single < cnt_odd - 2)
    {
        if (m % 2 == 0)
        {
            cout << "Takahashi" << endl;
        }
        else
        {
            cout << "Aoki" << endl;
        }
        return 0;
    }

    if (cnt_single < cnt_odd || m % 2 == (pariry ^ (cnt_odd % 4 == 0)))
    {
        cout << "Aoki" << endl;
    }
    else
    {
        cout << "Takahashi" << endl;
    }

    return 0;
}