# CF-655-DIV2 C

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.

1 Like

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.

2 Likes

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

1 Like

This is what I did.

1 Like

Yeah me too. Editorial is really complex this time

1 Like

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.

4 Likes

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.

1 Like

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.

1 Like
1 Like