Glydon's blog

By Glydon, history, 7 months 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

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

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    7 months 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.

»
7 months 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?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have explained above about 2 duplicates, In short as per observation you can always see when you have no duplicates You can reach a sorted situation in max (n-2) steps, because when (n-2) elements can always be arranged in the right order and always 2 elements are left to judge if those 2 are in the correct order or not, if those remaining two values are not in the correct order then they cant be sorted otherwise it's sorted.

    I can't prove mathematically, sorry for the inconvenience , and if this post is really that misleading I will have to remove it.

    Either way, I will like it if Some1 proves this wrong. I am just Newbie. I will not be Upset even if I am proven wrong.
    I thought of sharing this in the first place because it got accepted :(

»
7 months 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.

»
7 months 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))$$$?

  • »
    »
    7 months 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

    • »
      »
      »
      7 months 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.

  • »
    »
    7 months 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

»
7 months 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.