## IOI '15 P5 - Sorting

View as PDF

Points: 25 (partial)
Time limit: 4.0s
Memory limit: 256M

Problem type
Allowed languages
C, C++

Aizhan has a sequence of integers . The sequence consists of distinct numbers from to . She is trying to sort this sequence in ascending order by swapping some pairs of elements. Her friend Ermek is also going to swap some pairs of elements — not necessarily in a helpful way.

Ermek and Aizhan are going to modify the sequence in a series of rounds. In each round, first Ermek makes a swap and then Aizhan makes another swap. More precisely, the person making a swap chooses two valid indices and swaps the elements at those indices. Note that the two indices do not have to be distinct. If they are equal, the current person swaps an element with itself, which does not change the sequence.

Aizhan knows that Ermek does not actually care about sorting the sequence . She also knows the exact indices Ermek is going to choose. Ermek plans to take part in rounds of swapping. We number these rounds from to . For each between and inclusive, Ermek will choose the indices and in round .

Aizhan wants to sort the sequence . Before each round, if Aizhan sees that the sequence is already sorted in ascending order, she will terminate the entire process. Given the original sequence and the indices Ermek is going to choose, your task is to find a sequence of swaps, which Aizhan can use to sort the sequence . In addition, in some subtasks you are required to find a sequence of swaps that is as short as possible. You may assume that it is possible to sort the sequence in or fewer rounds.

Note that if Aizhan sees that the sequence is sorted after Ermek's swap, she can choose to swap two equal indices (e.g., and ). As a result the sequence is also sorted after the entire round, so Aizhan reaches her goal. Also note that if the initial sequence is already sorted, the minimal number of rounds needed to sort it is .

##### Example 1

Suppose that:

• The initial sequence is .
• Ermek is willing to make swaps.
• The sequences and that describe the indices Ermek is going to choose are and . In other words, the pairs of indices that Ermek plans to choose are , , , , , and .

In this setting Aizhan can sort the sequence into the order in three rounds. She can do so by choosing the indices , , and then .

The following table shows how Ermek and Aizhan modify the sequence.

RoundPlayerPair of swapped indicesSequence
beginning
Ermek
Aizhan
Ermek
Aizhan
Ermek
Aizhan
##### Example 2

Suppose that:

• The initial sequence is .
• Ermek is willing to make swaps.
• The pairs of indices that Ermek plans to choose are , , , , and .

In this setting Aizhan can sort the sequence in three rounds, for example by choosing the pairs of indices , , and then . The following table shows how Ermek and Aizhan modify the sequence.

RoundPlayerPair of swapped indicesSequence
beginning
Ermek
Aizhan
Ermek
Aizhan
Ermek
Aizhan

You are given the sequence , the number , and the sequences of indices and . Compute a sequence of swaps, which Aizhan can use to sort the sequence . In subtasks and , the sequence of swaps you find has to be the shortest possible.

You need to implement:

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]);

• This function will be called by the grader exactly once.
• N: the length of the sequence .
• S: an array of integers containing the initial sequence .
• M: the number of swaps Ermek plans to make.
• X, Y: arrays of integers of length . For , in round Ermek plans to swap numbers at indices and .
• P, Q: arrays of integers. Use these arrays to report one possible sequence of swaps Aizhan can make to sort the sequence . Denote by the length of the sequence of swaps that your program has found. For each between and inclusive, the indices Aizhan should choose in round should be stored into and . You may assume that the arrays P and Q have already been allocated to elements each.
• This function should return the value of (defined above).

subtask points extra constraints on , requirement on
1 8 for all
2 12 for all
3 16 for all
4 18 none
5 20 none minimum possible
6 26 none minimum possible

You may assume that there exists a solution that requires or fewer rounds.