Привет сообществу Codeforces! В этом посте я поделюсь с вами историей того, как я писал всеросс 2017. Вы погрузитесь в мир необычайно жутких багов и необычайно слабых тестов:) Рекомендую для лучшего понимания прочитать условия 5 и 8 задач всеросса (Накопитель и Траектория обучения) http://neerc.ifmo.ru/school/archive/2016-2017/ru-olymp-roi-2017-day2.pdf
Рассказ начну с того, что второй тур всеросса начался для меня не слишком удачно. Где-то около часа я безуспешно пытался решить первую задачу и запихал решение, которое заходит на 20 баллов и получает WA на след. группу, что свидетельствует о плохих тестах в первой группе (проблем с памятью у меня явно быть не могло). Я подумал, что первая подгруппа первой задачи мало волнует составителей, и решил не обращать на это внимание.
Потом вроде контест пошел получше, и за 1.5 часа до конца у меня уже было 200 баллов по первым двум задачам (как оказалось можно получить 100 баллов за первую и решить ее за квадрат при ограничениях до 10^6, но мы дойдем до этого:) ). В последний час я придумал, как решать 4-ую на 50, но вследствие казавшихся мне тогда сверхъестественными причин, я получал WA на 4-ой подгруппе, не проходя только 1 тест из подгруппы и проходя полностью 1, 2, 3 и 5 (т.е получая 30 баллов за первые 3; нельзя получить баллы за 5-ую подгруппу, не пройдя 4-ую). Это казалось мне очень странным, но я ничего не мог с этим поделать, и к концу тура у меня так и осталось 30 баллов по этой задаче. Покопавшись в коде дома и посмотрев тест, я обнаружил совершенно нелепый баг: в компараторе set-а я кидал в set отрезки и сравнивал их лишь по сумме на отрезке, не написав в компараторе, что нужно делать, если суммы окажутся равны; таким образом при удалении одного отрезка у меня по-видимому удалялись все отрезки с данной суммой на отрезке. (Код: https://pastebin.com/P6b425j8)
Однако это каким-то образом работало и не проходило лишь 1 (!) тест из 4-ой подгруппы. Я списал это на то, что составители тестов даже и не думали о том, что так можно набагать и тест, который не прошло моя программа, по-видимому, генерился рандомно, и мне не повезло (а может и повезло, иначе я бы не пополнил свой опыт ошибок) в том, что в этом рандомном тесте мой баг проявился. Я подумал, что на этом мои косяки в решенных задачах (и косяки авторов тестов) закончились.
Каково же было мое удивление, когда рассказывая свое решение первой задачи (Накопитель) второго дня другу, я обнаружил то, что причины, по которым я считал, что мое решение этой задачи работает за линию, на самом деле неверны, более того, я начал подозревать, что существует тест, на котором мое решение работает за квадрат. Мое решение было удивительно банальным в плане идеи (расскажу для случая когда строка t, которую нам нужно получить состоит из всех плюсов): перебираем отрезок из плюсов, и пытаемся расшириться от него влево или вправо, пока можем, с помощью цикла while (код: https://pastebin.com/nAw6uiBc). Немного поразмышляв, я и в самом деле придумал контртест, на котором моя программа работает 15 секунд уже на строке длиной 10^5 (оригинальные ограничения строки до 10^6). Тест этот устроен довольно просто: сначала делаем строку s такой: ++-++-++-++-.... и в конце приписываем отрезок из минусов с длиной, равной длиной нашей строки. Пример такой строки: ++-++-++----------
Довольно понятно, почему мое решение будет работать на таком тесте за квадрат: программа будет стараться расшириться от каждого отрезка из плюсов и будет делать это довольно успешно на первой половине строки, но превратить всю строку в плюсы никогда не сможет, при этом при каждом расширении будет затрачено порядка O (n) операций и расширений тоже будет O(n), т.е итоговая асимптотика = O(n^2). Эта оценка и подтвердилась на практике, я сгенерил этот тест на 10^6 и не смог дождаться, пока моя программа отработает; лишь уменьшив длину до 10^5 я увидел, что время выполнения на таком тесте — порядка 15 секунд. Очень странно, что подобный тест не был включен в комплект тестов, так как мое решение довольно банально и, по идее, члены жюри должны были придумать против него контртест.
Этим постом я не старался как-то принизить работу жюри олимпиады, я понимаю, что редко существуют тесты, которые заваливают все неверные решения разом. Да и мне грех жаловаться, ведь баллы в результате у меня только увеличились. Но хочется думать, что получив Accepted, ты и в самом деле решил задачу, а не просто послал решение, которое работает на всех тестах, которые придумали составители:)
