Mọi người giải thích cho e về phần sort bài DTKSUB của e vs:

link1: http://ideone.com/biRasf#comments

 x:= a[random(h-l+1)+l];

link2: http://ideone.com/FzKgVC

x:= a[(h+l) shr 1];

Nếu có suy biến khiên chạy chậm thì cách 2 sẽ dễ bị hơn nhưng trong khi đó e nộp thì link1 TLE còn link 2 thì AC.

Mong mọi người giải thích cụ thể cho e :D :v

Cách thứ 2 AC là do test của chúng nó mấy thằng ở vị trí giữa thường gần trung vị nên chạy nhanh. Cách chọn chốt như vậy rất dễ bị suy biến.

Cách thứ 1 thì cho độ phức tập ổn định hơn và khó bị suy biến.

Bạn có thể dùng nút thứ 9 từ trái sang để chèn link nhé :p