В 2004 году на просторах интернета появилась игра "Жук", рекламный блог на CF, где необходимо построить лабиринт, который задержит Жука на как можно более длительное время. Сегодня я обновил свой рекорд, построив лабиринт на $$$93.401.998$$$ ходов и, заняв 6-е место в топе, решил сделать зеркало этой игры, подготовив задачу на платформе Polygon и добавив в мэшап на codeforces. У меня это получилось, можно сабмитить решения и набирать (нет) баллы, но получилось не так, как хотелось бы... Первое, что не удалось сделать, это огромные сэмплы в условии задачи. В игре поле $$$21 \times 31$$$ и при попытке добавить сэмпл с таким полем вылезает ошибка и предложение использовать опцию "examples in statements". Где эта опция находится — я не нашёл. Гугление тоже не помогло.
Второе, что не удалось сделать, это пользовательский "Scorer file" на вкладке Advanced. Примеров в интернете и на самом полигоне не было (аналогичных примерам чекеров и валидаторов), поэтому я что-то написал сам, просматривая исходники библиотеки testlib. Это скомпилировалось и должно работать, но не работает — просто не запускается при проверке решения. Даже из-за assert(false); не вылетает. Исходный код того, что получилось. Предполагалось, что чекер будет писать в поле checkerComment, сколько ходов сделал Жук на лабиринте участника, и это значение бы доставалось и возвращалось...
Эта проблема меня не остановила и я решил сделать следующее: вычислить количество очков бинпоиском по ответу участника. То есть, я даю на вход степень двойки и если побитовое И от ответа участника и степени двойки даёт эту степень двойки, то к ответу прибавляется эта степень двойки. Таким образом, за $$$64$$$ теста можно посчитать количество очков (да, чекер будет считать ответ $$$64$$$ раза). Собственно, это и реализовано по ссылке выше.
Видите ли вы в этом уязвимость? Конечно, ведь можно для каждого теста сообщать всё новый и новый ответ (новый лабиринт), зарабатывая степени двойки на различных лабиринтах (подгоняя ответ так, чтобы нужный бит был выставлен). К тому же, если возвращать WA, то пакет с задачей на полигоне не может быть собран, так как решение жюри обязано проходить все тесты. Разумеется, у меня нет лабиринтов тех, кто находится выше меня в топе, поэтому программа жюри не может пройти некоторые тесты на степень двойки.
Как же я собрал пакет? А просто заифал, что это решение жюри, и если это оно, то возвращал OK.
Также придётся иметь $$$64$$$ группы тестов и чтобы каждая группа проверялась независимо?
Ну и третья проблема: автор задачи в мэшапе видит все решения участников. Возможно, фиолетовые участники в режиме тренера тоже видят. Если вы отправите код, который генерит лабиринт на 1 млрд, то лично я будут его видеть и смогу использовать в корыстных целях... Но это решаемо, если бы мэшап создавал автор игры "Жук" или тот, у кого кредит доверия довольно высок.
Буду рад, если поможете решить первые две проблемы.
P.S. Оригинальный сайт buglab.ru не осиливает проверку огромных лабиринтов, а если сабмитить огромные лабиринты, то, похоже, что весь сайт виснет на продолжительное время. Насколько я понимаю, у текущего топ-1 лабиринт на $$$7.550.297.908$$$ и он не может его сабмитнуть. Интересно, осилит ли чекер такой лабиринт? У меня проверка делается влоб за $$$O(\text{кол-во ходов жука})$$$. Да, 7*10^9 действий в чекере.
