🧩 AtCoder Beginner Contest 373

TayLockSeptember 28, 2024About 4 min

🧩 AtCoder Beginner Contest 373

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Graph	BFS / DFS	⭐🔥
E	Binary Search	Binary Search	🧠
F	Knapsack	DP	🌀
G	Math	Hungarian algorithm/minimum cost flow algorithms	🌀

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

#include <bits/stdc++.h>

using namespace std;

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

    int ans = 0;
    for (int i = 0; i < 12; i++)
    {
        string s;
        cin >> s;

        ans += (i + 1) == s.size();
    }

    cout << ans << endl;

    return 0;
}

📌 B - 1D Keyboard

#include <bits/stdc++.h>

using namespace std;

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

    string S;
    cin >> S;

    map<char, int> mp;
    for (int i = 0; i < 26; i++)
    {
        mp[S[i]] = i;
    }

    int ans = 0;
    for (int i = 1; i < 26; i++)
    {
        ans += abs(mp['A' + i] - mp['A' + i - 1]);
    }

    cout << ans << endl;

    return 0;
}

📌 C - Max Ai+Bj

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

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    cout << A[N - 1] + B[N - 1] << endl;

    return 0;
}

📌 D - Hidden Weights

#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<pair<int, int>>> adj(N);
    for (int i = 0; i < M; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;

        adj[u].push_back({v, w});
        adj[v].push_back({u, -w});
    }

    vector<long long> dis(N);
    vector<bool> vis(N);

    auto dfs = [&](auto &&self, int u) -> void
    {
        vis[u] = true;
        for (auto [v, w] : adj[u])
        {
            if (!vis[v])
            {
                dis[v] = dis[u] + w;
                self(self, v);
            }
        }
    };

    for (int i = 0; i < N; i++)
    {
        if (!vis[i])
        {
            dfs(dfs, i);
        }
    }

    for (int i = 0; i < N; i++)
    {
        cout << dis[i] << " \n"[i == N - 1];
    }

    return 0;
}

📌 E - How to Win the Election

Tips

If one can solve the following decision problem, then the answer to this problem can be found with binary search:

if candidate $i$ ends up obtaining a total of $X$ votes, is it possible that each of the $M$ candidates with most votes, except for candidate $i$ , has more than $X$ votes?

If it is possible, then candidate $i$ cannot secure their victory when they end up having $X$ votes, as the result may not allow them to be elected. Conversely, if it is impossible, then candidate can always win if they obtain a total of $X$ votes

Tips

We want to find at least how many additional votes are required for each of the $M$ candidates with most votes, except for candidate $i$ , to have at least $(X + 1)$ votes. For this count $C$ , the decision problem is answered No if $C > K - \sum_{i = 0}^{N}A_i$ ; and Yes otherwise

We can assume that these $M$ candidates are the $M$ candidates with most votes counted so far, except for candidate $i$ , to find the minimum value:

If $1 \le i \le N - M$ , then candidates $N - M + 1, ..., N$ comprise the set
When $N - M + 1 \le i \le N$ , candidates $N - M, N - M + 1, ..., i - 1, i + 1, ..., N$ do

Among these candidates, those with $(X + 1)$ or more votes do not need additional votes, but those with $j(\le X)$ votes need $X + 1 - j$ more votes

Tips

We can use the properties that the top $M$ candidates have mostly consecutive indices, and that whether they have $(X + 1)$ or more votes or not is monotonic with respect to $j$ , which help us to utilize cumulative sums and binary search, enabling to find the value required to solve the decision problem

do a binary search to find the maximum index of a candidate with $X$ or less votes, find the number of candidates with that index or less, among those in the set we have defined above. The sought sum is (the number of candidates) $ \times (X + 1)$, subtracted by the number of votes that those in the set have obtained so far
Finally, add the number of additional votes required for candidate $i$ to end up having $X$ or more votes to the sum, and the result is the minimum additional vote count required

#include <bits/stdc++.h>

using namespace std;

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

    int N, M;
    long long K;
    cin >> N >> M >> K;

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

        sum += A[i];
    }

    if (N == M)
    {
        for (int i = 0; i < N; i++)
        {
            cout << 0 << " \n"[i == N - 1];
        }
        return 0;
    }

    vector<long long> v = A;
    sort(v.begin(), v.end());

    vector<long long> pre(N + 1);
    for (int i = 0; i < N; i++)
    {
        pre[i + 1] = pre[i] + v[i];
    }

    for (int i = 0; i < N; i++)
    {
        long long lo = 0, hi = K - sum + 1;

        while (lo < hi)
        {
            long long mid = (lo + hi) / 2;

            // the total votes candidate i would have if they get mid extra votes
            long long a = A[i] + mid;

            // how many candidates (including i) have ≤ a votes
            int j = upper_bound(v.begin(), v.end(), a) - v.begin();
            // If there are ≥ M candidates with > a votes, i may lose
            if (N - j >= M)
            {
                // try larger mid
                lo = mid + 1;
                continue;
            }

            // This simulates the minimum number of extra votes other candidates need to surpass i
            long long res = (j - (N - M)) * (a + 1) - (pre[j] - pre[N - M]);

            // If i is already in the top M, we account for the possible shift in ranking
            if (A[i] >= v[N - M])
            {
                res += A[i] - v[N - M - 1];
            }

            // Check if it's feasible for other candidates to overtake i after i takes mid votes
            if (res <= K - sum - mid)
            {
                lo = mid + 1;
            }
            else
            {
                hi = mid;
            }
        }

        cout << (lo > K - sum ? -1 : lo) << " \n"[i == N - 1];
    }

    return 0;
}

📌 F - Knapsack with Diminishing Values

Warning

Hard Problems to Tackle Later

// TODO

📌 G - No Cross Matching

Warning

Hard Problems to Tackle Later

// TODO