Две простые задачки на волну

Александр Ипатов

Статья написана к четвертьфиналу чемпионата мира по программированию 2014 года

В 2004 году Чемпионат Урала, он же четвертьфинал, после четырёхлетнего путешествия вернулся в Екатеринбург. Программный комитет подготовил 2 тура по 10 задач. Уж не знаю почему, только в каждом из туров было несколько задач на волну (обход графа в ширину). Злые языки поговаривают, что это было сделано специально для того, чтобы у команд УрГУ было преимущество — ведь на наших локальных соревнованиях задачи на разные применения волны традиционно были почти в каждом комплекте.

В первом туре это были задачи "Погоня в метро" и "ПДВАС и ПВИПАС". Про первую особо нечего рассказывать. А вот вторая задача оказалась камнем преткновения для фаворитов соревнования из Пермского ГУ и Уфимского ГАТУ — они даже не сделали по ней ни одной попытки. В то время как две первые команды УрГУ, включая нашу, эту задачу сдали. После контеста Ден Расковалов написал на форуме, что пермяки проиграли нашей команде чисто тактически: стали решать гробовые задачи и "прохлопали, в результате, задачку на волну". В задаче стояло ограничение что-то типа N = 1500, мы написали, как нам тогда казалось, квадратичное решение, услышали на разборе такое же решение жюри и порадовались.

Через несколько лет, когда я занимался поддержкой архива задач на Тимусе, на эту задачу начали присылать новые тесты с просьбой добавить их. Я добавлял и перепроверял все решения; некоторые из тех авторов, чьё решение падало, сдавали задачу заново. Но в один прекрасный день мне прислали тест, который свалил почти все AC-решения по времени. Я стал разбираться, в чём дело, и выяснил, что алгоритм жюри (а по совместительству наш и почти всех авторов на Тимусе) работает на этом тесте за кубическое, а не квадратичное время. Когда я изучил те решения, которые успешно прошли этот тест, оказалось, что и они все тоже кубические. Поработав несколько дней, я сгенерировал тесты и против всех них. Итак, у нас теперь была задача, были тесты, но не было ни одного решения, которое бы проходило все эти тесты за допустимое время. Перебрав несколько эвристик и придумав несколько тестов против них, я понизил ограничения в задаче в несколько раз, удалил все большие старые тесты и сгенерировал тесты под новые ограничения. Сейчас эта задача действительно решается кубическим алгоритмом, который изначально предложили её авторы, хотя и более быстрое решение, конечно, тоже существует. В таком виде задача и осталась на Тимусе, если не считать того, что нам потом присылали и другие тесты против некоторых эвристик (наиболее преуспели в этом Роман Ризванов и Сергей Ведерников, в сумме свалившие более трёхсот AC-решений).

Во втором туре чемпионата Урала 2004 были такие задачу на волну: "Разбиение графа" и "Грязь".

Программный комитет подготовил на "Грязь" следующие решения: волну со сложностью N^2, Дейкстру на хипе со сложностью N^2*log(N) и волну со сложностью N^3 (а в задаче было N=500). Против третьего решения был тест, на котором оно работало 6-7 секунд на компьютерах жюри. Насколько знаю, изначально такое решение засчитывать не собирались. Но в последний момент выяснилось, что есть тест, на котором авторское решение за N^2 даёт неверный ответ (из-за того, что алгоритм в корне неверный!). Чтобы не заставлять участников обязательно писать Дейкстру (это бы сделало задачу существенно сложней, чем она изначально задумывалась), было принято решение засчитывать кубическую волну. На задачу выставили ограничение по времени (TL) в 20 секунд.

Что получилось? Ден Расковалов в самом начале контеста увидел эту задачу, сказал: "так это же простенькая задачка на волну!", написал кубическое решение (не помню уже, зная ли тогда о том, что оно кубическое, а не квадратичное) и сдал его с первой попытки на 13-й минуте соревнования. Это был первый Accepted нашей команды в тот день, при том, как выяснилось, это решение работало 18.5 секунд (то есть прошло аккурат в новый TL по задаче).

А вот как решала задачу команда УрГУ 1 (здесь я без исправлений цитирую рассказ Вовы Яковлева со старого форума contest.ur.ru):

"Кое-кто на 13-й минуте сдал, а мы на 298-й! Писать начали сразу. Первое решение, похоже, было правильным, но ловило TLE test#16. Подумали, решили делать всё по-другому, Серёга переделал своё решение (думаю, довольно сильно, если не полностью). Submit. WA test#22. Ещё несколько попыток, бросили задачу. Примерно через час от нечего делать (во как бывает!) я взялся писать эту задачу с нуля. 20 минут, WA test#22. Как так? Два независимых решения получают одинаковый вердикт! Сейчас понятно, алгоритм-то один и тот же. Бросаем задачу ещё раз. На этот раз совсем хороним. За 20 минут до конца опять же от нечего делать я решил переделать алгоритм. Сел, написал. Не работает. Я пустил Серёгу добивать H. Минут через 10 напечатали. (Тут ошибка, надо было сразу печатать.) Нашёл ошибку, исправил, послал, AC (за 2 минуты до конца!). Ладно хоть так кончилось :)"

После контеста обсуждение задачи продолжилось. Оказалось, на контесте жюри пропускало одни кубические решения и заваливало другие. Против авторского кубического решения и решений большинства команд были придуманы тесты, на которых эти решения работали не 6 и не 20 секунд, а что-то ближе к минуте. Против всех тех квадратичных решений волной, что предлагались авторами в качестве альтернативных, были придуманы тесты, на которых они давали неверный ответ. Наконец, было найдено правильное квадратичное решение волной (говорят, что кто-то из участников решал так задачу на контесте). На Тимусе были добавлены новые тесты и уменьшен Time Limit, чтобы отныне проходило только такое решение и решение Дейкстрой.

Добавлю, что, поскольку в задачах Чемпионата Урала 2004 не было "критических" ошибок (ошибок в чекерах и тестах, которые мешали бы сдать задачу), так же как и не было перепроверок решений по ходу контеста, у участников того соревнования осталось не слишком много негатива по отношению к программному комитету. Хоть итоговые результаты соревнования и стали во многом следствием везения, а не умения отдельных команд, выяснились все эти факты уже только тогда, когда соревнование завершилось.