TLE '16 Contest 6 (Mock CCC) S4 - Bubble Sort


Submit solution


Points:17 (partial)
Time limit:2.0s
Memory limit:256M

Problem type

Can you sort the bubbles by increasing bubble radius using bubble sort?

Since the Canadian Computing Competition (CCC) often requires the use of a sorting algorithm, Darcy needs to practice sorting! Darcy's favourite sorting algorithm is bubble sort.

To practice his ability to bubble sort, he gathers up an array A which contains N integers. He accesses this array by calling A[0] as the first element, and A[N-1] as the last element. Every element in this array is an integer in the range 0 \dots N-1, and there are no duplicate elements.

Darcy swaps adjacent elements to sort this array, but if A[x]=x, he does not want to swap the integer x ever again. Specifically, Darcy is allowed to swap the elements A[i] and A[i+1] if these following conditions hold:

  • The first index is valid (0 \le i \le N-1)
  • The second index is valid (0 \le i+1 \le N-1)
  • Darcy can swap the element at the first index (A[i] \ne i)
  • Darcy can swap the element at the second index (A[i+1] \ne i+1)

Eventually, Darcy gets confused and asks for help. Is there a sequence of swaps that will sort A? In the case that no sequence exists, output Give up.

Input Specification

The first line contains the integer N (1 \le N \le 1500).

The second line contains N space-separated integers, which are the elements of A. These integers are between 0 and N-1, inclusive. Every element in the array is distinct.

  • For 3 of the 15 available marks, the elements of A are in descending order.
  • For an additional 2 of the 15 available marks, all multiples of 6 are put in the correct index. Specifically, A[6x] = 6x.
  • For an additional 2 of the 15 available marks, 1 \le N \le 6.
  • For an additional 4 of the 15 available marks, 1 \le N \le 100.

Output Specification

If it is impossible to sort the array A, output Give up.

Otherwise, output the number of swaps needed to sort the array. Let this number be called S. Your integer S must not exceed 2 million (= 2 \times 10^5 \times 10). You do not have to print the lowest possible S.

On the next S lines of output, print two indices i and j. This indicates that A[i] and A[j] will be swapped in this step.

Sample Input 1

2
0 1

Sample Output 1

0

Explanation for Sample Output 1

The array is already sorted, so no swaps are necessary.

Sample Input 2

5
4 3 2 1 0

Sample Output 2

Give up

Explanation for Sample Output 2

Darcy does not want to swap the integer 2 because A[2] = 2. As a result, the remaining integers cannot be swapped to their proper indices. This array is impossible to sort.

Sample Input 3

6
2 5 1 4 0 3

Sample Output 3

13
3 2
3 2
3 2
4 3
1 2
2 3
3 4
4 5
1 2
2 3
3 4
0 1
1 2

Explanation for Sample Output 3

The table shows array A as the 13 instructions are performed. Notice that the bubble sort algorithm can be used after the 4^{th} swap.

Instruction number Indices Array A
0 - \{2, 5, 1, 4, 0, 3\}
1 3, 2 \{2, 5, 4, 1, 0, 3\}
2 3, 2 \{2, 5, 1, 4, 0, 3\}
3 3, 2 \{2, 5, 4, 1, 0, 3\}
4 4, 3 \{2, 5, 4, 0, 1, 3\}
5 1, 2 \{2, 4, 5, 0, 1, 3\}
6 2, 3 \{2, 4, 0, 5, 1, 3\}
7 3, 4 \{2, 4, 0, 1, 5, 3\}
8 4, 5 \{2, 4, 0, 1, 3, 5\}
9 1, 2 \{2, 0, 4, 1, 3, 5\}
10 2, 3 \{2, 0, 1, 4, 3, 5\}
11 3, 4 \{2, 0, 1, 3, 4, 5\}
12 0, 1 \{0, 2, 1, 3, 4, 5\}
13 1, 2 \{0, 1, 2, 3, 4, 5\}

Comments

There are no comments at the moment.