После небольших обсуждений, мы решили все-таки выложить код генератора, который вызывает #TLE у коллекций HashSet и HashMap в Java.
Вот он — http://pastebin.com/qpyNcD3R
Идея: давайте заставим хеш-коллекции складывать все элементы в одну корзину.
Особенность реализации HashSet/HashMap в том, что они использует линейное преобразование хеша, а затем как номер корзины использует остаток от деления хеша на bucketsNumber.
Цитаты из оригинального кода:
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length-1); /*length всегда степень двойки --- DK*/
}
Собственно, вся сложность заключается в построении обратного преобразования — вот оно:
int hashinv(int h) {
h ^= (h >>> 4) ^ (h >>> 7) ^ (h >>> 8) ^ (h >>> 14) ^ (h >>> 15)
^ (h >>> 18) ^ (h >>> 19) ^ (h >>> 20) ^ (h >>> 21)
^ (h >>> 23) ^ (h >>> 26) ^ (h >>> 28);
return h;
}
Далее, просто выписываем числа:
final int size = 100000;
int[] s = new int[size];
for (int i = 0, val = 0; i < size; i++) {
s[i] = Integer.MAX_VALUE;
while (s[i] > 1000000000)
s[i] = hashinv(bitreverse(val++));
}
Здесь bitreverse обращает порядок младших 31 бита в числе.
Этот генератор работает для версий Java 6 и Java 7 при любом не очень сложном преобразовании порядка ввода (сортировка, random_shuffle, и т.д.).
Удачных вам взломов!
Заваливать библиотеки с уязвимостями — дело хорошее. В конечном счёте, если авторам библиотечной функции показать, что это реальная проблема, все от этого даже выигрывают.
Для пар и троек целых чисел, насколько я знаю, некоторые среды программирования умеют генерировать реализацию по умолчанию, так что тоже можно завалить.
Честно говоря, здесь вообще нет идей, как избежать возможного #TLE и не потерять при этом производительность в среднем случае.
С философской точки зрения, СП содержит огромный перегиб в пункте "должно работать на всех тестах". Правильно — "должно работать на всех РАЗУМНЫХ тестах". Вряд ли когда-нибудь кто-нибудь сталкивался с проблемой, описанной выше, не создавая ее специально. Совершенно неясно, как использовать ее, как и проблему с #TLE в Arrays.sort, вне СП; то же самое (вероятно, такой генератор тоже сделаем) с известной полиномиальной хеш-функцией для String в Java. Весь мой опыт практического программирования протестует против учета столь редких возможных проблем на практике.
Теоретически, можно заDoSить/заDDoSить что-нибудь, практически — сам этого не делал.
Сами придумали обратное преобразование?
Кажется, что это не сложнее, чем обратить матрицу 32 × 32 — какие биты исходного вектора складываются в какие биты полученного. А потом внимательно посмотреть на результат, и он тоже окажется состоящим из диагоналей, на которых стоят единицы. Или не окажется?
Понадобилось 10 минут. Кажется, делал так:
По-хорошему, надо бы как-то запретить правилами юзать подобные "особенности" компиляторов...
А мне кажется, что это полностью логично. Захотел человек использовать такой язык/компилятор — изволь познакомиться с особенностями стандартной библиотеки.
Отношение у меня к этому такое же, как и к просьбам поднять ограничение для Python'а в пару раз, когда авторское решение на C++ заходит с 5-кратным запасом.
Я думаю, можно просто не делать таких задач. Например, на 129 раунде ничто не мешало авторам ограничить значения чисел величиной 2n. Проверка на то, что участники умеют сжимать координаты, она глупая какая-то, по-моему.
Массивы вполне можно давать уже отсортированными. А если приходится сортировать что-то сложное, надо писать классы, и Java их mergesort-ом сортирует, т.е. с этим проблем нет.
Проблемы как минимум в том, что:
это будет очень сложно отсечь формальным правилом,
то, что добавление такого правила ставит участников в более равные условия — спорно.
1. это будет очень сложно отсечь формальным правилом
Формального правила конечно не нужно. Обычно во всех видах спорта подобные тонкие моменты обходятся правилом под названием "на усмотрение арбитра". Провозгласить что-то типа: "Запрещено использование уязвимостей стандартных функций". А разбираться уже по факту...
Как вы себе это представляете?
Давайте лучше запретим участникам делать выходы за границу массивов, потому что они в некоторых языках ловятся сложнее.
Нравится писать на Java — пожалуйста. У нее более мощная библиотека — пользуйтесь. Но то что авторы не удосужились написать сортировку за NlogN не в среднем, а всегда, и их hash на ура ломается за 10 минут — это ваши проблемы. Тем более, что Prewritten code разрешен. Напишите свою сортировку и свой hashset которые будут без таких проблем.
А заодно и свою Java ... тошнить от такого начинает. Здесь в конце концов алгоритмы важны или теперь всё превращается в использование "косяков" в реализации определенного языка ? Давайте тогда и в С++ поищем... сразу подключим Питон с Руби... там медленное чтение, так давайте давать столько данных, чтобы на них не проходило... это же тоже вроде "уязвимости" ?
Если вы найдете тест, на котором валится std::sort я обещаю добавлять его во все задачи, которые делаю.
Питон, кстати, автоматически получается завален в половине задач.
Например, какую-нибудь тривиальную динамику на двумерном массиве 2000 × 2000 в две секунды впихнуть уже довольно сложно.
Мое мнение: это соревнования по программированию, а не по дискретной математике, теории алгоритмов и проблемам вычислимости. Надо не только придумать решение, но и написать его так, чтобы работало быстро и не валилось (даже по глупым ошибкам). Причины взрыва шаттла через полторы минуты после старта мало волнуют космонавтов.
Если бы не было взломов, такое бы делалось неформальным "ай-яй, авторы так не делайте". Как это можно запретить на взломах — совсем не ясно.
Я умею. Запретить Java. Вообще оставить один язык, чтобы все были в равных условиях.
P.S. Надеюсь написанное выше, не только мне кажется бредом.
Ну и компилятор доступный только один, само собой лол
Эм, а в этом языке запретить случайные коллизии хешей?
Обязательно. Если у тебя/в результате твоего взлома случилась коллизия хешей или вообще не общий случай чего-нибудь, то сразу дисквал. А лучше со всему участниками контеста. На всякий случай.
Просто раздельные рейтинги по языкам.
На самом деле это лечится за 4 минуты своим наследованием от HashMap/Set и похожей функцией хеширования, разве нет?
Адаптировать генератор к похожей функции хеширования — дело тех же нескольких минут...
Можно константы для сдвига случайные брать попробовать.
Тогда они случайно окажутся близки к нулю или размеру машинного слова, и тормозить будет уже на каком-нибудь совершенно обычном тесте (не взломе) — например, на числах, кратных большой степени двойки.
Ну скажем если генерить как +/- единицу от тех, что есть, мне кажется к совсем катастрофическим последствиям не должно приводить. В то же время, генератор с гарантией с первой попытки ломать уже вроде не должен.
Ну, это обходится — h ^ (h >> rand(2, 5)) ^ (h >> rand(6, 9)) ^ ...
Можно солить хеш случайным числом, выбираемым при старте программы.
Каким образом солить? Xor и сложение по модулю 2^32 не покатит точно. Сложение по некоторому другому модулю — крайне сомнительно. Если множить по модулю — надо писать лишнее деление по модулю.
Спасибо! Значит будем использовать TreeMap : — )
I_love_natalia: challenge accepted!
А я вот уже написал EHashMap/EHashSet с рандомизацией числа бакетов
Well, then the question arises.. what should I use then?!
Hmm... TreeMap and compareTo instead of HashMap and hashCode?
В Java 8 похоже решили эту проблему:
http://openjdk.java.net/jeps/180
Improve the performance of java.util.HashMap under high hash-collision conditions by using balanced trees rather than linked lists to store map entries. Implement the same improvement in the LinkedHashMap class.
Так что вроде бы не решили.
А, это старое изменение. Для String теперь все должно быть надежно. Но они обещают что-то совсем непонятное. Деревья вместо списков? Это скорее всего на обычных (не имеющих целью ничего завалить) данных будет медленнее работать, чем текущая реализация.
может и не будет медленнее — они ввели threshold в HashMap.java:
It seems to take a lot of time to find enough numbers less than 100000 while it barely take time to find enough numbers less than 1000000000.
Do you want to find 100000 different positive integer numbers less than 100000?
I got it!
T.T
What about if I change the load factor?
As I know bucketsCount would be different and the code for hacking should be different (I guess).