Strange Swaps-Editorial

Links

[Contest](https://www.codechef.com/INSO2018/problems/STSWAP)

Author: Adarsh Kumar

Tester: Manas Gupta

Editorialist: Manas Gupta

DIFFICULTY:

Easy

PREREQUISITES:

Sorting

EXPLANATION:

We have been given an n element array.

We first consider the case in which k < n/2. In this case we can obtain the sorted form of the original array.

Then consider the case in which k>=n/2. In this case the elements which will be at a distance of at most k from both the sides can not be swapped with any other integer and will thus remain in the same index as that in the original array. The remaining numbers can be sorted and placed in the remaining indices.

Author’s Solution can be found here

Tester’s Solution can be found here

5 Likes

I learn a new sorting concept.
Thanks a lot for this question

This is a tricky question.

Can someone provide a more elaborate explanation to the solution proposed. Also can someone please provide the proof for the case when k<=n/2;
Thanks in advance :slight_smile:

@pavitra_ag

Make a graph with n vertices representing the indices of array with edges between all the indices whose values can be swapped. Now find the minimum value in the graph. Move the value to the minimum index by swapping values along the edges. After it has reached the minimum index, remove that vertex and all edges emanating from it. Repeat the process until all vertices are removed.

Following the above procedure, it can be observed that the array can be sorted for all the indices that lie in a connected component.

For k < n/2 all the indices form a connected component and hence the array can be sorted.
For k >= n/2 all elements except the elements at a distance of at most k from both the sides form a connected component and can be sorted.

3 Likes

Can anyone please give a formal proof why in the case of k >= n/2 the elements that are not fixed can be made into a sorted arrangement? Thanks in advance :slight_smile:

@adarshkr532 can you give it in a form of picture please.

So it will become easier to understand the logic of yours.

1 Like