Easy Solution of D in Round#759

Revision en3, by GlydonNeedsDedication, 2021-12-13 11:02:12

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

Tags editorial, observation, help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English GlydonNeedsDedication 2021-12-13 11:02:12 9 Tiny change: 'u require at least 3 element' -> 'u require 3 element'
en2 English GlydonNeedsDedication 2021-12-13 10:59:42 18
en1 English GlydonNeedsDedication 2021-12-13 10:58:55 887 Initial revision (published)