USACO Silver 2016 February - Load Balancing

Author: Benjamin Qi

Official Analysis (Java)

Solution 1

Similar to the analysis.

Time Complexity:

1#include <bits/stdc++.h>
2using namespace std;
3
4using ll = long long;
5using ld = long double;
6using db = double;
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;

Solution 2

Time Complexity:

It does not suffice to check only a constant number of and -coordinates that are close to the median or , respectively. For example, consider the case where and . Then .

However, we can speed up an solution by a constant factor by checking fewer and coordinates than the bronze editorial does. Note that if we increase the -coordinate of the north-south fence by two and there are still at most cows to the left of the fence, then the answer for this new configuration cannot be worse. Thus, the number of -coordinates which the solution below checks is at most (plus a constant). Similar reasoning holds for the -coordinates.

1#include <bits/stdc++.h>
2using namespace std;
3
4using ll = long long;
5using ld = long double;
6using db = double;
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Give Us Feedback on USACO Silver 2016 February - Load Balancing!