GlydonNeedsDedication's blog

By GlydonNeedsDedication, history, 3 years ago, In English

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can you please explain why we can always sort using duplicates?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

From your blog it's not clear why either of these statements are true. Care to explain?

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

By the way, this solution is $$$O(n)$$$ as well. Why did you said $$$O(n*log(n))$$$?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, your solution is really good. Took me some time to figure out how it is working but WOW.