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. :stuck_out_tongue_winking_eye:

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

This Hall’s Marriage Theorem ?

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