USACO 2024 February Contest Bronze Division - Milk Exchange

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

In order to solve this problem, we have to know that we are given a graph with \(n\) nodes and \(n\) edges (some kind of a functional graph if you know silver concepts) and we know that some vertexes will be net givers and these net givers will have to slowly give away their milk to the net receivers.

Therefore, we will start finding cycles from the net givers and basically until we find the cycle, we sum up the quantities of milk of the net givers and check if we need more than \(m\) seconds to empty them.

In the end, we will find these sums independently for each cycle using the cycle detection algorithm you can read more about when reading about functional graphs.

Source codes

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

#include <iostream>
#include <vector>
using namespace std;

int n, v[200002], cnt[200002], vis[200002], nxt[200002];
long long m;
string s;

long long sum = 0;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    cin >> s;
    s = ' ' + s; // 1-index string

    for(int i = 1; i <= n; i++)
    {
        cin >> v[i];
        sum += v[i];
    }

    for(int i = 1; i <= n; i++)
    {
        if(s[i] == 'L')
        {
            if(i == 1)
                cnt[n]++, nxt[i] = n;
            else
                cnt[i-1]++, nxt[i] = i-1;
        }
        else
        {
            if(i == n)
                cnt[1]++, nxt[i] = 1;
            else
                cnt[i+1]++, nxt[i] = i+1;
        }
    }

    for(int i = 1; i <= n; i++)
    {
        if(vis[i] == 0 && cnt[i] == 0)
        {
            vector<int> cycle;
            int pos = i;
            while(vis[pos] == 0)
            {
                vis[pos] = 1;
                cycle.push_back(pos);
                pos = nxt[pos];
            }
            long long noncyclesum = 0;
            for(int j = 0; j < cycle.size() && cycle[j] != pos; j++)
                noncyclesum += v[cycle[j]];
            sum -= min(m, noncyclesum);
        }
    }

    cout << sum << '\n';
    return 0;
}

n, m = map(int, input().split())
s = input().strip()
s = " " + s

v_values = list(map(int, input().split()))
v = [0] + v_values
total_sum = sum(v_values)

cnt = [0] * (n + 1)
vis = [0] * (n + 1)
nxt = [0] * (n + 1)

for i in range(1, n + 1):
    if s[i] == 'L':
        if i == 1:
            cnt[n] += 1
            nxt[i] = n
        else:
            cnt[i - 1] += 1
            nxt[i] = i - 1
    else: 
        if i == n:
            cnt[1] += 1
            nxt[i] = 1
        else:
            cnt[i + 1] += 1
            nxt[i] = i + 1

for i in range(1, n + 1):
    if vis[i] == 0 and cnt[i] == 0:
        cycle = [] 
        pos = i
        while vis[pos] == 0:
            vis[pos] = 1
            cycle.append(pos)
            pos = nxt[pos]

        non_cycle_sum = 0
        for position in cycle:
            if position == pos:
                break  
            non_cycle_sum += v[position]

        total_sum -= min(m, non_cycle_sum)

print(total_sum)