CCO '18 P6 - Flop Sorting

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 2.0s
Java 3.0s
Memory limit: 512M
Java 512M

Problem type

Canadian Computing Olympiad: 2018 Day 2, Problem 3

Desperate to contribute to the CCO, Robert tried inventing a segment tree problem. The specification for that problem is:

You are given a list of N distinct integers between 1 and N. These are arranged in a row such that the i-th integer from the left is a_i , where 1 \leq i \leq N. We define a flop operation on a set of elements as swapping the minimum element of the set with the maximum element of the set. There will be Q flop operations, each specifying two numbers l and r (1 \leq l \leq r \leq N). For each operation, you must perform a flop on the interval [l, r] (that is, on the segment of numbers a_l, a_{l+1}, \cdots, a_{r-1}, a_r). You must perform the Q flops in the order given, and report the final result.

Now that he is finished with the problem statement, Robert needs to create some test data. For one test case in particular, he is trying to encode an inside joke into the initial and final sequences of numbers. With these two sequences fixed, help him find any sequence of flop operations that transforms the first sequence into the second.

Input Specification

The first line will contain the integer N\,(1 \leq N \leq 4096). The second line will contain N distinct space separated integers between 1 and N, representing the initial sequence. The third line will also contain N distinct space separated integers between 1 and N, representing the final sequence.

Output Specification

The first line of output should contain the integer Q, with Q \leq 300\,000. The next Q lines should contain two integers l and r with 1 \leq l \leq r \leq N.

For 5 of the available 25 marks, N \leq 100.

For an additional 10 of the available 25 marks, N \leq 2048.

Sample Input

1 3 5 6 4 2
1 2 3 4 5 6

Output for Sample Input

2 3
3 6
2 5
4 5

Explanation for Output for Sample Input

The first flop swaps 3 and 5, the second flop swaps 6 and 2, the third flop swaps 5 and 2, and the fourth flop swaps 5 and 4.


There are no comments at the moment.