Problem A: TN’s Kingdom I – Establishment

This problem is rather easy. Recall that any spanning tree of a complete graph K_n can be mapped in a bijection to a sequence of length (n - 2) over the set of vertices {v₁, v₂, …, v_n} where no leaf nodes appear. There are n^{n - 2} such sequences in total, (n - 1)^{n - 2} of which do not contain a specific node. Therefore the answer is ((n - 1) / n)^{n - 2}.

Problem B: TN’s Kingdom II – Construction

This problem requires your solution to find the Euclidean minimum spanning tree of a point set P given on the plane. One efficient algorithm is to compute the Delaunay triangulation of the point set D(P) and use only the edges in D(P) for the computation of the spanning tree. This algorithm runs in O(n lg n) time and asymptotically optimal.

Problem C: TN’s Kingdom III – Assassination

Your solution has find a sequence β whose cyclic convolution with the sequence α is γ. Fourier transform can be used to speed up the calculation. The condition that the length of the sequences perfectly factors over small primes makes the algorithm much easier to implement.

Problem D: TN’s Kingdom IV – Collapse

The task is to compute the maximum flow on a undirected s-t planar network. The max-flow min-cut theorem can be applied. Assume the network is connected. A cut of such a network is equivalent to a cycle of adjacent faces containing the unbounded face. Finding a minimum cycle (and simultaneously  a minimum cut) can be done by solving a single source shortest paths problem which requires O(n lg n) time.

Problem E: Sliding Window

A trivial solution to this task running in O(n lg n) time is to maintain a min-heap and a max-heap. But better solutions exist. You can maintain the sliding window as a double-ended queue, which will yield a linear-time algorithm by amortized analysis.

Problem F: Bohemian Rhapsody

The problem can be reduced to the computation of the area of  intersection of circles. The jury solution does the calculation by dividing the intersection into the union of a polygon and some segments.

Problem G: Perfect Permutation

If the remainder of n divided by 4 is 2 or 3, then no such permutations exist, otherwise a permutation can be found by construction.

Problem H: An Easy Problem?!

Simple geometry will solve the problem as long as all special cases are handled.