Problem Statement - Link

I have come across such problems involving permutation of sub-sequences or sub-arrays(Triple Sort for e.g.).

What area of mathematics this corresponds to?(Symmetry groups, maybe?)

The solutions usually have a mathematical root.

This was Ad-hoc problem. I didnâ€™t see any hard mathematics in it.

One can view it as : Number of cyclic permutations of sub-arrays to sort it. My question comes from this line of thought.

The Editorial seems bit complicated.

Iâ€™ll explain what I did. If it is already sorted, then 0.

If the array is not sorted and no element is at its correct place. We can do it in 1 go. I hope this doesnâ€™t requires any proof. It is just putting element from its old wrong postion to new correct position and weâ€™ll get the sorted array.

If there are some elements which are at correct positions, then remove the sorted elements in front and in the end (if any) â€¦ consider only the middle part. If in the middle part each element is at wrong postionâ€¦then ans is 1 by previous logic. else you just position every element at wrong postion in 1 go and sort them in another go. So, here ans is 2.

Let say set of cont wrong values be `W`

and correct be `R`

Possible seq are

W ans=1

R ans=0

WR ans=1

RW ans=1

RWR ans=1

any other case ans=2

For any wrong set you can convert it in one step

This is what I did.

Yeah me too. Editorial is really complex this time

That is because the editorial is required to prove the solution, whereas you have only outlined the algorithm. Though Hallâ€™s theorem gives a simple direct proof.

Did it really require a proof? I found it to be obvious by my above explanation. I hope there is no flaw in my explanation. Can you check?

This is the part of your proof that needed Hallâ€™s theorem.

Yes. You can use it to prove that there exists an intermediate permutation such that any element is neither at itâ€™s initial position or final position. Consider an edge from each index to all nodes that are not itself and itâ€™s final position.

Or better put, there exists an edge from i to j if j \not = i and j \not= A_i. We need a perfect matching in this graph to find our intermediate permutation.