🧩 AtCoder Beginner Contest 393

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
E	GCD	Math	🔥
F	LIS (Longest monotonically Increasing Subsequence)	DP	🔥

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 - Poisonous Oyster

393A

#include <bits/stdc++.h>

using namespace std;

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

    string s, t;
    cin >> s >> t;

    if (s == "sick" && t == "sick")
    {
        cout << 1 << endl;
    }
    else if (s == "sick" && t == "fine")
    {
        cout << 2 << endl;
    }
    else if (s == "fine" && t == "sick")
    {
        cout << 3 << endl;
    }
    else
    {
        cout << 4 << endl;
    }

    return 0;
}

📌 B - A..B..C

393B

#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();
    int ans = 0;

    for (int i = 0; i < n - 2; i++)
    {
        for (int j = i + 1; j < n - 1; j++)
        {
            for (int k = j + 1; k < n; k++)
            {
                if (j - i == k - j && s[i] == 'A' && s[j] == 'B' && s[k] == 'C')
                {
                    ans++;
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

📌 C - Make it Simple

393C

#include <bits/stdc++.h>

using namespace std;

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

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

    set<pair<int, int>> st;
    int ans = 0;
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        if (u == v)
        {
            ans++;
            continue;
        }

        if (u > v)
        {
            swap(u, v);
        }

        if (st.count({u, v}))
        {
            ans++;
        }
        else
        {
            st.insert({u, v});
        }
    }

    cout << ans << endl;

    return 0;
}

📌 D - Swap to Gather

393D

Tips

Fro each 0 in $S$, consider the number of 1 to its left(let it be $l$) and the number of 1 to its right(let it be $r$):

• If $l < r$, it's better to bring 0 to the left of the 1 chunk
• If $l > r$, it's better tp bring 0 to the right of the 1 chunk

Thus, the answer is the number of $\min(l, r)$ for all 0

Let:

• $C_0$ be the number of 0 in $S$
• $C_1$ be the number of 1 in $S$, and $C_1 = N - C_0$

For each $i$ ($1 \le i \le C_0$), let $d_i$ be the number of 1s to the right of the $i$-th 0 from the left:

• $d_0 = 0$
• $d_{C_0 + 1} = C_1$
• then $d_0 \le d_1 \le d_2 \le ... \le d_{C_0} \le d_{C_0 + 1}$

Tips

Let us reinterpret the problem according to the value $d_i$

First, swapping the same character is meaningless, so the operation in the original problem statement is equivalent to performing one of the following operations against $d_i$:

• Choose one $i$ ($1 \le i \le C_0$) with $d_{i - 1} < d_i$, and decrease $d_i$ by $1$
• Choose one $i$ ($1 \le i \le C_0$) with $d_i < d_{i + 1}$, and increase $d_i$ bu $1$

The termination condition is as follows:

• There exist $p$ ($0 \le p \le C_0$) such that $0 = d_1 = ... = d_p$ and $d_{p + 1} = ... = d_{C_0} = C_1$

One operation changes $d_i$ by one, so clearly at least $K$ operations is required, where:

$$K = \sum_{i = 1}^{C_0}(\min(d_i, C_1 - d_i))$$

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    string s;
    cin >> n >> s;

    int c1 = 0;
    for (auto c : s)
    {
        c1 += c == '1';
    }

    int cur = 0;
    long long ans = 0;

    for (auto c : s)
    {
        if (c == '0')
        {
            ans += min(cur, c1 - cur);
        }
        else
        {
            cur++;
        }
    }

    cout << ans << endl;

    return 0;
}

Tips

To make all 1s contiguous, we want to move them into one block, and the optimal block is the one that minimizes total movement distance:

• Store the indices of all 1s, suppose we have $k$ ones at positions: $p_1, P_2, ..., p_k$
• The best place to group them together is centered around the median position $m$
• If we place 1s in positions $m - k/2, ..., m, ..., m + k/2$, we can compute the number of operations required

$$ans = \sum_{i = 0}^{k - 1}(|pos[i] - (pos[k/2] - k/2 + i)|)$$

#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> pos;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '1')
        {
            pos.push_back(i);
        }
    }

    int k = pos.size();
    long long ans = 0;

    for (int i = 0; i < k; i++)
    {
        ans += abs(pos[i] - (pos[k/2] - k / 2 + i));
    }

    cout << ans << endl;

    return 0;
}

📌 E - GCD of Subset

393E

Tips

One can make the GCD $x$ only if:

• $A_i$ is divisible by $x$
• $A$ has at least $K$ elements divisible by $x$

The answer is the maximum among such $x$

Let $s_n$ be the number of occurrences of $n$ in $A$

Let $t_n$ be the number of multiples of $n$ in $A$. Here, we will use the notation $d|s$ as "$d$ divides n". $t_n$ and $s_n$ have the realtion:

$$t_d = \sum_{d|n}(s_n)$$

Let $u_n$ be the answer for $A_i = n$. $u_n$ realtes $t_n$ as:

$$u_n = \max({d \, such \, that \, d|n \, and \, t_d \ge K})$$

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

    int m = *max_element(A.begin(), A.end());
    vector<int> s(m + 1), t(m + 1), u(m + 1);

    for (auto a : A)
    {
        s[a]++;
    }

    for (int d = 1; d <= m; d++)
    {
        for (int n = d; n <= m; n += d)
        {
            t[d] += s[n];
        }
    }

    for (int d = 1; d <= m; d++)
    {
        if (t[d] < K)
        {
            continue;
        }

        for (int n = d; n <= m; n += d)
        {
            u[n] = max(u[n], d);
        }
    }

    for (auto a : A)
    {
        cout << u[a] << endl;
    }

    return 0;
}

📌 F - Prefix LIS Query

393F

LIS (Longest monotonically Increasing Subsequence)

Inspect $A_i$ in the order of $i = 1, 2, ..., N$ to update the following DP table in-place:

• $dp[j]$ ($1 \le j \le N$): the smallest value of the final term of a length-$j$ subsequence that can be extracted from the elements so far, or $\infty$ if there is no such subsequence

Considering the definition of the DP above, the answer to query $k$ turns out to be equal to:

• The maximum $j$ such that $dp[j] \le X_k$ in the DP table when inspecting up to $i = R_k$
• for each step $i$, finding the answer for all queries $k$ with $i = R_k$ using binary serach

#include <bits/stdc++.h>

using namespace std;

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

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

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

    vector<vector<pair<int, int>>> qs(n);
    for (int i = 0; i < q; i++)
    {
        int r, x;
        cin >> r >> x;
        r--;

        qs[r].push_back({i, x});
    }

    vector<int> ans(q);
    vector<int> dp(n, 1e9 + 10);

    for (int i = 0; i < n; i++)
    {
        auto it = lower_bound(dp.begin(), dp.end(), A[i]);
        *it  = A[i];

        for (auto [id, x] : qs[i])
        {
            ans[id] = upper_bound(dp.begin(), dp.end(), x) - dp.begin();
        }
    }

    for (int i = 0; i < q; i++)
    {
        cout << ans[i] << endl;
    }

    return 0;
}

📌 G - Unevenness

393G

Warning

Hard Problems to Tackle Later

// TODO