Easy Solution of D in Round#759

Правка en1, от GlydonNeedsDedication, 2021-12-13 10:58:55

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 at least 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

Теги editorial, observation, help

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский GlydonNeedsDedication 2021-12-13 11:02:12 9 Tiny change: 'u require at least 3 element' -> 'u require 3 element'
en2 Английский GlydonNeedsDedication 2021-12-13 10:59:42 18
en1 Английский GlydonNeedsDedication 2021-12-13 10:58:55 887 Initial revision (published)