Соревнование Codeforces Marathon Round 1 закончено. Пока тестируются итоговые решения, думаю, многим участникам будет интересно поделиться своими идеями и узнать альтернативные подходы. Начну с идей, которые испробовал я — и успешных, и нет; по коду посылок видно, что у участников интересных идей больше, но, надеюсь, они сами их расскажут. У каждого решения ниже в квадратных скобках указаны минимальный, средний и максимальный баллы при тестировании на 1000 локальных тестов. Замечу сразу, что константы и технические детали в решениях не претендуют на оптимальность: баллы лишь отражают примерное соотношение идей и часто могут быть чуть улучшены. -----

Решение 1 [4099 4159.699 4288]: случайное.

Просто выведем 100 раз 5000 случайных битов.

Решение 2 [4160 4226.294 4365]: запоминание последнего бита.

Последний проверенный бит всегда неправильный. Например, если ответ на попытку — число 4050, значит, ровно на 4050-м бите нашей строки случилась 2000-я ошибка. Зафиксируем правильное значение этого бита. При генерации очередной случайной строки все зафиксированные биты имеют уже известные нам значения, остальные генерируются случайно.

Решение 3 [4182 4291.374 4453]: выяснение нескольких битов.

Это решение из двух частей. В первой части (90 попыток) попытки разделены на 45 пар. Первая попытка пары i генерируется случайно (кроме зафиксированных битов, которые нам уже известны). Вторая попытка пары i отличается только в i-м бите и в последнем проверенном бите.

Какую информацию мы можем получить из такой пары? Пусть, например, первая попытка дала результат 3980, а вторая (в ней поменялись бит 1 и бит 3980) — результат 3975. Значит, во-первых, бит 1 был правильным в первой попытке (раз она прошла дальше). Во-вторых, 2000-я ошибка во второй попытке — это 1999-я ошибка в первой, а значит, между 3975 и 3980 битами в наших попытках нет ни одной ошибки.

Аналогично, если результат второй попытки больше первой — например, 3981, - мы знаем, что бит 1 был правильным во второй попытке, а ещё что между 3980 и 3981 ошибок нет (в этот раз это нам ничем не помогло, потому что и битов между ними нет).

За пару попыток мы точно узнаём в среднем три бита.

Во второй части решения (оставшиеся 10 попыток) будем просто генерировать случайные строки, кроме зафиксированных битов, которых в среднем получилось 135 и становится на один больше после каждой попытки.

Решение 4 [4260 4369.927 4498]: симметричное выяснение нескольких битов.

Это решение из двух частей. В первой части (90 попыток) первая попытка делается случайно, а каждая следующая (i-я) меняет бит i и последний проверенный бит в предыдущей. Как и в решении 3, по тому, как изменился ответ, мы можем не только понять на будущее, каким должен быть бит i, но и узнать в среднем два бита в районе 4000. Однако теперь мы узнаём в среднем три бита за одну попытку, а не за пару. Заметим, что мы не можем выставлять первые 89 битов в правильные значения сразу, поэтому известные в конце биты распределены более симметрично вокруг 4000.

Во второй части решения (оставшиеся 10 попыток) будем просто генерировать случайные строки, кроме зафиксированных битов, которых в среднем получилось 267 и становится на один больше после каждой попытки.

На этом решения, выясняющие конкретные биты, у меня закончились. Судя по предварительной таблице, больше половины участников придумали кое-что получше. Полезная эвристика отсюда, которая может помочь в других решениях - всегда запоминать, что последний проверенный бит точно неправильный.

Решение 5 [4429 4533.129 4671]: инвертирование отрезков.

Разобъём наши 5000 битов на отрезки длины, например, 45. Для первой попытки сгенерируем случайную строку, а в каждой следующей попытке будем инвертировать очередной отрезок. После инвертирования мы, сравнив два числа, точно знаем, лучше было с инвертированием или без него; выберем наилучшее из двух положений и перейдём к следующей попытке.

Почему это вообще работает? Интуитивно — среднее отклонение на отрезке достаточно большое, значит, будет достаточно много отрезков, на которых инвертирование сильно меняет ответ: например, если на отрезке было 19 из 45 правильных битов, после инвертирования их становится 26. Если мы, наоборот, из 26 сделали 19 — вернём 26 (и предыдущий результат) на место.

Константа 45 подбиралась на глаз; кажется, большинству участников в каких-то похожих решениях больше понравилась константа 40.

Решение 6 [4399 4582.368 4723]: инвертирование отрезков с возобновлением.

Положим 4000 первых позиций битов в пул "настоящее", а оставшиеся 1000 позиций в пул "будущее". Для первой попытки, как обычно, сгенерируем случайную строку. Для каждой следующей попытки возьмём из пула "настоящее" 79 случайных битов и инвертируем их все. Если ответ изменился больше чем на 10 — значит, на этом "отрезке" есть достаточно большое отклонение. Воспользуемся этим: зафиксируем все эти 79 битов в лучшем из двух состояний (либо все оставим, либо все инвертируем обратно). В противном случае также выставим лучшее из двух состояний, но фиксировать биты не будем, а переложим их в пул "будущее".

Когда пул "настоящее" кончился, возьмём из пула "будущее" все биты, до которых мы хоть раз дошли (то есть бит 4999, скорее всего, не берём), сделаем из них новое "настоящее" и продолжим.

За счёт того, что мы переиспользуем биты, фиксирование которых не приносит большой выгоды, мы можем брать более длинные "отрезки": их длина 79 вместо 45 в решении 5. А значит, и среднее отклонение на "отрезках" будет больше.

Константы 79 и 10 подбирались небольшим перебором.

Решение 7 [4539 4702.079 4878]: инвертирование отрезков с возобновлением и запоминанием.

Будем делать то же, что в решении 6, но вспомним про идею из предыдущей серии решений: последний проверенный бит всегда неправильный. Выгода от применения этой идеи почти не зависит от выгоды от инвертирования больших отрезков.

В этой версии решения оказалось выгодно сделать отрезок ещё длиннее: константы 79 и 10 заменены на 99 и 18.

Решения с инвертированием отрезков на этом кончаются. Лучшее из них в предварительной таблице занимает 20-30 место. Слабые стороны этих решений в том, что мы меняем только малую часть строки, а значит, получаем в среднем мало битов информации. Ещё мы фиксируем раз и навсегда весь хороший отрезок. Что из этого и как можно улучшить — надеюсь, расскажут участники из топа.

Решение 8 [4251 4403.645 4594]: дискретное вероятностное в каждой позиции.

Сделаем 99 случайных попыток. Для каждой из 5000 позиций будем запоминать вероятные биты. Для каждой попытки с результатом хотя бы 4000 отметим её биты до последнего проверенного как вероятные на всех позициях, а для каждой попытки с результатом меньше 4000 — инвертируем её и отметим инвертированные биты до последнего проверенного как вероятные.

В последней попытке в каждой позиции выберем тот вариант, который больше раз оказался вероятным.

Решение 9 [4433 4601.678 4773]: вероятностное в каждой позиции с запоминанием.

Попробуем улучшить предыдущее решение.

Во-первых, вспомним про то, что последний проверенный бит всегда неправильный, и будем фиксировать такие биты.

Во-вторых, научимся использовать не только знак результата (условно — меньше ли он 4000), но и величину. Например, если 2000 ошибок как-то распределены по 4001 биту, это нужно учитывать с меньшим коэффициентом, чем когда те же 2000 ошибок распределены по 4100 битам.

С учётом зафиксированных битов каждая попытка даёт нам информацию вида "в t битах 1999 ошибок". В каждом из этих t битов запишем, что вероятность того, что он правильный, равна 1999 / t. В конце просто усредним все записи в каждом бите.

В последней попытке в каждой позиции выберем тот вариант, который оказался более вероятным.

Около трети участников реализовали что-то лучше, чем описанные решения, считающие вероятности отдельно в каждой позиции.

Ещё одна идея — полное инвертирование. Будем использовать попытки парами, вторая попытка пары — полная побитовая инверсия первой. Каждая такая пара попыток даёт информацию вида "на отрезке от lo до hi ровно err ошибок". Действительно, пусть первая попытка пары дала результат 4015, а вторая 3980. В сумме на отрезках [1, 3980] и [1, 4015] 4000 ошибок. Кроме того, в сумме от 1 до 3980 ровно 3980 ошибок: каждый бит побывал и нулём, и единицей ровно по одному разу. Значит, среди битов от 3981 до 4015 ошибок ровно 20.

С этими отрезками можно делать разные операции: пересекать их, искать строку, подходящую под всю известную информацию, если не получается — искать как можно лучше подходящую строку. Мои решения с такими отрезками получают средние результаты между 4400 и 4500, но уже технически нагружены. Наверняка можно сделать лучше.

Немного об истории задачи. Изначально она задумывалась как сложная неточная задача на соревнование по правилам ACM ICPC. План был такой: испробовать несколько подходов и посмотреть, отсекаются ли ограничениями простые и слабые от содержательных и сильных. Однако первые же несколько идей решения не пожелали выстроиться по результату в порядке, сколько-нибудь похожем на сложность их реализации, так что задачу пришлось отложить. С другой стороны, в соревнование с частичной оценкой такая задача хорошо вписывается, поскольку есть несколько совсем разных идей решения, придумать и реализовать которые достаточно легко.

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