Сегодня у меня попалась комната, ну очень хорошая для взломов. Листаю я коды (Задача А div. 2), и тут натыкаюсь на явно квадратичное решение, а ограничения на длину строк 10^5.
Пишу тест:
aaaaaa...aaa(10^5)
bbbbbb...bbb(10^5)
Отправляю просто скопировав из файла, который вывел мне мой тестген. Выходит ошибка, что невозможно обработать тест. Потом пробую отослать сам файл(txt) с тестом. Ошибка та же.
Задаю вопрос жюри. Они отвечают, что тест слишком большой, и надо писать программу, которая бы выводила тест в стандартный поток.
Думаю, ну ладно. Пишу генератор:
for (int i = 0; i < (int)1e5; i++)
cout << 'a';
cout << endl;
for (int i = 0; i < (int)1e5; i++)
cout << 'b';
cout << endl;
Отправляю, выходит ошибка "**Неизвестный вердикт:GENERATOR_CRASHED**", оказывается, генератор работает долго.
Не печалюсь, исправляю все на printf, ошибка та же.
Попробовала putchar, все равно ТЛ.
Думаю, запишу ка я все в строку, а потом выведу ее. Получаю ошибку памяти (ML).
В итоге, получилось завалить решение, когда я создавала строку длиной не 10^5, а только 30000.
Убила очень много времени, чтобы подогнать, чтобы не было ML и TL.
Как вообще поступать в таких ситуациях? А если бы решение было не совсем квадратичное, и на 30 000 заходило бы(со скрипом), а на 100 000 уже нет?
Вот этот код в запуске работает 30 мс.
Как вариант, можно засунуть всё в char[], создать строку от этого массива и вывести её.
Вы попробуйте лучше все выводить у себя на компьютере. В консоль. Там оно действительно работает долго. Со строками работало быстро, но ВНЕЗАПНО получало ML. Могу предоставить все скриншоты.
Да, как ни странно, вывод в консоль 10^5 символов будет долгим) Вообще, и 10^6 обычно без проблем запросто генератором выводится.
Каким генератором?
Тем, что приведен в тексте блога, или в комментарии выше. P.S. я имею ввиду, на сервере
Проверил, локально все символы выводятся в пределах 20 мс.
в файл?
В консоль.
Если честно, меня очень удивляет, как оно тут за 30 мс работает...
может на сервере он работает так быстро, потому что выводит первые 255 символов, и дальше перестает выводить
Да да да.
Это не так на сервере решение запускается полностью просто выводится префикс вывода.
Эту ошибку получает код выше.
А эту — со строками.
Блин, ну в 10-то секунд он должен был уложиться. Проблема в чём-то другом.
Со строками, у меня есть еще одна посылка, на 50 000, и она тоже ловит ML. Почему???
Может какие-то лишние параметры генератора?
нет. Там генератор у меня считывал длину n, и до n выводил строки "aaaa" и "bbbb". В скриншотах я вводила как раз 100000.
Скорее всего в этом и проблема, выложи считывание.
Печально, что исходники нельзя глянуть. Сейчас восстановлю весь код. вот он
вот такой вот был код. Точь-в-точь.
Параметры генератора передаются в argv, а не считываются через cin)) Прога просто либо не считывала, и в n шлак был, либо ждала ввода, как я понимаю.
что?
Стоп, а когда я вводила также n = 30000, все зашло.
int main(int argc, char *argv[]), а потом atoi(argv[0]), или atoi(argv[1]) если еще имя приложения передаетсяЧто? Генератору-то на вход ничего не даётся, и
будет ждать вечно.
=================================================== А зачем ему параметры тогда вообще? Как надо было писать?
p.s. почему-то исчезла возможность смотреть свои взломы, или я просто уже ничего не вижу.
========================================================== Странно как-то. Я вроде также делала, для n = 30000, и все зашло. О_О
Можно в argv что-нибудь разное передавать, не меняя код генератора.
Ну и... Почему нельзя было задать n константой?..
Потому что при каждом «str += 'a';» создаётся новый объект с буфером, размер которого равен размеру строки. Так что общий расход памяти будет превосходить 2 * sizeof(char) * (1 + ... + 50000).
Upd: неправда, см. комментарии ниже.
Казалось бы, при
+=как раз происходит перевыделение, а не создание нового — примерно как сvector<>::push_back.Ок, насчёт operator+= — спорно (надо смотреть реализацию STL), но operator+ точно должен выделять новый буфер.
Он новый выделит, старый-то он освободит.
Угу, и 100к выделений памяти небесплатны.
Почему ML — хрен его знает.
Проверил, += действительно не пересоздаёт постоянно буфер.
Так, а как поступать в итоге?
Никак. Это правильно, лишняя память будет при
str=str+a, и то, не очень много. Может файл не тот отправляешь?Нет =) Это исключено =) Я очень много раз отсылала, и проверяла много раз, что отсылаю то, что нужно =) Взломала я этого человека с 9 раза )
Взламывал спокойно генераторами вида
print 'a'*10**5print 'b'*10**5Правда не на этом раунде. Покажи весь генератор, может станет понятнее почему он падал.
Какой-то генератор к предыдущему соревнованию:
Возможно, меня спасает ifdef... Без него не пробовал.
Оффтоп, но меня по поводу взломов интересовало две вещи:
1) Можно ли юзать обфускаторы кода? :) Тогда смотрящий точно не поймет, в чем слабость алгоритма. Особенно применяется к антихеш-тестам для конкретного основания хеша и способа хеширования, которые в тестировании встретятся наврядли. 2) Скопировать чужой код, я так понял, из окошка взлома нельзя (чтобы проверить какой-то тест на правильность). А зачем это сделано? Сам не встречал, но неужели нет какого-нибудь OCR для этого, напечатанный код то с картинки распознать, или вообще как-то напрямую? Задача интересная )
Если минусуете, то популярно объясните, почему.
На Topcoder в явном виде запрещено. Тут, видимо, нет, но Вам же хуже: не узнаете о неверности решения во время контеста — точно потеряете баллы.
Нет, нельзя. Сделано, например, чтобы нельзя было застрессить решение со своим "правильным" и вбить тест. OCR, конечно, бывают (например, которые распознают фото документов), но я не видел, чтобы кто-то с этим заморачивался.
Я как раз отметил не "неверные" решения, а "почти всегда работающие" :) Например хеши со специфичным основанием, которые не взламываются итоговыми тестами, или какие-то костыли, с которыми, например, макстест проходит по времени, а немножко (но правильно) измененный — нет. Так что от взлома такого решения автор именно потеряет.
Да, именно для этой цели и имеется в виду. А ведь если заморочиться и автоматизировать процесс, профит будет серьезный, нет?
(мне просто любопытно)
Про OCR здесь выглядит абсолютной халявой, т.к. убиваем цвет + считаем корреляцию должно давать 0% ошибок.
Вот-вот, распознать идеальную картинку задача вообще простая и даже не творческая ) Поэтому и думается, что кто-то, да заморочился.
1) Допустим, что в решении участника есть ошибка. Рассмотрим две стратегии: а) решение обфусцировано, его никто не взломает; б) решение не обфусцировано, тогда кто-то его взломает.
В случае а) имеем: решение не взломано и падает на системном тестировании. Участник: +0 очков, потенциальный взломщик: +0 очков.
В случае б): решение взломано, с немалой вероятностью участник находит ошибку и перепосылает правильное решение. Участник: +300—… очков, взломщик: +100 очков.
Ну и какая стратегия лучше для участника?
2) Это сделано для того, чтобы нельзя было у себя запустить программу и быстренько посмотреть, действительно ли она выводит неправильный ответ.
Подозреваю также, что и обфускация, и попытка скопировать код является нарушением правил.
Обфускации бывают разные. Я например на CF разок получил -50 за попытку челленджа по обфусцированному решению — сначала было написано правильное решение, потом return, потом неправильное ровно на страницу просмотрщика. С такой стратегией взломщик (прокрутивший решение до конца и увидивший баг) получает -50, а участнику-обфускатору от такого никаких убытков.
И да, что-то я в правилах не нахожу ничего про запрет OCR/перехват текста программы до рендеринга флешом.
В Codeforces Round 155 (Div. 2) я пытался взломать решение, где был выделен массив на 3000, хотя в худшем случае может использоваться 3*10^5. Написал генератор на паскале:
Получил ошибку (некорректный тест) FAIL Unexpected character #13, but ' ' expected (stdin). Может кто-нибудь знает, в чем дело?
Найден перенос строки. Ожидался пробел
Там надо было 2*n чисел во второй строке выводить
код 13 — переход на новую строку, значит последний writeln не нужен.
спасибо, понял ошибку, жалко, что 100 баллов потерял(