https://www.wincentdragonbyte.com/archive/finals2026/I/statement
Прикольная оптимизационная задача. Вам даны две колоды карт с различными числами от 1 до 1000. Вы играете в пьяницу. Каждый раз, когда кладете очередные две карты вниз колоды, можно выбрать в каком порядке их положить. Нужно выбирать так, чтобы игра закончилась как можно быстрее. Дано 1000 тестов, и скор зависит от максимальной длины ответа. Если все ответы меньше 7500 действий — полный балл. Если есть хотя бы один ответ длиннее 175000, то 0 баллов.
Во время контеста большинство участников, которые отправили эту задачу, получили скор в районе 40-50 баллов. Максимальный скор был 60.83. Расскажу как можно получить 70 баллов стандартными средствами вообще не думая про суть задачи.
Для начала напишем простой эмулятор игры, который кладет все время большую из двух карт наверх. На некоторых тестах он уже работает очень хорошо. А на некоторых делает сотни тысяч действий, поэтому такое решение набирает 0 баллов. Если класть меньшую карту наверх, то почему-то игра вообще никогда не заканчивается.
Давайте в 99% случаев класть большую карту, а в 1% меньшую. Такое решение проходит какие-то тесты, но не проходит другие. Давайте для каждого теста будем перебирать
randseed пока не найдем такой, который решает тест за 30000 операций. Такое решение я написал на контесте и получил ~55 баллов.Давайте опустим границу до 23000 операций. Придется подождать чуть дольше, возможно распараллелить как в предыдущем посте, но так можно получить уже ~64 балла.
Воспользуемся стандартным трюком из оптимизационных контестов. Запишем последовательность наших действий как строку из 0 и 1. Поменяем случайную позицию. Если это привело к лучшему решению, то сохраним, иначе отменим. Будем так делать пока не придем в ситуацию, где никакое изменение не помогает. Если действий стало меньше 19000 — отлично, иначе попробуем с другого
randseed. Немного подождем и у нас 70 баллов!