Array Rotation
Time limit10sMemory limit128 MB
Given a target permutation of ±1..N reachable by repeated reverse-and-negate interval operations starting from the sorted array, output a sequence of such operations that produces it.
- Level
Medium6 of 10
- Topics
- Simulation, Greedy, Array
- Solved
- No attempts yet
Problem
An array initially contains the natural numbers from 1 to N in order. The following array shows the case N=6.
You may choose any interval (a, b) and rotate it once. A rotation reverses the order of the numbers from position a through position b, and also changes the sign of every number in that interval. (1 ≤ a ≤ b ≤ N) If the interval (1, 4) is rotated in the array above, the result is as follows.
The same operation can be applied repeatedly to an array that has already been rotated. If interval (3, 5) is then rotated, the final array becomes:
The initial array is always the ordered array 1 through N. Given a final array state, write a program that constructs that final array from the initial array using a small number of rotation operations.
Input
The first line contains the array size N (1 ≤ N ≤ 250). The second line contains the final array state in order, separated by spaces. For each value from 1 through N, exactly one number with that absolute value appears in the sequence.
Output
On the first line, print K, the number of rotation operations used. Then print K lines in the order the operations are performed. Each line contains two integers a and b, the interval (a, b) to rotate. (1 ≤ a ≤ b ≤ N)