USACO · 1373

Balancing Bacteria

This C++ solution uses simulation for USACO 1373 Balancing Bacteria. Read the reasoning, inspect the code, or try your own test case below.

1373Arrays & prefix sumsSimulationC++21 lines
Solution024of 248
Open official problem ↗ Download C++ file ↓ Search the library → Open full Code Lab ↗ Report an issue ↗

Approach

Simulation

Balancing Bacteria asks for the minimum range-prefix adjustments to zero the array; the code uses the equivalent first/second-difference accumulation.

Arrays & prefix sums

Problem and code

Useful links.

Written by benbenyaojifen. Try the problem first, then compare your approach with the code.

Open official problem ↗View exact source file ↗
Implementation

balancing_bacteria.cpp

C++

    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    int n;
    signed main(){
        ios::sync_with_stdio(0); cin.tie(0);
        cin >> n;
        vector<int> v(n);
        for(int i = 0; i < n; i++) cin >> v[i];
        vector<int> diff(n);
        diff[0] = v[0];
        for(int i = 1; i < v.size(); i++){
            diff[i] = v[i] - v[i - 1];
        }
        int ans = abs(diff[0]);
        for(int i = 1; i < diff.size(); i++){
            ans += abs(diff[i] - diff[i - 1]);
        }
        cout << ans << '\n';
        return 0;
    }
        

Did this explanation save you time? I'm a Grade 11 student building this free library to make difficult algorithms easier to understand.

Buy me a coffee ↗Keep studying →

Test this problem

Run your code here.

Paste your code, run a test case, compare the output, or trace selected values.

Full trace, comparison & stress testing ↗
StatusReady
Output
No run yet.
Diagnostics
No diagnostics yet.

Each run is isolated and has strict limits. Passing one test does not guarantee the judge will accept the solution.