Subtask 1

This subtask was created to reward solutions which compute the best permutation using dynamic programming on bitmasks. One common strategy was to precompute a lookup table for large or all values of ~N~ to ensure that the solution fits in the time limit.

Time Complexity: ~\mathcal{O}(N^2 2^N)~

Subtask 2

This subtask was intended to reward slower implementations of the heuristic presented below.

Subtask 3

The key realization for this problem is that it is closely related to the travelling salesman problem which is NP-hard, so any currently known solution for these larger values of ~N~ would probably rely on heuristics. One such heuristic that works particularly well with this problem is simulated annealing. An important thing to recognize is that the neighbour function can be optimized from simply picking two random elements and swapping their positions in the permutation, which could change up to four adjacent distances. Instead, we may choose to reverse a random subarray of the permutation for a much stronger neighbour function. This is because it only changes up to two adjacent distances, and it is still possible to reach any permutation through a linear number of reversals. Another possible optimization is to only recalculate the two adjacent distances that have changed instead of recalculating the entire primeness from scratch, which allows us to run many more iterations of annealing.

Bonus: Simulated annealing is not the strongest heuristic applicable to this problem, by far. If you believe you have a more efficient method than presented above, you are welcome to submit it to the hard version of this problem.