eldonak's blog

By eldonak, history, 3 years ago, In English

This solution has already been introduced by GlydonNeedsDedication in this post, but unfortunately it got many down votes although the solution is correct (because he didn't explain it well?). I'm not sure whether I'll do a better job, but here I go. Here I'm copying my comment in his post and additional explanations.

Case 1: If there are any duplicates in the array. We can swap any pair $$$i$$$ and $$$j$$$ in the array with each other if we have at least one pair of duplicates. Let the $$$d_{1}$$$ and $$$d_{2}$$$ be the numbers which are same. If we want to swap $$$i$$$ and $$$j$$$, then:
First 3-cycle $$$(i,j,d_{1})$$$ then $$$(j,d_{1},d_{2})$$$. Visualization:
$$$ \quad \underline{i} \quad \underline{j} \quad \underline{d_{1}} \quad d_{2} $$$ (the order of these doesn't matter)
$$$ \quad \underline{d_{1}} \quad i \quad \underline{j} \quad \underline{d_{2}} \newline \quad j \quad i \quad d_{2} \quad d_{1} $$$

As you see, $$$d_{1}$$$ and $$$d_{2}$$$ change as well but since they are same it doesn't matter. If we want to change $$$d_{1}$$$ and any other number $$$i$$$, then 3-cycle $$$(i,d_{1},d_{2})$$$ will do it.
$$$ \quad i \quad d_{1} \quad d_{2} \newline \quad d_{2} \quad i \quad d_{1} $$$ (again $$$d_{1}$$$ and $$$d_{2}$$$ same, so it's done)

As a result, we can do a regular swap operation to any pair. Hence the answer is always yes.

Case 2: If there are no duplicates. That means all the elements are different (permutation of numbers $$$1$$$ to $$$n$$$), thus there is exactly one possible position of all elements. Let's use position $$$n$$$ as joker position (I'll explain later). If we want to move a number from position $$$i$$$ to position $$$j$$$ ($$$i \neq n$$$ and $$$j \neq n$$$), then we will do 3-cycle $$$(i,j,n)$$$. Visualization: $$$ \quad i \quad j \quad n \newline \quad n \quad i \quad j $$$ So we can put all elements at the position 1 to $$$(n-1)$$$ to their real positions. Except if its real position is $$$n$$$. After these operations, there is only 2 positions we have to worry about: the position $$$n$$$ and the position that has the value $$$n$$$.

If they are same, that means all the numbers set to their real position, so the answer is yes.
Else, they have each other's numbers, therefore we need exactly 1 swap. However, we can never do that with 3-cycle operations because one 3-cycle operation actually does 2 swap operation (3-cycle(i,j,k) = swap(i,j), swap(i,k)). Therefore the number of total swaps always going to be even after this point. Hence the answer is no.
Here is my code that got AC 138973195

Note: If you're going to upvote this post, consider upvoting GlydonNeedsDedication's post as well.

Full text and comments »

  • Vote: I like it
  • +26
  • Vote: I do not like it