USACO Silver 2016 February - Load Balancing
Author: Benjamin Qi
Solution 1
Similar to the analysis.
Time Complexity:
1#include <bits/stdc++.h>2using namespace std;34using ll = long long;5using ld = long double;6using db = double;7using str = string; // yay python!89using 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;34using ll = long long;5using ld = long double;6using db = double;7using str = string; // yay python!89using 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!