Здравствуйте.
Проблема, которую я только что обнаружил, а I_love_natalia тому свидетель, возникла при генерации antiquicksort-теста. В частности, из-за этого бага я сегодня схлопотал неудачный взлом. Я очень удивился, когда во время контеста программа жертвы, взломанная таким генератором, отработала быстро. Однако под конец контеста я поменял размер массива с 100000 на 99987, и взлом стал успешен!
А теперь коротко о том, что же происходит. Вот тест-кейс:
Запустим генератор (чуть-чуть измененный, брать отсюда: http://pastebin.com/99RwHR6w) в запуске на сервере CF.
Сервер выведет что-то наподобие
Sorting ended in 1953msДобавим в конец файла два перевода строки и запустим снова
Результат поражает:
Sorting ended in 0ms. Вот что переводы строки животворящие делают!
Можно поэкспериментировать с добавлением и удалением пробелов и переводов строк: результаты будут отличаться: либо сортировка проходит за нулевое время, либо за примерно 2 секунды.
Для любителей острых ощущений прилагается видео: ссылка (осторожно, в распакованном виде оно занимает около 600 МБ)
Что это такое? На моем домашнем компьютере такого не происходит. Баг Java-машины, или сервер CF пытается уберечь участников от взлома?
UPDATE: Судя по всему, на некоторых серверах стоит Java 7, на которой сортировка реализована по-другому и выполняется на этих тестах быстро. Это очень нехорошо, т.к. я выбираю язык Java 6, когда хочу послать задачу, а она, оказывается, может тестироваться под Java 7. Прошу всех принять это к сведению, пока администрация все не поправит.
То есть, получается, генератор генерирует разные последовательности в зависимости от наличия пробелов в исходнике?
Последовательности одинаковые, а вот время сортировки почему-то разное.А вот и нифига, ждите breaking news от I_love_natalia!
Последовательности на самом деле разные. Вот выдача
Первая выдача
Scrambling ended in 2140ms with 11104pivots
hashCode = 5442986
Sorting ended in 1906ms
Использовано: 4090 мс, 45228 КБ
Вторая выдача
Scrambling ended in 2703ms with 11104pivots
hashCode = 9047389
Sorting ended in 16ms
Использовано: 2250 мс, 47088 КБ
Поведение кода зависит от пробела в нем.
Кстати, попробуйте вычислить хэш-код предварительно инициализированного массива.
Думаю, тут прикол в другом. На codeforces если код скомпилировался — то все его последующие запуски будут на одной и той же машинке. Добавляя пустые строки, вы заставляете его перекомпилироваться и сменить тем самым машинку. А тестирующие машинки разные — я на это уже разок напоролся (в "запуске на сервере" мне повезло с машинкой, а в систестах — нет). Видимо, java там тоже разная :)
Читай выше, только что дописал про поведение.
Ну это пока не опровергает мою гипотезу. Поведение может зависеть не от пробела в коде, а от версии джавы.
Дело в том, что одинаковые (побитово) исходники всегда исполнялись за одинаковое время. Пробовали раз 5-6, наверное.
Надо спросить у администрации: а одинаковая ли Java стоит на всех серверах?
Кстати, думаю, кто-нибудь, у кого на компьютере много версий Java стоит, может ответить, а одинаковый ли в них во всех класс java.util.Arrays?
В седьмой жабе уже идет Dual-Pivot Quicksort. Интереснее то, как реализована функция Array.hashCode(). Но исходников OpenJDK 7 на моем ноуте на данный момент нет.
Что, серьезно что ли? Dual-Pivot Quicksort? Facepalm. А сделать, как у всех нормальных людей Introsort им религия не позволяет?
Edit: вообще, я вспомнил, что я уже выражал свое мнение по этому поводу здесь. Был бы признателен, если бы кто-нибудь объяснил мне, в чем я был не прав тогда.
Серьезно.
В чем Вы были тогда неправы — сказать не могу, могу только посоветовать сравнить на аналогичных тестах сортировку из JDK 6 и JDK 7.
Да, спасибо, я сразу пошел исходники изучать. Это я просто выражал свое искреннее недоумение этим решением.
Ну наверняка там скомпилированные исходники source'ов закешированы, поэтому побитово одинаковые программы будут исполняться на одной и той же машинке.
Сейчас проверил — там везде версия 1.6.0_29. Но при этом значения, выдаваемые вашей программой при добавлении пробелов, повторяются, и количество различных значений подозрительно похоже на количество тестирующих машин :)
А, нет. Вот машинку с 1.6.0_30 нашёл :)
Можно вызвать GetTickCount апишную? Или подобным образом идентифицировать машину?
(GetTickCount от включения считается).
Сходится идеально. Логи запусков в правке, первое число — System.nanoTime(). И да, 0 только на 7ой джаве.
На одном из серверов стоит Java 1.7? Мне кажется, это очень нехорошо. По моему выполнению
27972789935386 — OK 57875555302061 — OK 40964117868683 — FAIL 45682842921039 — OK
В частности, ты не попал на еще один сервер.
Ну да, 40945109233456 — это 7ая джава.
Ну, "очень нехорошо" уже то, что машинки разные. Остаётся надеяться, что вконтакт проспонсирует на запупку одинаковых :)
Я думаю, что ВКонтакте не разорится от приобретения 4 БЕСПЛАТНЫХ одинаковых версий JVM :)
А почему решили, что машины разные? Они абсолютно одинаковые.
Как Java 7 пробралась не знаю, но ее мы изничтожим :)
Прошу прощения у dalex, а Java 7 присоединяется.
Ну где-то полгода назад они точно были разные. По крайней мере, на одних мой код стабильно влезал в ТЛ, на других — стабильно не влезал. И во время контеста при тестировании на макстесте мне повезло с машинкой, а на систестах — нет. После контеста я поэкспериментировал с добавлением пробелов в программу и обнаружил, что разброс был ~100мс (не помню сейчас точно, но 50мс точно было).
А реджадж контеста будет? ;)
Предлагаешь реджаджить все посылки на яве за все время существования CF? Тысяч триста? ;)
Нет, реджаджа не будет, будет расправа над Java 7 :)
Взлом неудачный отмените человеку, ему же важен результат даже при внеконкурсном ;)
Кстати, похоже, "левых" Java-решений не прошло. Так что реджадж и правда не нужен.
А почему не сделать наоборот и не заменить Java 6 на Java 7?
Может быть стоит оставить Java 7 отдельным компилятором?
Я на жаве пишу не часто, на CF вроде вообще не писал. Но мне одному эта ситуация кажется бредовой? Что ломают библиотечную сортировку. Теперь вместо решения задач люди будут писать свои сортировки рандомно шафлить массивы перед сортировкой. Если жава 7 лишена такого недостатка, может как сказал SergeyLazarev стоит обновиться?
...люди будут писать свои сортировки...
оужасже
По-видимому, сортировка и в седьмой джаве ломается, там же тоже квиксорт заявлен. Речь не об этом: сейчас решение может проверяться не на том комплиляторе, что был выбран при отправке, и это надо исправить.
Кстати, в последний год задач, где нужна была сортировка, почти не было. Вчера авторы навели интригу, написав все до начала раунда, и мы получили то, что есть.
В Java 7 quicksort'ом сортируются только небольшие отрезки, которые потом merge'атся.
Не совсем так. Все же в большинстве случаев в Arrays.sort для встроенных типов будет отрабатывать Dual-Pivot Quicksort. Mergesort там выполняется в довольно редких случаях почти отсортированных данных, если внимательно посмотреть на код. Видимо, это сделано для того, чтобы уменьшить количество вариантов вырождения в квадратичную сложность, даже не знаю.
Как написано в комментариях "This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance". Нигде ничего не написано про сложность O(n log(n)) в худшем случае.
Исходный код для изучения Edit: Сорри забыл основную ссылку
С одной стороны, да: может, несколько глупо.
С другой: человек может выбрать инструмент + сам потрудиться, чтобы выполнить поставленную задачу. Для любых 10^5 чисел посортить их за 2с. И если он выбирает для этого Java, которая говорит: я посорчу в среднем за nlogn, то участник — ССЗБ
А почему бы и не ломать библиотечные методы? Если участник на С++ напишет printf(s); я с удовольствием напишу ему тест !!!!!?!?!!???!!?!???!??? если такое допустимо входными данными. Или %d%u%s. Участник использует какой-то метод — участник берет всю ответственность на себя.
test
The victim would be me :D
May I ask in which version of Java is the problem actual? Java 7 or Java 6? Thanks
There's no problem any more. The only problem was "when you submit your solution under Java 6 it can run under Java 7 instead".