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

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

The USACO 2012 February contest is available February 3 through February 6.

Контест доступен с 3 по 6 Февраля 2012 года. Участие открытое, 3 дивизиона. 3 задачи на 3 часа.

На сайте написано, что результаты будут 12 февраля, всем удачи!

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

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

ok, я нашел в правилах, там линукс

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

Расскажите как решать задачу про веревку и про прямоугольники?(бронзовый див.)

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

    Есть мнение, что контест ещё не закончился.

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

Удачи всем)

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

Как решать b и c в bronze div ?

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

    Не закончилось соревнование. В 15:59 МСК ещё можно стартовать и 3 часа решать.

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

Спасибо

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

    Про прямоугольники — если не ошибаюсь, дано 10 прямоугольников, найти площадь их объединения. Можно довольно просто это посчитать по формуле включений-исключений за O(N*2^N). Просто переберем все возможные подмножества прямоугольников, будем добавлять площадь пересечения прямоугольников в подмножестве к ответу с плюсом или минусом.
    http://e-maxx.ru/algo/inclusion_exclusion_principle

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

    Прямоугольники: создал массив объектов вида <x, y_down, y_up, flag>, где флаг говорит, начинается ли в этом объекте прямоугольник или заканчивается. Поместил в массив все границы прямоугольников, посортировал, и добавлял площадь пройденного куска. Сложность — (UPD) O(N^2*log(N)) — за счет подсчета суммарной высоты прямоугольников на текущий момент.

    Третья: посчитаем длины s[i], пока они меньше 10^9. Теперь находим максимальный префикс s[k], меньший n, являющийся элементом последовательности, и вычитаем его длину из n. Теперь мы знаем, что дальше следуют 'm' и k+3 букв 'o'. Если n > k+4, то выкидываем k+4 символа и получаем, что n принадлежит постфиксу — т.е. тоже элементу последовательности. Решаем задачу для этого полученного n сначала =)

    P.s. Кто-нибудь знает, как сделать зачеркнутый текст?

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

      Можете показать исходник задачи про прямоугольники? O(N2) зашло бы и в silver, там N до 1000.

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

        Вот. Но про квадрат я наврал, ввиду ограничений бронзового дивизиона там совсем не квадрат, прошу прощения, но, кажется, знаю как решить и за n^2*log(n) — нужно только изменить способ поиска суммарной высоты прямоугольников на текущем отрезке. Достаточно пробежать все открытые прямоугольники и положить их верхние/нижние границы в массив с пометкой открывающие/закрывающие, посортировать и пройти по нему, т.е. сделать по сути то же самое, что и по горизонтали.

        P.s. А если поддерживать отсортированный набор с использованием set<>, то вроде бы можно и за n^2. Поправьте, если не прав.

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

          Ну формально там квадрат — O(20000*N2) ~ O(N2) =)
          Может я неправильно понял, но как с std::set может быть N2 ? Сам set ведь работает за логарифм.

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

            Когда проходим по отсортированному массиву левых/правых границ, добавляем верхнюю/нижнюю границы в set за O(log(n)). Если закрывающую — то удаляем за то же время. При этом эти границе содержатся в отсортированном виде, и мы можем перебирать их по порядку — за О(n). Эта процедура выполняется на для каждой встреченной точки, итого имеем O(n^2). Set нужен для поддержания отсортированности массива. В принципе можно просто содержать отсортированный массив, в который добавлять/удалять за O(n), асимптотика в итоге та же, так может быть проще.

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

Первая silver проще сканлайна решается?

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

Как решалась 1 задача голда?

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

    Единственное, что придумалось — поток минимальной стоимости, но там квадрат минимум =( Интересно услышать и про вторую задачу в голде.

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

      поток минимальной стоимости за квадрат? Это как?

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

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

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

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

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

          Ну, она может еще поменять что-то из предыдущего. А что за жадность?

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

            А как здесь поток построить?

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

              Две доли: 1)n вершин — это коровы. 2)n+k вершин — это коровы и скидки. Соединяем корову либо с ней самой с ценой P (если без скидки), либо со всеми скидками с ценой C. Нашли минимальное по цене масимальное паросочетание — это будет ответ.

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

      Вторая задача — ось симметрии либо является серединным перепендикуляром к отрезку, соединяющему первую точку с какой-то, либо является серединным перпендикуляром к отрезку, соединяющему вторую точку и какую-то и при этом проходит через первую точку, либо проходит через первую и вторую точку

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

и 3-ая из голда?

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

    Общие мысли: Подвесим дерево. За O(NK) посчитаем для каждой вершины ответ для поддерева при соответствующем K. Теперь посмотрим, какие вершины мы не посчитали в ответе. Те, путь к которым пролегает через родителей. Давайте еще за O(K) для каждой вершины поднимемся на K, на каждом шаге прибавляя к ответу уже посчитанное первой динамикой число для родителя (надо еще вычесть ответ для поддерева, из которого пришли).

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

    Я так решал — будем динамически считать ответ для всех вершин, уменьшенный на число коров в самой этой вершины для всех K. Тогда answer[i][j] = сумма по всем детям answer[i — 1][v] + cow[v] — (кол-во детей — 1) * answer[i — 2][j]. Почему это так — когда мы считаем сумму для всех детей, мы лишний раз считаем возврат в начальную вершину (но без еще лишнего возврата в саму эту вершину, поэтому -1 при множителе)

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

А когда будут результаты?

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

Появились результаты.
Хотя фигня, конечно. При Колстаде уже во вторник вечером письмо с предварительными результатами было, а в четверг вечером — окончательные. А теперь неделю ждешь.