ZZZ's Site

狗蛋儿

26 July 2020

[Codeforces 1375E] Inversion SwapSort

by zzz

Problem Description

Problem Link

Given an array of integers with length ~1000, apply all the inverse pair<i, j> with swap in a certain order to get the array sorted.

Input

3
3 1 2

Output

2
1 3
1 2

Solution

Solution Link

Here from this problem, there are several important strategies.

Transformation to a smaller problem

A outline idea is to fix the smallest number or the largest number to the right index by applying some of swaps. Meanwhile, keep the relative order of the other elements. So, the question of N becomes the question of N - 1.

How to achieve this?

Transformation to an easier problem

A easier problem is to solve the same question for a permutation. We can tag the two elements of the same value with their indices, so they don’t yield additional inverse pair. So, the question of permutation is identitical to the original question, (yields the same output). It’s a important trick to transform an array with duplicate values to a permutation.

Merging the given operations to a more powerful operation

For example, for 4 1 5 3 2, after one iteration, an desired state is 1 2 5 4 3.

4 1 5 3 2
1 2 5 4 3

From which the Loop(轮换) of the index is (1 2 5 4), and the Swaps(交换) here are

1 4
1 5
1 2

,which are

1 pos[4-1]
1 pos[4-2]
1 pos[4-3]

One way to help to visualize / understand the functionality by chaining the swaps <1, x>, <1, y>, <1, z>, is that

ele[1] -> pos x,
ele[x] -> pos y,
ele[y] -> pos z,
ele[z] -> pos 1.

With that abstraction in mind, the construction of the solution will be so much easier.

Looking back

A problem doesn’t kill you makes you stronger.

tags: Codeforces - Constructive - Swap - Loop

Posts

subscribe via RSS