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

Автор Rubanenko, 12 лет назад, По-русски

Завтра, в 12.00 по Москве, начинается сезон мною очень любимых личных олимпиад на neerc.ifmo.ru/school! Не забудьте заново зарегистрироваться. Всем желаю удачи!

Разумеется, предлагаю после контеста здесь же обсудить задачи.

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

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

feedback'и будут?

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

    Думаю, что нет. Они обычно появляются на контестах перед Всероссом, а в преддверии регионального этапа их нету.

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

У кого-то фидбэк пашет? У меня просто пишет "Unknown, Scored".

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

Монитора и не предполагается?

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

в первой задаче "любое" == каждое или хотя бы один?

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

    Думаю, что каждое.

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

      это уныло, так писать условия =/

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

        да вроде понятно...

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

          слово "любое" можно понять двусмысленно.

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

            ну да, лучше было написать "каждое"

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

              да, голубчик, намного лучше.

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

            Слово "любое" абсолютно понятно, не нужно придумывать ему второй смысл.

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

              К сожалению, слово "любой" несет в русском языке одновременно два противоположных смысла. Например, в словаре Lingvo:

              Любой
              ...
              II. Какой угодно (на выбор).
              III. Каждый из себе подобных; всякий.

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

        Для меня, конечно, русский не родной, но думаю, что "любой"=="каждый".

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

          Контрпример: "если оптимальных ответов несколько, выведите любой".

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

    У меня времени на прочтение задачи, ушло больше чем на решение;)

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

    Я вот тоже к сожалению понял, что хотя бы одно, причем даже не задумался над этим

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

Интересно получилось у меня: два жадника и два двоичных подъема:) Хотя на третью есть решение за N+М, я писал тупое N log N+M log M.

Больше всего за первую боюсь:) Там же выгодно либо за 1 штуку платить, либо только за 2 максимальных, да?

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

    Вроде да. Я боюсь за heavy-light в D :)

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

      Я делал фенвиком. Типа как на емаксе написано про покраску ребер. Хэви-лайт — для такого количества вершин и запросов слегка сурово, хотя может они поэтому такой ТЛ/МЛ и поставили.

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

    Да.

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

    у меня такой же расклад) в первой да, если максимальные в одном элементе — за одну, а если в двух, то либо сначала первый, затем второй либо наоборот, и лонги надо не забыть, вроде это верно

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

Ололо, я правильно понимаю, что засчитывалось последнее решение, даже если ты вручную выбрал засчитывать другое? :D

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

Вторая задача....втф?!

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

А где можно увидеть результаты?

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

Тот неловкий момент, когда ты забываешь поставить used и твое решение вместо 100 получает 2..

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

    Я писал хешсет на вторую руками. Для пары (x,y) брал хеш-функцию, как их произведение. Почему-то долго работает... Поменял, и прошло :(

    В общем, я тебя понимаю.

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

      Хеш-фунция равная произведению числителя на знаменатель падала по ТЛ? А можешь код показать? У нее же коллизий быть в принципе не может (если дробь несократимая, а знаменатель — степень двойки)...

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

        У меня шех-функция (x*13+y), т.к я испугался, что произведение за long long выйдет. Тоже упало. Наверное, потому что куб :D

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

          Ну куб заходить и не должен, авторское решение N^2 logN — оно хранит точки в TreeSet'e, и не беспокоится по поводу коллизий :)

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

        Вот...

        Код корявый, но найти должен :)

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

          А... Ну так ты умножаешь на степень двойки (которая в знаменателе), а потом берешь по модулю 2 в степени 22. Понятно, что коллизий будет много. Если бы модуль был бы простым, то работало значительно быстрее.

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

            Спасибо, что помог разобраться. Я всегда беру по такому модулю, чтобы не использовать остаток... Соптимизировал, называется..:)

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

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

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

        Там даже если поставить h=(x+1)*(y+1), то проходит. Получается, что нулей много... Хз откуда они берутся.

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

    у меня тоже такая ситуация

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

Ребята, какая главная идея в решении А ?

UPD Извиняюсь, перечитал условие и понял, что все было раз в 500 проще...

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

    Очевидно, что число равное максимуму по первому параметру мы заплатим, ведь никуда мы от него не денемся. Это же утверждение верно и для второго параметра. Зато после этого по каждому параметру уже платить не придется. Если максимум и там, и там лежит в одном задании, то его делаем первым, за остальное не платим. Иначе смотрим как нам выгодно — макс по первому, а потом по второму, или наоборот.

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

У кого есть права, залейте пожалуйста в тренировки.

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

Вопрос по задаче С. Правильное ли такое решение за n+m: читаем все запросы. Для каждой вершины сделаем список запросов, на которые нужно ответить, чтобы эта вершина была r(то есть в нее нужно попасть). Подвесим дерево за первую вершину. Для запросов, где l не является предком r ответ очевиден: первый предок l. Теперь для запросов, где l выше r: запустим дфс, для каждой вершины в массиве cur будем хранить вершину, в которую мы пошли из нее при обходе. Теперь если мы находимся в какой-то вершине, пройдемся по всем запросам для этой вершины и ответом на очередной запрос будет cur[l]. То есть идея такая, что мы запоминаем в какое поддерево идем и оно и будет ответом. Вроде понятно объяснил но правильно ли(:

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

    Да, конечно правильно. напоминает алгоритм Тарьяна. Я минут 10 думал над красивым решением, но потом сел двоичный подъем писать. Пока писал, в голову это пришло, но решил не изобретать велосипед.

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

Соревнование добавлено в тренировки. Удачи в дорешивании!

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

    Спасибо!

    На вторую 6 секунд поставил, чтобы у меня хотя бы тут прошло?:)

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

      Там авторские решение достаточно медленные

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

        А почему во вкладке "Задачи" в тренировке для второй и четвертой задачи ТЛ показывает 6с и 10с, хотя, если послать решение, то тл оно получает за 2с и за 6с соответственно?

        Кстати, авторское во второй работает меньше секунды...

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

    А почему на D -256 Мб а не 512?

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

На нашем с We.Pepsi.Infi сайте опубликован разбор. http://algorus.blogspot.ru/2012/12/2012-2013.html

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

Кто-то может скинуть ссылку конкретно на страницу регистрации в олимпиаде?