USACO Silver 2016 February - Load Balancing

Official Analysis (Java)

Solution 1

Similar to the analysis.

Time Complexity: $\mathcal{O}(N^2)$

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double; 
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;

Solution 2

Time Complexity: $\mathcal{O}(N^3)$

It does not suffice to check only a constant number of $x$ and $y$-coordinates that are close to the median $x$ or $y$, respectively. For example, consider the case where $N=999$ and $x_i=y_i=2i-1$. Then $M=333$.

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

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double; 
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;