Всем привет!

Основное время Codeforces Marathon Round 2 закончилось. В предварительных результатах участники Rafbill и hakomo получили очень близкие баллы, но при этом достаточно сильно оторвались от следующей группы. Удастся ли им сохранить этот отрыв после итогового тестирования, и кто окажется выше? Это мы узнаем через несколько часов.

А пока предлагаю участникам поделиться идеями своих решений в комментариях ниже или в собственных постах. Начну с упоминания нескольких решений, которые я сам попробовал написать.

1. Одно из самых простых решений, стабильно получающих какие-то баллы, таково: будем двигать хамелеона 0 цветом d[0], хамелеона 1 цветом d[1], ..., хамелеона 9 цветом d[9], затем опять хамелеона 0 цветом d[10], и так далее до хамелеона 9, в которого мы швырнём баночку цвета d[9999]. Такое решение набирает 9719.44 балла на предварительных тестах, занимая ~250-е из ~275 мест с ненулевыми баллами.

2. Более разумное простое решение — жадность. Во-первых, будем всегда швырять баночку в хамелеона, который оказался последним. Будем симулировать происходящее и выбирать тот цвет, после которого этот последний хамелеон пройдёт дальше всего. Такое решение набирает уже 32096.7 баллов на предварительных тестах, занимая ~130-е место.

3. Одна из возможных следующих идей — копить какой-нибудь один цвет в руках, пока баночек этого цвета не станет хотя бы X (например, все 10). Остальными цветами действуем как в предыдущем жадном решении. После этого можно тратить баночки этого цвета, пока они не кончатся (вполне возможно, их в итоге окажется больше X). Кажется, что в этот момент хамелеоны движутся довольно быстро. Но проверка показывает, что это решение работает хуже жадности: например, при X = 10 оно получает всего 29269.37 баллов на предварительных тестах, занимая ~195-е место. Тем не менее, возможно, эта идея помогает в комбинации с другими?

4. Когда один из важных параметров в задаче — это время (например, номер хода от 0 до 9999), часто помогает Beam Search. Опишу вкратце эту технологию.

Вместо того, чтобы действовать всегда жадно, будем перебирать возможные ходы и в каждый момент времени хранить W (десятки, сотни, тысячи...) лучших состояний. Из каждого из состояний, сохранённых для момента t, будем делать один или несколько ходов разными способами и поддерживать W наилучших результатов для каждого из следующих моментов t + 1, t + 2, ..., до которых мы добрались.

Вот другой взгляд на Beam Search. Рассмотрим решение динамическим программированием, зависящее от момента t и состояния s. Конечно, состояний слишком много, поэтому будем хранить не все, а только те W состояний для каждого момента t, для которых получился наилучший ответ.

Чтобы воспользоваться этой технологией, нужно придумать, как оценивать конфигурации. Например, сначала по позиции последнего хамелеона, а при равенстве по сумме позиций всех хамелеонов. Кроме того, нужно придумать, как делаются локальные изменения: ходы для получения следующих состояний. Это может быть, например, один любой следующий ход, или сразу несколько ходов одним цветом.

Не очень сложное решение с применением Beam Search у меня получило 33508.39 баллов на предварительных тестах. Это всего лишь примерно 55-е место. Так что с интересом жду, что про задачу расскажут участники!

Напоследок хочу поблагодарить Наталью Гинзбург (naagi) и Андрея Лопатина (KOTEHOK) за помощь в подготовке задачи, а также Михаила Мирзаянова (MikeMirzayanov) за помощь с системами Codeforces и Polygon.

Дополнение. Прошло несколько раз по несколько часов, и мы наконец готовы объявить окончательные результаты! Вот первая десятка с несколькими числами: минимальные баллы (или количество пройденных тестов из тысячи), средние баллы (по ним определялись места), максимальные баллы.

• 41543 42432.939 43550 Rafbill
• 41327 42412.584 43332 hakomo
• (996) 41031.784 42175 teapotd
• 40103 40980.620 42016 yarrr
• (995) 40652.147 41887 UminchuR
• 39675 40620.653 41682 hatoo
• 39773 40617.445 41605 Coder
• 38899 40084.291 41186 Hoi_koro
• 38956 39935.629 41032 ts_
• 39057 39888.408 40944 MrDindows

Поздравляем победителей, и спасибо всем за участие!