USACO 2024 January Contest Bronze Division - Balancing Bacteria

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Let's start from a simple traversal where we take from left to right and greedily modify depending on what we need to do at that actual step, hoping that it will propagate in a way or another.

It turns out that it's actually optimal to start from left to right and keep track of the current difference of the queries we've made so far, by knowing how many operations we've done of either type and either strength.

Take note that as we go towards the right, we need to increase the delta too to take in account the increased propagation effect FJ's move has.

Source codes

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

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<long long> v(n+1);
    for(int i = 1; i <= n; i++)
        cin >> v[i];

    long long cntpos = 0, cntneg = 0;
    long long delta = 0;

    for(int i = 1; i <= n; i++)
    {
        delta += cntpos;
        delta -= cntneg;
        long long trueval = v[i] + delta;
        if(trueval < 0)
            cntpos -= trueval, delta -= trueval;
        else
            cntneg += trueval, delta -= trueval;
    }

    cout << cntpos + cntneg << '\n';
    return 0;
}

n = int(input())
fr = [0] * (n + 1)
v = [0] * (n + 1)

arr = list(map(int, input().split()))
for i in range(1, n + 1):
    v[i] = arr[i - 1]

cntpos = 0
cntneg = 0
delta = 0

for i in range(1, n + 1):
    delta = delta + cntpos - cntneg
    trueval = v[i] + delta
    if trueval < 0:
        cntpos = cntpos - trueval
    else:
        cntneg = cntneg + trueval
    delta = delta - trueval

print(cntpos + cntneg)