🧩 AtCoder Beginner Contest 369

TayLockAugust 31, 2024About 4 min

🧩 AtCoder Beginner Contest 369

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Maximum value	DP	⭐🔥🧠
E	Shortest Path	DP & Warshall-Floyed	🧠🌀
F	longest increasing subsequence(LIS)	LIS	🌀
G	Tree DP	Tree 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 - 369

#include <bits/stdc++.h>

using namespace std;

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

    int A, B;
    cin >> A >> B;

    if (A > B)
    {
        swap(A, B);
    }

    set<int> s;

    s.insert(A - (B - A));
    if ((B - A) % 2 == 0)
    {
        s.insert(A + (B - A) / 2);
    }
    s.insert(B + (B - A));

    cout << s.size() << endl;

    return 0;
}

📌 B - Piano 3

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    int ans = 1e9;

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

    for (int l = 1; l <= 100; l++)
    {
        for (int r = 1; r <= 100; r++)
        {
            int temp = 0;
            int left = l, right = r;

            for (int i = 0; i < N; i++)
            {
                if (P[i] == 'L')
                {
                    temp += abs(A[i] - left);
                    left = A[i];
                }
                else
                {
                    temp += abs(A[i] - right);
                    right = A[i];
                }
            }

            ans = min(ans, temp);
        }
    }

    cout << ans << endl;

    return 0;
}

📌 C - Count Arithmetic Subarrays

#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];
    }

    long long ans = 0;

    for (int l = 0, r = 0; l < N; l++)
    {
        while (r + 1 < N && A[r + 1] - A[r] == A[l + 1] - A[l])
        {
            r++;
        }

        ans += r - l + 1;
    }

    cout << ans << endl;

    return 0;
}

📌 D - Bonus EXP

Tips

Let:

$dp_{even}[k]$ : the maximum total experience point when defeating an even number of monsters out of the first $k$ monsters to encountered, and $dp_{odd}[k]$ be that for an odd number of monsters, or $-\infin$ if it is impossible

Initially,

$dp_{even}[0] = 0$
$dp_{odd}[0] = -\infin$

Tips

Here, for $1 \le i \le N$ , note that the experience point that can be gained from the $i$ -th monster is solely dependent on:

whether Takahashi chose to defeat it or let it go; and
(if he decided to defeat it)whether the number of monsters defeated so far is even or odd

Also, to encounter the first $i$ monsters and defeat an even number of monsters, the following two cases are only possible:

defeat an even number of monsters among the first $(k - 1)$ , and let the $k$ -th go; or
defeat an odd number of monsters among the first $(k - 1)$ , and defeat the $k$ -th

Therefore, if we know $dp_{even}[i - 1]$ and $dp_{odd}[i - 1]$ , we can find:

\begin{cases} dp_{even}[i] &= \max(dp_{even}[i - 1], dp_{odd}[i - 1] + 2 \times A_i) \\ dp_{odd}[i] &= \max(dp_{odd}[i - 1], dp_{even}[i - 1] + \times A_i) \\ \end{cases}

The final answer is:

\max(dp_{even}[N], dp_{odd}[N])

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

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

    vector<long long> dp(2);
    dp[0] = 0ll;
    dp[1] = -1e18;

    for (int i = 0; i < N; i++)
    {
        vector<long long> nxt = dp;

        nxt[0] = max(dp[0], dp[1] + 2 * A[i]);
        nxt[1] = max(dp[1], dp[0] + A[i]);

        dp = nxt;
    }

    cout << max(dp[0], dp[1]) << endl;

    return 0;
}

📌 E - Sightseeing Tour

Tips

First of all, let $t(i, j)$ be the time required to travel from island $i$ to $j$ without any constraints

This can be computed for all pairs of islands in a total $O(N^3)$ time using Warshall-Floyed algorithm

Tips

Consider solving the $i$ -th problem, the bridges connect islands $(U_{B_{i, 1}}, V_{B_{i, 1}}), (U_{B_{i, 2}}, V_{B_{i, 2}}), ..., (U_{B_{i, K_i}}, V_{B_{i, K_i}}),$

Fix the order of using those bridges and the directions. When the bridges are decided to be used in the order and directions of $x_1 \rightarrow y_1, x_2 \rightarrow y_2, ..., x_{K_i} \rightarrow y_{K_i}$ , then the minimum time required to travel from island $i$ to island $N$ subject to the condition is:

\lbrace t(1, x_1) + t(y_1, x_2) + t(y2, x_3) + ... + t(y_{K_i - 1}, x_{K_i}) + t(y_{K_i}, N) \rbrace + \lbrace T_{B_{i, 1}} + T_{B_{i, 2}} + ... + T_{B_{i, K_i}} \rbrace

The final answer is the minimum of this value for all order and directions

Tips

if we precompute $t(i, j)$ , this can be found as the sum of $(2 K_i + 1)$ numbers
fix the order of using those bridges: $K_i!$
fix the directions: $2^{K_i}$

If we use dynamic programming once the order is fixed, the time required to solve one question becomes about: $5 K_i (K_i!)$ , which enables us to solve the problem faster

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<vector<long long>> dis(N, vector<long long>(N, 1e18));
    for (int i = 0; i < N; i++)
    {
        dis[i][i] = 0;
    }

    vector<long long> U(M), V(M), T(M);
    for (int i = 0; i < M; i++)
    {
        cin >> U[i] >> V[i] >> T[i];
        U[i]--;
        V[i]--;

        dis[U[i]][V[i]] = min(dis[U[i]][V[i]], T[i]);
        dis[V[i]][U[i]] = dis[U[i]][V[i]];
    }

    for (int k = 0; k < N; k++)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }

    int Q;
    cin >> Q;

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

        vector<int> B(K);
        for (int i = 0; i < K; i++)
        {
            cin >> B[i];
            B[i]--;
        }
        sort(B.begin(), B.end());

        long long ans = 1e18;

        do
        {
            array<long long, 2> dp = {dis[0][V[B[0]]] + T[B[0]], dis[0][U[B[0]]] + T[B[0]]};

            for (int i = 1; i < K; i++)
            {
                int a = B[i - 1];
                int b = B[i];

                dp = {min(dp[0] + dis[U[a]][V[b]], dp[1] + dis[V[a]][V[b]]) + T[b], min(dp[0] + dis[U[a]][U[b]], dp[1] + dis[V[a]][U[b]]) + T[b]};
            }

            ans = min({ans, dp[0] + dis[U[B[K - 1]]][N - 1], dp[1] + dis[V[B[K - 1]]][N - 1]});
        } while (next_permutation(B.begin(), B.end()));

        cout << ans << endl;
    }

    return 0;
}

📌 F - Gather Coins

Warning

Hard Problems to Tackle Later

// TODO

📌 G - As far as possible

Warning

Hard Problems to Tackle Later

// TODO