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

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

Довольно странно, что никто не создал пост для обсуждения. Сейчас заканчивается мартовский раунд USACO 2012. Желающие еще могут начать участие в течениие целых 18.5 часов. Предлагаю после окончания обсуждать тут задачи.

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

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

silver div::->как решать Problem 2: Flowerpot ?

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

    Я условия не знаю, в Gold были задачи Large Banner, Haybale Restacking, Cows in a Skyscraper. И, да, формально еще кто-то мог начать писать в 16:00 по Москве, поэтому начало обсуждения лучше перенести на 19:00.

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

    Если это та про цветы, то в голову приходит только максимальный поток минимальной стоимости. Но учитывая, что N до 100 и дивизион — silver, скорее всего какая-то жадность должна быть.
    Все-таки не та про цветы, я про Landscape подумал.

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

    Решать двумя указателями. Сделать сжатие координат по икс. Далее для каждого икса выписать максимальный и минимальный игрек. Далее перебираем начало отрезка ответа, а конец подбираем указателем. Чтобы быстро проверять, можно двигать указатель или нет, нужно хранить сет текущих игреков.

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

Правильно ли я понимаю, что в Large Banner трудно придумать чего-то красивее свёртки Мёбиуса?

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

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

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

      Некоторое мясо через одно место.

      Во-первых, ответ есть произведение по всем взаимно простым парам величины (m + 1 - x)(n + 1 - y). До этого все, наверное, дошли.

      Во-вторых, введём функцию F(r), которая есть ответ только с верхним ограничением на длину |(x, y)| ≤ R. Тогда ответ на нашу задачу — F(r) — F(l — \eps ).

      В-третьих, введём функцию G(r), которая даёт нам ответ, в котором мы разрешаем не взаимно-простые координаты. Заметим, что в G(r) входят те вектора, у которых gcd равен единице, двойке, ... — всем возможным числам от 1 до \floor r. Значит G(r) = F(r / 1) + F(r / 2) + ....

      Функцию G(x) мы умеем считать быстро — за O(n). А значение функции F(x) восстанавливается через G через свёртку Мёбиуса.

      Но это онани^W жесть, которая вряд ли предполагалась как решение. Кто знает что круче?

      PS: извиняюсь за отсутствие латеха, у меня упорно формулы со второй вылезает Unable to parse markup.

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

    Расшифруй, о, Математик! UPD: прочитал выше

    Я прооптимизировал тупое решение. Для этого надо быстро научиться считать сумму и количество чисел x<=N, взаимно простых с y. Делается тупо формулой включений-исключений.

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

      Я, в свою очередь, это не научился делать. Я написал вот этот треш. Как же ты считал количество и сумму чисел, взаимно простых с y, ограниченных сверху?

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

        Что такое количество чисел, взаимно простых с y? Пусть y = p1k1 (здесь и ниже pi — простые). Тогда это все числа, минут те, которые делятся на p1. Пусть y = p1k1·p2k2. Тогда это все числа, минус те, которые делятся на p1, минус те, которые делятся на p2, плюс те, которые делятся на p1·p2. И так далее — по формуле включений-исключений

        Так как простых делителей у нас немного (y достаточно маленький) — порядка шести-восьми, то можно написать за 2k. И нетрудно заметить, что сумма от количества ничем не отличается, если мы умеем считать и то, и другое для запроса вида "сумма/количество чисел от 1 до y, которые делятся на α.

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

          Окей. Что-то я не могу понять, почему я не стал разивавать эту идею, вроде всё прямолинейно.

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

          Так это решение работает за O(NlogN) и, я думаю, является авторским. Мало того, если хранить только те делители, от которых функция Мебиуса не равна 0, то константа будет вообще маленькая.

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

          не туда

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

Кто как решал задачу Cows in a Skyscraper в золотом диве? Тупое решение за 3n, запущенное на сервере, получило совсем TL.

UPD: хочется услышать либо совсем клёвые оптимайзы, либо асимптотически лучшее решение.

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

    Можно соптимизировать в 2 раза. На асимптотику не влияет, но по времени работы заметно: когда перебираем подмаски невзятых коров сразу берем самую первую единицу и перебираем в 2 раза меньше подмасок.

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

    Да ну? Я когда отсылал, сымитировал на сэмпл-тесте тест из 18 чисел, у меня не затлилось. Сколько у тебя локально работает?

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

      Без оптимайзов — около 1 секунды. Там сервер небыстрый.

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

        > real 0m0.996s

        хмм.

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

          А ты на сервере тестировал с вбитым в код тестом?

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

            Ага, я отсылал.

            Сейчас пойду проверю, не померещилось ли мне.

            UPD: Я один не могу залогиниться? Выдаёт ошибку Access Denied красным цветом. Не помню такого раньше, вроде раньше после контеста всегда можно было.

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

              Попробуй тест с W = 108 и рандомными весами до 5·107. Ответ должен получиться порядка 4-6.

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

              У меня залогиниться получилось

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

                wtf. Пойду колстаду кто там сейчас начальник напишу.

                В общем, у меня на таком тесте вот секунду и работает как раз.

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

        Без оптимайзов — около 1 секунды. Там сервер небыстрый.

        Inter 3GHz, Linux. Там решения, работающие на локальной машине 2-3 сек, там "летают".

        Вот...

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

    У меня локально под виндой работало около 1,5 сек.

    Оптимайзил так: если можно взять всю маску, то брал ее, если переход — убрать одну корову, то не делал его. Так отсекается много состояний.

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

Кто что на 2ю писал? Лучше квадрата не придумал.

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

    Научимся решать задачу для линии. Заметим, что если не делать лишних действий, то всё однозначно. Как заметить: уберём сложную операцию, добавим простую "переложить из одной в соседнюю" ценой 1. Ничего не поменялось. Теперь посмотрим на самую левую кучку. В/из неё надо переложить понятно сколько. Переложили, убрали. Аналогично с остатком. Получается формула вида |c1| + |c1 + c2| + ... (где ci = bi - ai)

    Теперь тупой вариант для кольца: перебираем, сколько переложили в/из первой в последнюю. Пересчитали ашки, прорелаксировали ответ. Наблюдение: по сути, мы перебираем, на сколько "сдвинуть" a1 (последнее слагаемое всегда ноль, потому что суммы равны). Теперь заметим, что оно одинаково влияет на все слагаемые и тут прекрасно сработает троичный поиск (aka бинпоиск по производной).

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

      Интересно, прочитал здесь уже 2 разных решения. У меня вообще третье :) Задача сводится к тому, чтобы научиться обрабатывать запросы трех типов:

      • Прибавить ко всем числам что-то.
      • Изменить одно число.
      • Посчитать сумму модулей всех чисел.

      Можно завести двоичное дерево поиска, в котором хранить числа в отсортированном порядке. Тогда чтобы посчитать сумму модулей, достаточно просплитить все по нулю, посчитать сумму в двух деревьях и найти разность этих двух сумм. А остальные две операции делаются как на обычном дереве.

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

      А можешь, пожалуйста, показать код?

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

    Пусть di = bi - ai Теперь рассмотрим величины xi — сколько стогов сена(или чего там) мы перешлем из кучи i-1 в кучу i(если пересылаем в обратном направлении, то xi < 0). Теперь получаем систему уравнений вида x_0 — x_1 = d_0, x_1 — x_2 = d_1, ..., x_{n — 1} — x_0 = d_{n — 1}. Нужно найти решение этой системы, минимизирующее сумму модулей x_i. Ясно, что все решения отличаются друг от друга прибавлением константы ко всем x. Тогда найдем любое решение(например положив x_0 = 0), отсортируем получившиеся x, и прибавим такое число, чтобы занулилось x_{n / 2}. Доказательство оптимальности тут такое же, как у точки, минимизирующей сумму расстояний до данных точек на прямой.

    Какой-то полный атас с техом и курсивом, но вроде основная идея понятна.

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

А я порешал бронзовый дивизион. Отлично просто. Зарегался, думал нормальных задачек щас порешаю, так нет, на тебе три задачи A+B, A*B, A^B

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

    а как ты решал задачу problem 2. connect ?

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

      ДП с маской. (M маска коров возле которых мы уже повернули, X корова возле которой мы сейчас стоим, Y предыдыущая вершина где мы были) Y это или номер коровы или точка (0, 0). возле коровы X мы сейчас тоим, и должны повернуть возле неё, перейдя при этом к другой корове возле которой еще не поворачивали, или вернувшись в (0, 0). как-то так.

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

      N<=10 -> можно решать за N!

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

Появились, наконец, результаты.

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

    Может, кто осилит найти ошибку здесь? А то 2 теста по WA не прошло, непонятно, как такое может быть

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

Рекомендую прочитать разбор задачи skyscraper: http://usaco.org/current/data/sol_skyscraper.html, довольно интересная идея.

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

    а O(3^n) проходили полный балл?

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

      У меня прошло. Но на Java был TL 4 секунды =)

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

    как не странно, но у меня прошло вот такое решение. перебирая все маски, пытался как можно оптимальнее заполнить каждый лифт. в итоге получил O(N * 2^N)

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

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