USACO 2023 January Contest Bronze Division - Leaders

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

There are many methods of solving this problem, but my solution relies on using prefix sums to count how many guernseys and holsteins occured up to a certain point using prefix sums, and then I have a traversal where I count the number of potential leaders according to the statement rules.

Later, we have a simple casework depending on whether the current position is a potential leader or not.

There are more simple solutions as well which rely on the fact that only a few cows actually matter as far as checking potential leaders goes.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;

    string s;
    cin >> s;

    vector<int> g(n+1), h(n+1), ex(n+1);
    for(int i = 1; i <= n; i++)
    {
        cin >> ex[i];
        g[i] = g[i-1], h[i] = h[i-1];
        if(s[i-1] == 'G')
            g[i]++;
        else
            h[i]++;
    }

    long long ans = 0;

    vector<int> leaders(n+1);
    for(int i = 1; i <= n; i++)
    {
        leaders[i] = leaders[i-1];

        if(s[i-1] == 'G' && g[ex[i]] - g[i-1] == g[n])
            leaders[i]++;
        if(s[i-1] == 'H' && h[ex[i]] - h[i-1] == h[n])
            leaders[i]++;
    }

    for(int i = 1; i <= n; i++)
        if(leaders[i] > leaders[i-1])
            ans += 1LL * (leaders[n] - leaders[i]);
        else
            ans += 1LL * (leaders[ex[i]] - leaders[i]);
    cout << ans << '\n';
    return 0;
}

n = int(input())
s = input().strip()
g = [0] * (n + 1)
h = [0] * (n + 1)
ex = [0] * (n + 1)
v = list(map(int, input().split()))
for i in range(1, n + 1):
    ex[i] = v[i - 1]
    g[i] = g[i - 1]
    h[i] = h[i - 1]
    if s[i - 1] == 'G':
        g[i] += 1
    else:
        h[i] += 1
ans = 0
leaders = [0] * (n + 1)
for i in range(1, n + 1):
    leaders[i] = leaders[i - 1]
    if s[i - 1] == 'G' and g[ex[i]] - g[i - 1] == g[n]:
        leaders[i] += 1
    if s[i - 1] == 'H' and h[ex[i]] - h[i - 1] == h[n]:
        leaders[i] += 1
for i in range(1, n + 1):
    if leaders[i] > leaders[i - 1]:
        ans += leaders[n] - leaders[i]
    else:
        ans += leaders[ex[i]] - leaders[i]
print(ans)