Solution Notes (Bruce Merry): Firstly, note that all we need to decide is how many bales move between each adjacent pair of piles, and in which direction. There is no point moving hay in both directions between two piles, because it just cancels out. Once we've decided the "flow" of the hay, it will always be possible to schedule the actual moving of hay.

If the piles were in a line instead of a circle, there would be a unique correct flow: from the first pile you can tell how much has to move to/from the second pile, and after that you can tell how much to move between the second and third piles, and so on. With a circle you get one free choice: the amount to move between the first and last piles. Changing this parameter has the effect of adding or subtracting a constant each inter-pile flow. Thus, if the flows between piles for one choice are (signed) integers f1, f2, f3, ..., fn, then we want to pick an integer m to minimize |f1-m| + |f2-m| + ... + |fn-m|.

This is the sum of convex functions, so it will itself be convex and the minimum could be found by a unimodal search (e.g. ternary search). However, the solution can be found more directly: if more than half the f's are greater than m then m should be increased, and if less than half the f's are greater than m then m should be decreased (this can easily be seen by computing the effect of increasing or decreasing m by 1). It follows that m should be chosen as the median of the f's.

Note from Brian: in the computing literature, this problem is sometimes called computing "circular earthmover distance".

``````
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstdlib>

using namespace std;

int main()
{
ifstream in("restack.in");
ofstream out("restack.out");

int N;
in >> N;
vector<int> A(N + 1), B(N + 1);
for (int i = 0; i < N; i++)
{
in >> A[i] >> B[i];
}
A[N] = A[0];
B[N] = B[0];
vector<int> S(N);
S[0] = A[0] - B[0];
for (int i = 1; i < N; i++)
S[i] = A[i] + S[i - 1] - B[i];
nth_element(S.begin(), S.begin() + N / 2, S.end());
int m = S[N / 2];
long long ans = 0;
for (int i = 0; i < N; i++)
ans += abs(S[i] - m);
out << ans << endl;
return 0;
}
``````