Let Operation 1 and 2 be the following operations.

1. Reverse the entire permutation: \(p_1,p_2,\dots,p_n\) becomes \(p_n,p_{n-1},\dots,p_1\).
2. Move the term at the beginning to the end: \(p_1, p_2, \dots,p_n\) becomes \(p_2,\dots, p_n, p_1\).

Solution A

There are only \(2n\) permutations that the operations above can sort into \(1,2,\dots,n\), as follows (when \(n=2\), there are just two of them because of duplication).

• The ones that can be sorted in ascending order by Operation 1
  • \(1,2,3,\dots,n\)
  • \(2,3,\dots,n,1\)
  • \(3,\dots,n,1,2\)
  • \(\vdots\)
  • \(n,1,2,3,\dots,n-1\)
• The ones that can be sorted in descending order by Operation 2
  • \(n,n-1,n-2,\dots,1\)
  • \(n-1,n-2,\dots,1,n\)
  • \(n-2,\dots,1,n,n-1\)
  • \(\vdots\)
  • \(1,n,n-1,n-2,\dots,2\)

Thus, there are only \(O(n)\) possible states on the way, so we can solve it basically by brute force. However, each operation would take \(O(n)\) time in naive implementation using the given array of length \(n\) as is, so we need to improve the way to maintain the states. One better way to represent a state is to represent it as the pair of the following information.

• The position of \(1\)
• Whether it can be sorted in ascending order by Operation 2 only

Sample Implementation in C++

Solution B

Doing Operation 2 → Operation 1 → Operation 2 leads to the same result as doing Operation 1 only. Thus, we do not need to consider doing Operation 2 → Operation 1 → Operation 2.

Similarly, doing Operation 1 → Operation 1 leads to the same result as doing nothing, so we do not need to consider it.

From above, we can see that Operation 1 only needs to be done at the beginning or end. Therefore, we can try four cases: whether we do Operation 1 at the beginning and whether we do it at the end, and adopt the one with the fewest operations among the ones that worked.