I solved it using this technique.

There will be some point such that you will not make moves crossing this point in your optimal solution. Therefore you can try all cyclic shifts, solve each of them as problem on array (where first and last elements aren't adjacent) and pick best result.

How to solve problem for array: result is equal to sum abs(pref_sum_A[i]-pref_sum_B[i]) over all i. Idea is following: it makes no sense to move some element in opposite directions (you can cancel such pair of moves), therefore if you have X elements in prefix of first array and Y elements in prefix of second array, there will be abs(X-Y) moves through the cut after this prefix — because you have to make X=Y, and you'll be either moving items from suffix into prefix or from prefix into suffix — but not both.

I tried to find pairs of piles such that one has a surplus and the other has a deficit of stones. I used a greedy approach (taking the adjacent piles first, then piles with distance 2 and so on ... ). Is this O(n^2) approach wrong?

Let X be the number of stones that passes through the border between 0 and 1 in 0->1 direction (if X is negative, it means that -X stones passes through the border in the opposite direction).

Then, X+a[1]-b[1] stones must pass through the border between 1 and 2 in 1->2 direction, X+a[1]-b[1]+a[2]-b[2] stones between 2->3, ... and so on.

Therefore the problem reduces to the following: find X that minimizes the sum |X| + |X+a[1]-b[1]| + |X+a[1]-b[1]+a[2]-b[2]| + ...

This is equivalent to a well-known problem where you are given points on a line and you need to find a point that minimizes the sum of distances to the given points. The solution is the median.

http://ideone.com/LmPqxj — one but not so obvious DFS. In my code a variable ways denotes the number of subtrees with this vertex as the topmost vertex. And variable pref is the sum of sizes, needed for the answer. I process children one by one, always merging two first children into a new one. Merging two children a, b is as follows:

ways = ways[a] * ways[b]
pref = ways[a] * pref[b] + ways[b] * pref[a]

Is it easy to see that p is a polynomial?

One not so simple solution for Div1-Hard: If you rotate by 45deg ((x,y) -> (s,t)=(x+y,x-y)) then the s-coord and t-coord move independently.

Where A_i, j is some constant with binomials and stuff. Because s,t move independently E(sⁱt^j) = E(sⁱ)E(t^j). Let r = ds₁ + ... + ds_t, each ds_i being +-1 uniformly randomly, then

If you expand rⁱ you'll notice that any term with an odd power for any ds will have expected value 0, otherwise it'll be 1, so we just need to count those. You can do that with a dp in O(n^2), state being i and how many of the ds currently have odd power. Overall the algo can be implemented in O(n^2).

Edit: Rip, i've reused the name t, I hope it's clear from the context which is which.

For every prime p count v_p(a₀), v_p(a₁), ..., v_p(a_n), where v_p(x) is the largest k such that p^k divides x. Sort these arrays. Then for the first number take the product of the largest v_p(a_i) for all p, for the second — the product of the second largest v_p(a_i) for all p and so on. It's obvious that this answer is optimal and reachable from the initial array.

For each prime numbers its occurrences (after factorizing numbers) will be sorted by the exponent degree. Let's say that the input sequence is 2⁵·3⁸·5¹, 2⁷·5¹⁰, 2³·3⁴·5⁴. Then, prime number 2 has its occurrences sorted as 2⁷, 2⁵, 2³ and similarly for primes 3, 5. The final sequence should be 2⁷·3⁸·5¹⁰, 2⁵·3⁴·5⁴, 2³·5¹.

That was the intended solution. But I was retarted as a tester and I came up with much harder solution only. I simulate the process, carefully choosing the order of operations. I can explain if anybody wants it. Code — http://ideone.com/BCOUcE

The only finite edges are incident to either source or sink so there will be only n iterations of dijkstra. So it's O(n²log(n)), you can't break it.

O(N^2) Greedy.

A solution only exists if the sum of both arrays are equal, if not output -1.

Start with an empty set {}.

Go from 1 to N, and at each step, solve for element number i. Maintain an invariant that all elements to your left have their target values ( all of them) so it makes no sense to change them, only look to the right.

Let curr[] denote initial configuration, and goal[] denote the desired configuration.

if curr[i] > initial[i]..You've excess, and since all elements to your left are with correct values, the excess must go to the right, you don't know where, but anyways, it has to move, so moving it to i + 1 does not make your answer worse.

if initial[i] > curr[i]..Keep moving to the right, and adding elements till initial[i] = curr[i]. ( This is not the two pointers method, after you fix i, you will start again from i + 1).

At step N, initial[N] must be equal curr[N] as you already fixed all values, and sums are equal.

Clearly if initial[i] = curr[i] do nothing.

Make sure to use long long when summing arrays.

Note: The above strategy does not work for Div1 250.

Looks updated now