Телеграм канал «Yandex Cup»

✳️ Привет из Японии — от maroonrk! Рику Кавасаки aka maroonrk — известный японский спортивный программист, золотой медалист IOI и ICPC World, финалист Yandex Cup 2024. Рику с теплом вспоминает прошлогодний финал в Ташкенте и ждёт старта нового чемпионата. Посоревноваться с ним можно будет в направлении Алгоритм. Звёзды спортивного программирования — в Стамбуле на финале Yandex Cup. Успейте зарегистрироваться до 29 октября: yandex.ru/cup 🟥🟥🟥🟥🟥🟥🟥🟥 ✳️ Greetings from Japan, from maroonrk! Riku Kawasaki aka maroonrk is a renowned Japanese competitive programmer, gold medalist of IOI and ICPC World, and a Yandex Cup 2024 finalist. Riku warmly recalls last year’s final in Tashkent and is looking forward to the new championship. Enter the Algorithm category to compete with him. Stars of competitive programming will gather in Istanbul for the Yandex Cup final. Register till October 29: yandex.ru/cup

Стрим Юниоры: успех Лёши Колегова Сначала Лёша прошёл в финал, а затем стал победителем в направлении Аналитика. Год назад на Yandex Cup в Ташкенте. В финале я был счастлив, что достиг этого своими силами. +100 к мотивации! Запомнились люди — организаторы и участники, без них ничего бы не было. Плейстейшены тоже были очень крутые. Понравилось, как были составлены задания. Решал, и мне казалось, что я распутываю загадки и копаю до истины. Я сильно вовлёкся в процесс. На Yandex Cup уже зарегался, с нетерпением жду новых задач! Читайте впечатления Лёши от финала и регистрируйтесь на Yandex Cup: yandex.ru/cup Check the English version in comments ⬇️

✳️ На связи Максим Спорышев, руководитель ML-направления Yandex Cup Максим руководит службой поведения и предсказания в департаменте Автономного транспорта и желает вам успешно стартовать в квалификации по ML. Напомним, что все вопросы по задачам, нужно задавать через сообщения в контесте Ждём ваших решений до 5 ноября: yandex.ru/cup 🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥 ✳️ Here's Maksim Sporyshev, Machine Learning Category Leader at Yandex Cup Maxim heads the Behavior and Prediction Team at the Department of Autonomous Transport and wishes you a successful start in the ML qualification. We remind you that all questions about problems should be asked through messages in the contest We are waiting for your solutions until November 5th: yandex.ru/cup

✳️ ML-квалификация стартовала Квалификационный раунд ML-направления стартовал и будет доступен до 23:59 5 ноября. В этот период можно приступать к решению в удобное для себя время. Список финалистов объявим до 10 ноября. Команда ML-направления составила и отобрала для вас самые интересные задачи: — Генерация картинок видеосенсора для автономного автомобиля — Ответы на вопросы к чертежам для задач по физике и математике — Устойчивость к галлюцинациям в больших языковых моделях Регистрируйтесь и приступайте к решению: yandex.ru/cup 🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥 ✳️ ML qualification started today The ML qualification round started and will last until 23:59 on November 5. During this period, you can start at a convenient time. The list of finalists will be announced by November 10. The ML team has compiled and selected the most interesting problems for you: — large language models hallucinations robustness — autonomous driving camera sensor image generation — stem problem illustrations Q&A with VLMs Haven’t registered yet? There’s still time: yandex.ru/cup

💜😁 Прогулялись по офисам — раздали стиля и окунулись в стамбульский вайб Ждём старта чемпионата всем Яндексом! Регаемся, регаемся, регаемся: yandex.ru/cup 🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥 💜😁 Shared some style and Istanbul vibe The championship is coming soon. Join us: yandex.ru/cup

✳️ Условие Есть некоторый набор данных вида ключ-значение. Все данные изначально создаются в главной базе, после чего вам необходимо переместить их в одну или несколько кеширующих реплик — на один и тот же ключ в главную базу данных должно быть не более одного запроса. Обращаться к базам можно по HTTP-интерфейсу, который состоит из двух эндпоинтов GET и PUT. Реплики должны быть сбалансированы, иначе они не смогут вместить всю информацию. Не более одного раза одна из кеширующих реплик может выйти из строя, в таком случае она начнёт всегда отвечать HTTP-кодом 502. Вам необходимо реализовать алгоритм, который сможет распределять данные и определять их местонахождение с учётом возможного отключения одной из реплик. Проверяющая система может эмулировать отказ, в том числе приложения участника. После отказа приложение участника перезапускается автоматически с самого начала. Это может произойти строго только между получением ответа от участника и отправкой очередной команды. Формат ввода Вам предоставляется конфигурационный файл с URL базы данных и серверов-реплик — путь до файла передается в качестве первого параметра командной строки в решение участника. Конфигурационный файл имеет следующий формат: { "db_url": "http://db_host:db_port/some_path/", "cache_urls": [ "http://cache1_host:cache1_port/some_path/", "http://cache2_host:cache2_port/some_other_path/", ... ] } Количество серверов-реплик может быть от 2-х до 10. На вход программе через stdin по одному передаются ключи. В ответ на каждый ключ, полученный из stdin ожидается запись значения для этого ключа в stdout в виде строки. ✳️ Ключевая идея На самом деле задача сводится к тому, что у нас есть api некоторого бэкенда над key-value хранилищем, и нам надо реализовать распределённый кэш. Распределённость требуется по трём причинам: 1) Все данные не влезут на одну реплику 2) Одна случайная реплика может отключиться в процессе работы 3) Наше приложение тоже может перезапуститься, поэтому в памяти данные держать не получится Важные детали реализации Самая важная часть решения — придумать, как распределять данные по репликам, чтобы переживать отказ и равномерно распределять данные по ним. Доступность данных: По условию задачи, отключаться в процессе работы может только одна реплика. Поэтому лучшим вариантом будет хранить каждый ключ на хотя бы двух, чтобы при выходе из строя какой-то реплики у нас всегда был резерв. ✳️ Равномерность распределения По сути - нам нужна функция, которая на оcнове ключа будет выбирать две реплики и делать это равномерно. Давайте возьмём функцию хеширования h(x). Пусть у нас есть N реплик, тогда две реплики можно выбрать так: 1) h(key) % N 2) (h(key) / N) % N Если функция хеширования достаточно хорошая, то распределение будет равномерным Более того: такой подход к решению задачи позволит нам по ключу стабильно определять на каких репликах он может быть и нам не придётся нигде хранить эту информацию. Для нас это тоже важно, так как по требованиям мы должны уметь переживать перезапуск нашей программы. ✳️ Собираем воедино Давайте посмотрим, как с учётом всех идей будет выглядеть решение: Шаг 1: Читаем json-файл, в котором лежат url базы и реплик Шаг 2: Запускаем цикл, который будет читать ключи из stdin Шаг 3: Считываем очередной ключ Шаг 4: Вычисляем h(key) и определяем две реплики, на которых могут быть данные Шаг 5: Пробуем прочитать данные с реплик: делаем параллельно два HTTP GET запроса в выбранные реплики. Если данные пришли хотя бы с одной — пишем их в stdout и переходим к шагу 3 Шаг 6: Если на репликах данных нет — значит такого ключа ещё раньше не было. Делаем HTTP GET запрос в сервис-базу, чтобы получить значение Шаг 7: Важно! Прежде чем выводить его в ответ - надо записать значение на реплики. Делаем два HTTP PUT запроса в выбранные реплики и только после этого выводим ответ в stdout и переходим к шагу 3 Почему в 7 шаге важно делать именно в таком порядке: потому что по условию задачи есть гарантия, что перезапуск нашей программы может произойти только после вывода в stdout ➡️Регистрация: yandex.ru/cup