Hi! When the final testing results are going to be published?

Also I really wonder what were the solutions that reach 8500+ on current standings. Could someone share one of those ideas, please?

Out of curiosity, one more question regarding the real-world application inspiration of the problem statement. I understand that it would make sense for robots to follow some kind of a repeating list of sites — to save memory, for example. However, why do robots' paths have to be cycles in the links graph and not just a repeating list of any sites, not necessary connected in a cycle?

If I didn't miss anything you can see your final score in your last submission before results will be published

Общая схема

Для начала заметим, что в 1/8 случаев робот всего один, поэтому научиться генерировать хотя бы один хороший цикл всё равно придётся. После того, как это сделано, оказывается, что неплохо работает Hill Climbing, на каждом шаге пытающийся обновить ответ, заменив произвольный цикл на случайно сгенерированный. Кроме этого, оказывается, что более сложные подходы, например отжиг вместо HC или попытка как-то достраивать имеющееся решение, работают плохо.

Генерация циклов

Это основная часть решения. От качества эвристики при генерации циклов зависит практически всё (скорость генерации и оценивания имеет гораздо меньший эффект, например). На среднего размера тесте HC у меня делает пару десятков обновлений ответа на несколько десятков тысяч итераций, т.е. мы ищем иголку в стоге сена, и направленность поиска предельно важна.

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

Цикл можно генерировать так: стартовав из случайной вершины, каждый раз переходить жадно в лучшую по набору параметров. Получится путь, из которого потом можно выбрать две случайных вершины u и v, взяв в ответ подпуть от u до v, если есть ссылка . Если её нет, можно выбрать другие случайные вершины. Необязательно делать так, чтобы u совпадала с началом пути. Одной и той же вершине можно запрещать появляться в пути дважды, а можно не запрещать. Это практически не влияет на результат.

Теперь об упомянутом "наборе параметров".

• Путь нужно ограничивать по глубине каким-то небольшим числом, возможно, зависящим от количества тем в тесте.
• Для начала заметим, что хорошая идея — идти жадно в сайт s с минимальным значением либо какой-то другой функции, возрастающей по indexingTime и убывающей по prob. Это даёт примерно 7700 очков.
• Но всё время так делать нельзя, поскольку может оказаться, что робот индексирует новости по одним и тем же темам, которым повезло оказаться на хороших сайтах, когда на самом деле иногда нужно заходить и на плохие сайты за редкими темами. Здесь помогает просто поддерживание набора тем, которые ещё ни разу не индексировались. При этом не рассматриваются сайты, которые не увеличивают этот набор (пока он не состоит из всех тем). С этой эвристикой получаем уже 8200.
• Предыдущее замечание можно сделать более количественным. Запомним для каждой темы, когда она индексировалась последний раз с точки зрения текущего пути, и разобьём оценку сайта на две составляющие — одна собственно о сайте (статическая, независящая от пути), другая о темах на нём (динамическая), и будем их комбинировать. Для динамической также полезно заметить, что какие-то темы есть на большом количестве сайтов, а какие-то — нет. Для этого можно посмотреть в код генератора, например. С такой эвристикой можно набрать около 8500. Ещё 150 очков добираются подкручиванием параметров и выбором различных монотонных функций вместо линейных.

Оценка решения

Лучше всего работает метод Монте-Карло, т.е. переписывание кода из чекера.

• Вместо того, чтобы каждый раз заново генерировать новости, это можно сделать в самом начале один раз, раскидав все новостные события по их сайтам.
• Код из условия можно существенно ускорить, переписав всё на связные списки. Итоговая сложность получается линейной по количеству событий и времени симуляции.
• Как ни странно, с временем симуляции тоже лучше не играться, а брать именно то, которое дано в тесте.
• Лучшее решение согласно этой функции оценки может оказаться в итоге не лучшим, т.к. в итоговой симуляции новости разлетятся по сайтам по-другому. С этим ничего не поделаешь, и остаётся надеяться на лучший в среднем результат. Повторение симуляции с разными распределениями новостей не помогает, попытка увеличить приоритет для сайтов с большими вероятностями, чтобы меньше зависеть от этого фактора, тоже не помогает.

Что ещё не работает

Вот ещё несколько идей, которые мне не удалось использовать для улучшения счёта.

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