Блог пользователя scorpion

Странная сортировка
Автор scorpion, 13 лет назад, По-русски
В прошедшем контесте была задача на сортировку(http://mirror.codeforces.com/contest/135/problem/Ahttp://mirror.codeforces.com/contest/135/problem/A). Многие писали qsort, но с выбором элемента посередине отрезка на чём и пролетели (http://mirror.codeforces.com/contest/136/submission/940111), но были некоторые участники которым повезло (http://mirror.codeforces.com/contest/135/submission/938576). Кто что думает по этому поводу?
  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Немного не по теме, по поводу ссылок на таски: http://mirror.codeforces.com/blog/entry/2682

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Спасибо, а то я давно хотел узнать как это делается!
    → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Во втором варианте добавляется единичка и, как следствие, плохой тест превращается в нормальный.

→ Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Сложный вопрос, кому тут повезло.
Хотя бы потому, что те, у кого решение не прошло, теперь знают о пользе рандомизации быстрой сортировки, а остальные нет :)
Вообще, вроде бы, в жизни постоянно кому-то везет, а кому-то нет, и многие люди в этот момент учатся на своих ошибках вместо того, чтобы создавать такие странные темы, пытаясь добиться кажущейся им справедливости.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
ИМХО, TL по первой посылке - очень и очень странный.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Мде, вчера измывался над товарищем, обещал, что его qsort словит TL из-за добавления взломов в тесты, а он прошел, я не понял :\
→ Ответить