Casino Crisis

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 0.5s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

The family of Darkness is once again in financial trouble! To clear off her debt, Darkness decided to go to the country of Elroad with Kazuma to earn some easy cash. However, after a certain someone almost caused the bankruptcy of Elroad, all the luck based games have been replaced with skill based games! Here's the nearest one they found which offers quite a fortune:

The dealer will give you an array A of size N containing a permutation of the numbers from 1 to N. He allows you to perform the following operation on it:

Select a subarray from index L to R (1 \le L \le R \le N). Consider an array B, containing the elements A_L, A_{L + 1}, ..., A_R sorted in increasing order. For all i from 1 to \lfloor{\frac{R - L + 1}{2}} \rfloor, swap the position of elements B_i and B_{R - L - i + 2} in A. In other words, swap the smallest element of the subarray with the largest element of the subarray, the second smallest element of the subarray with the second largest element of the subarray, and so on, until you reach the median of the subarray.

You win the game if you manage to sort A in increasing order using no more than Q operations.

Please help Darkness write a program to beat the game for her!

Input Specification

The first line will contain 2 integers N and Q, the size of the given array A and the number of operations allowed.

The next line will contain N integers A_1, A_2, ..., A_N, representing the array A.

Output Specification

On the first line output one integer M, the number of operations used. This number should not exceed Q.

Then output M lines each containing two integers L_j and R_j, representing the subarray on which the jth operation is performed.

Note: You do not need to find the shortest sequence of operations to sort the array. If there are multiple valid solutions, output any of them. Also, it can be proven that it is always possible to sort the array using no more than 2N operations.

Constraints

For all subtasks,

1 \le N \le 2000

1 \le A_i \le N

0 \le M \le Q

1 \le L_j \le R_j \le N

All A_i are pairwise distinct.

Subtask 1 [20%]

Q = 2 \times N^2

1 \le N \le 300

Subtask 2 [30%]

Q = 16N

Subtask 3 [50%]

Q = 2N

Sample Input

7 98
7 5 4 6 2 3 1

Sample Output

4
2 4
2 3
1 7
5 6

Explanation

First you perform the operation on the subarray A_2, A_3, A_4. This swaps the 4 and the 6, changing the array to [7, 5, 6, 4, 2, 3, 1].

Then you perform the operation on the subarray A_2, A_3. This swaps the 5 and the 6, changing the array to [7, 6, 5, 4, 2, 3, 1].

Then you perform the operation on the entire array. This swaps the following pairs: (1, 7), (2, 6), (3, 5). The array is now [1, 2, 3, 4, 6, 5, 7].

Finally you perform the operation on the subarray A_5, A_6. This swaps the 6 and the 5, changing the array to [1, 2, 3, 4, 5, 6, 7].

Since the final array is sorted in increasing order using no more than Q operations, Darkness wins and is once again debt free!

Note that the sample output is not the only possible output which will receive AC for this case.


Comments

There are no comments at the moment.