Auto comment: topic has been updated by VMaksimoski008 (previous revision, new revision, compare).

Auto comment: topic has been updated by VMaksimoski008 (previous revision, new revision, compare).

Auto comment: topic has been updated by VMaksimoski008 (previous revision, new revision, compare).

Auto comment: topic has been updated by VMaksimoski008 (previous revision, new revision, compare).

Any problem source?

Disclaimer: I do not know how to prove that this is optimal(not even if it is optimal).

Let us draw an edge from each number placed at the wrong index to the number in the corresponding index. Now you get some directed cyclic graph. For each cycle, there are 2 possibilities: it is made out of both numbers $$$\le M$$$ and $$$>M$$$, or it is made of a single type of number. Let the length of the cycle be $$$L$$$. You can solve the first type of cycle in $$$L-1$$$ operations, by keeping it type 1 until you get to 2. The type 2 cycle has to be changed to a type 1 cycle first, so the length becomes $$$L+1$$$, but it is solved in $$$L+1-1=L$$$ operations. In total for a type 2 you use $$$L+1$$$ operations. Then the answer is the number of numbers not well placed — number of type 1 cycles + number of type 2 cycles.

I am also unsure but I think it will be like this. Draw edge (one-way) between $$$(i,a[i])$$$ for $$$ 0\le i \le n - 1$$$. We will not take into consideration cycles of length 1, i.e the element is pointing to itself (it is in the correct position).First, let's prove the following lemma. $$$\newline$$$ Lemma: If the array is not sorted, we will have at least one cycle with length $$$\ge 2$$$ $$$\newline$$$ Proof: $$$\newline$$$ Since the array contains numbers $$$[0,N-1]$$$ and we draw edges $$$(i,a[i])$$$, there must be an edge starting from index $$$i$$$ and an edge ending at index $$$i$$$. Let's say that there are exactly $$$k$$$ elements which are misplaced (in the wrong position). Then if we have an edge $$$(i,j \neq i) \implies$$$ both $$$i$$$ and $$$j$$$ are misplaced. This means that if we start traversing from some misplaced point $$$s$$$, there exist $$$k - 1$$$ possibilities where will go next s.t we don't form a cycle. Notice how this number decreases as we continue to traverse the directed graph $$$(k-1,k-2,...,0)$$$. Eventually we will visit exactly $$$k$$$ nodes but still have one edge to go through $$$\implies$$$ the end of this edge will be an index already visited, hence there is a cycle. $$$\newline \newline$$$ Now let's call a cycle good if it contains a pair of indexes $$$(i,j)$$$, such that $$$(m-i) \cdot (m - j) < 0$$$ (they are on a different side in regards to $$$m$$$). On the other hand, we will call bad any cycle where this pair does not exist. (Notice how we are unable to make a move on any cycle that we defined as bad because all elements will be on one side.) This means that we can only rearrange elements between themselves in a good cycle. $$$\newline$$$ Lemma: The minimum number of operations needed to arrange a good cycle is $$$sizeof(cycle) - 1$$$ $$$\newline$$$ Proof: $$$\newline$$$ First, let's show that this is actually possible in every case. Assume there are exactly $$$k$$$ elements in this good cycle. Since there are at least 2 edges that crossed the border $$$m$$$, we can pick a start of the cycle to be an edge that crossed the boarder. More formally, we begin the cycle at a point $$$p$$$ s.t $$$\exists$$$ an edge $$$(p,u)$$$ and $$$(m - p) \cdot (m - u) < 0$$$ AND $$$\nexists$$$ an edge $$$(o,p)$$$ and $$$(m - p) \cdot (m - o) < 0$$$, because in this way will split the cycle into two bad parts (if this is the only such point). If this $$$p$$$ doesn't exist, than we must have more than 1 point that both points at and is pointed by another points on the opposite side (in this case we are allowed to use one of them as $$$p$$$ since it will not break the cycle). If $$$k=2$$$ point $$$p$$$ does not exist and we arrange the cycle in one operation. Otherwise we have to pick this point $$$p$$$ and swap $$$(p,a[p])$$$. $$$\implies$$$ in 1 operation we can place any element on it's correct place if it needs to cross the boarder, and we can arrange a cycle of two elements in 1 operation. If we swap $$$(p,a[p])$$$, what we will have left is a cycle of length $$$k-1$$$. Eventually, if we repeat this proces $$$k - 2$$$ times, the cycle will have only 2 elements, hence $$$T = (k - 2) + 1 = k - 1$$$. Lastly, if there exists a lower cost algorithm, it would require $$$< k - 1$$$ operations and we know that it is not possible since there are $$$k$$$ edges and we cannot place two elements in 1 operation on their correct position unless the cycle has length 2, i.e (both are pointing at each other). In other words, we can use the operation to swap two misplaced elements to their correct positions only once.

Now we have an optimal strategy to solve good cycles and we cannot make an operation to a bad cycle. What is left is to intentionally swap an element from this bad cycle with an element from the other side of $$$m$$$, hence we now have a good cycle of $$$k + 1$$$, if $$$k = sizeof(cycle)$$$. Since we can solve this newly formed good cycle in $$$k$$$ moves, the answer is $$$k+1$$$ because we performed a switch in the beginning. Now let's count the number of bad cycles on one side of $$$m$$$ and on the other side, label them as $$$k_1$$$ and $$$k_2$$$. Then we just subtract $$$2 \cdot min(k_1,k_2)$$$ from our original answer because we can merge a pair of bad cycles on opposite sides and save 1 operation.