Блог пользователя eldonak

Автор eldonak, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +26
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

This explanation is pretty well organized and I mentioned in my post that it was a NlogN solution because I didn't notice that constraint i.e 1 <= Ai <= n. Otherwise, your solution is perfect and better than mine. btw I wanted to explain the same logic you explained. But I pretty much messed up the explanation. After getting so many downvotes I was actually sad over the fact that I just wanted to introduce a way to solve but things turned out differently.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sometimes I don't understand the number of downvotes in some posts. There was an AC code in your post so it's not like you were presenting a rubbish as a solution to people. Even if you hadn't given any explanation and said I don't know why but this approach works, it should be ok in my opinion. Isn't it the purpose of these posts, to complete each other. So, don't worry about the downvotes, keep being nice.