Ага, сдалось.

Ну вот с сортом, в итоге, сдалось: http://pastie.org/2705652

Круто! Спасибо.
Нам не хватило осознания того факта, что можно округлить.

У меня тоже 800 (на 20 тестах жюри 699–808).

Идея примерно такая же. Будем генерировать случайные лабиринты по алгоритму и сортировать их по расстоянию до цели.

Как только лабиринтов стало много (скажем, 10000), берём тот из них, до которого расстояние минимально, и проходим его (естественно, сдвигаясь так же во всех остальных и во всех будущих лабиринтах). После этого догенерируем ещё лабиринтов так, чтобы у нас висело 10000 непройденных, и опять пройдём тот, который быстрее всего пройти. Будем повторять, пока не кончится длина ответа. Это уже где-то 1000–1100 штрафа.

Улучшение: при равенстве расстояний (а после первых нескольких лабиринтов минимальное расстояние будет почти всегда 1, и будут сотни лабиринтов на таком расстоянии) выбираем шаг в ту сторону, в которую лабиринтов за этот шаг пройдётся больше. Это важно: сразу становится 700–800 штрафа.

Ещё нужно, чтобы генератор работал быстро (например, в поиске двух наиболее удалённых клеток притворимся, что граф — дерево), так как с такими константами генерируются миллионы лабиринтов, а длина ответа всё не становится 10000.

Константы (размер поддерживаемого множества и желаемую длину ответа) можно подкрутить так, чтобы и работало минут 5–10, и штраф был 800–900.

Ещё я пробовал генетический алгоритм, который строит ответ по маленьким кусочкам длины 100 (здесь и далее в решении все константы взяты с потолка). Для каждого кусочка сгенерируем 1000 лабиринтов и будем оценивать ответы по тому, сколько из них пройдено. Популяция — 100 путей, сначала просто пишем случайные буквы. Скрещивание — начало и 50 от одного + 50 от другого, мутация — какие-то символы ответа заменить на прохождение с этого места какого-нибудь лабиринта. Сгенерировали несколько поколений, 100 лучших кусочков зафиксировали как начала путей и с ними аналогично строим 101..200 символы ответа, и так далее.

Правда, этот алгоритм часа за полтора с трудом добивается штрафа 830–960, но в реализации есть что улучшить.

Да. Это ведь обычный meet in the middle.

Есть подозрение, что у нас тормозил вовсе не поиск (который хоть и двоичный поиск, но всего с 1-2 промахами кеша), а умножение многочленов по модулю. Но это фиг поймёшь - на нашем компе на 500 кейсах работало полсекунды, но он 1) 64-битный, 2) с большим кешом.

А можешь рассказать?

Можно еще рекурсивно.
Если текущий символ (обозначим его с) - плюс или минус, вызовем функцию еще 2 раза подряд (т.е. для операндов этого оператора) - получим строки s и t, и возвратим s + t + c.
Иначе возвращаем c.