USACO 2024 January Contest, Bronze
Problem 1. Majority Opinion
http://www.usaco.org/index.php?page=viewproblem2&cpid=1371
** Dr. Chen’s C++ analysis & solution:**
Problem 2. Cannonball
http://www.usaco.org/index.php?page=viewproblem2&cpid=1372
** Dr. Chen’s C++ analysis & solution:**
Problem 3. Balancing Bacteria
http://www.usaco.org/index.php?page=viewproblem2&cpid=1373
** Dr. Chen’s C++ analysis & solution:**
On Problem 3 - Balancing Bacteria, the following nested loop solution is the most intuitive solution:
/*
Author: Dr. Owen Chen
Datetime: 2024-01-28
USACO 2024 January Contest, Bronze
Problem 3. Balancing Bacteria
Version 1 - Nested Loop
Complexity: O(N^2)
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int N;
cin >> N;
vector<ll> bacteria(N);
for (int i = 0; i < N; i++) {
cin >> bacteria[i];
}
ll res = 0;
for (int i = 0; i < N; i++) {
if (bacteria[i] != 0) {
res += abs(bacteria[i]);
for (int j = i+1; j < N; j++) {
bacteria[j] -= bacteria[i] * ( j - i + 1);
}
}
}
cout << res << endl;
return 0;
}
Unfortunately, the above O(N^2) solution will time out on test cases 11-15 when N is very large.
To solve all test cases, see the two-cumulative-sum solution above.