[Problem] Minimum number of swaps to sort an array (with duplicates)

Правка ru1, от Skeef79, 2022-05-27 20:48:05

You are given an array $$$a$$$ of length $$$n$$$. Notice that array can contain dupilcate elements.

You can perform the following operation:

  • choose two integers $$$i$$$, $$$j$$$ such that $$$1\leq i,j \leq n$$$
  • swap $$$a_i$$$ and $$$a_j$$$

Find the minimum number of operations to sort the array.

It seems like a very natural problem, but I didn't find any solutions to it. Does anyone know the solution?

Some thoughts:

Let $$$a'$$$ be an array $$$a$$$ after sorting. Let's consider a graph $$$G$$$ with edges $$$a'[i] \rightarrow a[i]$$$. So now we need to somehow decompose this graph into cycles, such that the number of cycles is maximum.

To do that we can notice that $$$G$$$ is an euliran graph so we can find an euler cycle of it (let's store it in array $$$p$$$). Now each cycle in $$$G$$$ is some segment in $$$p$$$ which starts and ends in the same number (actually it can be circural segment). So we have some segments in $$$p$$$ and we need to find the maximum number of segments, such that they do not intersect (but they can lie inside each other and touch). This problem seems like some dp on segments, but I didn't figure it out yet.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Skeef79 2022-07-11 20:19:55 1188 Initial revision for English translation
ru1 Русский Skeef79 2022-05-27 20:48:05 1188 Первая редакция (опубликовано)