As I didn't get the solution provided in the editorial of 1585D - Yet Another Sorting Problem and how it can be done with O(N)
I had come up with this logic O(NlogN):
1st-> If there is a duplicate element, we can sort the whole array with the help of those two using the 3-cycle technique so always "YES"
2nd-> if there is no duplicate present, simply take one element at a time and place that element into its perfect position (the position where it should be if it was sorted) using the 3 cycles technique.
When 2 elements are remaining and they are not sorted it means they can't be sorted as you require 3 elements to sort!
There might be better solutions available but I guess it's easy to understand and observe also.
My solution -> click here
Can you please explain why we can always sort using duplicates?
As you have at least 1 duplicate value , lets say X
as count of X >= 2
(we will consider count of X = 2 here )
so if ith index need some value Y and Y!=X , find Y's position in arr , lets say its j
So put one X in position i using 3 cycle technique
and let the 2nd X's position is k
so now simply do 3 cycle sort on these 3 like --
temp = a[i]
a[i] = a[j]
a[j] = a[k]
a[k] = temp
keep repeating this index by index ; at the end, you might see the array is sorted OR 2 elements are misplaced one of which will be X and you know what you have to perform!
just perform 3 cycle sort using X, X, left_value_to_be_sorted
this is only leading us to the correct solution as X has 2 different positions that is considered to be its position. Flexibility is the key here.
My explanation is a mess! Please grab a pen and paper, you will understand better, sorry I have confused you.
From your blog it's not clear why either of these statements are true. Care to explain?
anotherTry -is-this-fft- Let me try to explain the trick about duplicates. The thing is, 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 i \quad j \quad d_{1} \quad d_{2} $$$ (the order of these doesn't matter)
$$$\quad d_{1} \quad i \quad j \quad 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$$$, than 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.
By the way, this solution is $$$O(n)$$$ as well. Why did you said $$$O(n*log(n))$$$?
I needed a duplicate sorted array to compare if the particular element is in its correct position or not, that's why. Give Downvote if you hated
It says $$$ 1 \le a_{i} \le n $$$ in the problem statement. Therefore, when all elements are different, they are the permutation of the numbers $$$1$$$ to $$$n$$$. So, value of a number equal to the correct position of that number.
By the way, I had upvoted your post before I comment. I just tried to say this solution can be done in $$$O(n)$$$ as well.
I just saw your submission of D, and realized I missed a constraint that 1 <= Ai <= n , I solved for in general! Independent of that Constraint :p If you consider that constraint then its O(N) solution
Hey, your solution is really good. Took me some time to figure out how it is working but WOW.
glad you liked it :)