Блог пользователя MikeMirzayanov

Автор MikeMirzayanov, история, 8 лет назад, По-русски

По всей России идет первый тур олимпиады. Болеем за ребят! Напоминаю, что что-либо спойлерить до окончания нельзя.

Интересно, в каких областях как проводят? Почти все на Яндекс-Контесте? Как впечатления?

Саратов проводит на отдельном интерфейсе для Codeforces, выглядит так:

  • Проголосовать: нравится
  • +75
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Во сколько официально будет можно спойлерить?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Вроде в 10:00 МСК все должны были начать. То есть в 15:00 МСК тур закончится. Видимо надо закладывать +epsilon.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Включая Калининград?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        Да

        каждый тур может начинаться только в интервале от 5.00 до 10.00 по московскому времени.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

А где есть рез-ты каких-нибудь регионов?

»
8 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

В прошлом году был гуглдок с результатами. Кто-нибудь сделает такой же?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как решать D быстрее, чем за ?

Я сначала сканлайном находил go[i] — до какой максимальной станции можно добраться от станции i, купив один билет. Потом считал jump[i] — до какой максимальной станции можно добраться от станции i, купив билетов.

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +15 Проголосовать: не нравится

    У меня то же самое, только я считал dp[i][j] — до какой максимальной станции можно добраться от станции j купив 2^i билетов. Предподсчет за O(nlogn), ответ на запрос за O(logn)

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится

    Заметим, что нам каждый раз выгодно занять место, с которого нас не выгоняет дольше всего. По считаем для каждой позиции go[i] — оптимальный переход из i.

    Затем насчитаем двоичные подъемы на этом массиве: go[i][j] — где мы окажемся, если стоим в i и сделаем 2j шагов. Теперь ответ можно искать, как ищут lca: прыгать на максимальную степень двойки, так чтобы оказаться левеех места, куда надо прийти.

    х Upd: опередили

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Можно использовать двоичные подъёмы. jump[i][d] — как далеко можно проехать со станции i за 2^d билетов.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится

    Можно set объединять с ранговой эвристикой за n * log^2n. В sete хранить запросы, также надо потдерживать прибавление еденицы всем элементам сета.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +37 Проголосовать: не нравится
»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

Таблица Питера https://yadi.sk/i/WMgtg12Vnzqfi (самодельная от geranazavr555)

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Условия задач: https://yadi.sk/i/BzmYeoDHnzs4o

»
8 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Планируется ли оглашение результатов первого тура в саратовской области?

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится +11 Проголосовать: не нравится

Условия и тесты скачал с локалки школы и выложил на Google Drive(около 50 МБ). Выкладываю через телефон, возможно что-то забыл, но, кажется, всё что есть в Ханты-Мансийске на локалке я выложил. (Обновлено). Добавлен PDF файл с заданиями первого и второго тура, ссылка та же. Обновлено, PDF файл был создан с домашнего ноутбука и загружен вместо первоначального, у предыдущего местами контент поехал.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Кто нить знает — кто создал задачи этой олимпиады ?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В Новосибирске проходило на тестирующей системе НГУ: https://olympic.nsu.ru/nsuts-new/login.cgi