Div2-Easy: http://ideone.com/uzGzxa

Div2-Medium: http://ideone.com/EXVZ7f

Div2-Hard: http://ideone.com/04H4H8 (This solution can solve n <= 50 instead of 3)

Div1-Easy: http://ideone.com/HMjObD

Suppose the heights are sorted: h[0] <= h[1] <= h[2] ...

In one hand, we know the answer can't be smaller than max{x[i+2] — x[i]}. We can proof this in the following way: If abs(x[i]-x[j]) >= ans, we add an edge between i and j. We assume there is an i and ans < x[i+2]-x[i]. Then if the graph is connected, edges (i, i+1) and (i+1, i+2) will be bridege (since if x < i and y > i+2 then there is no edge between x and y.) It means this graph don't have a hamiltonian cycle, so we can't arrange these foxes around a round table.

In another hand, we know that we have a solution that ans = max{x[i+2]-x[i]}: x[0]-x[2]-x[4]-x[6]-...-n-...x[5]-x[3]-x[1]-x[0].

So we know this solution is optimal.

Div1-Medium: http://ideone.com/pQhKaG

We can compute S in the following way: For each edge, let s1 be the number of nodes in one side, we know there are s1*(n-s1) paths use this edge. So S = sum{s1 * (n-s1)}.

So we can solve it by dp: let dp[i][j] = minimal number of S such that we have a tree with i nodes and sum{s1 * (n-s1) among all edges it have} % m = j. Each time we pick 2 rooted trees, merge them: root1 becomes a son of root2. We can compute the new sum{s1 * (n-s1)} in O(1). So our algorithm can run in O(n^2 m^2).

Div1-Hard: http://ideone.com/b4v3nY (rng_58's code)

The given input is a mapping from {0,..,n-1} to itself, it is x=>(0*x), we call it f. Suppose 0*0 = 3, then what can we get? We know that 3*x = (0*0)*x = 0*(0*x) = f(f(x)) = f^2 x. So it means x=>(3*x) is f^2. And if we know 0*3 = 5, then we should get x=>(5*x) is f^3..

We construct this graph: for each i, we add directed edge from i to firstRow[i]. Then there must be some connected component, each one is a cycle with some tree towards the cycle. Suppose we have path: 0->1->2->3->4->2. (it means the component of 0 have a cycle length = 3, and the distance from 0 to cycle is 2). Then we have: f^6 = f^3. Then we know in the following cases there is no solution.

1. There is a cycle, its length is not a divisor of 3: For example, if there is a cycle 5->6->5. Then f^6 (5) = 5, but f^3 (5) = 6, they are not equal.
2. There is a node, the distance to cycle is larger than 2 + 1 = 3:

For example, if there is a path: 7->8->9->10->11->11, then we have: f^6 (7) = 11 (something on the cycle), but f^3 (7) = 10 (something not on the cycle). Beside these 2 cases, the solution always exist:

1. Let e[0] = 1, if there is an edge(i->j), then we set e[i] = e[j] — 1. By this we can get e[i] for all nodes in 0's component. We set i*j = f^(e[i]) (j).
2. For all element in other component, we set: i*j = i.

We could verify it is a valid solution.