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

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

Сегодня в 1900 по Москве.
Время в других часовых поясах.

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

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

Как решать 550? Немного похожа на независимое множество в транзитивном замыкании.

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

    так оно и есть. 1533 с тимуса — боян [||||||||||||||||||||]
    убиваем всех девок что принадлежат какому-нибудь циклу, а затем 1533.

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

      тогда вопрос, как решать 1533?)

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

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

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

        максимальное независимое множество в DAG (Direct Acyclic Graph) после удаления циклов у нас останется DAG

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

кто-нибудь сдал тернарник в 250?

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

1000: представим числа в двоичном виде. Пройдемся гауссом прямо и обратно, пусть результат это A. Возьмём XOR строк, пусть это S. Ответ — сумма по i : S xor (i==0?0:A[i])

550: макс. антицепь = мин. покрытие путями = N минус макс. паросочетание в раздвоенном графе. Циклы? Пофиг на них. Если девушка сама себя может защитить, то в графе являющимся замыканием есть такое макс. паросочетание где все такие девушки идут в самих себя, а значит не влияют.

Эх, если бы не было бы тупой ошибки в паросочетании (khun(i) -> khun(M[i])) , было бы седьмое.

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

    А как именно в 550 граф раздваивать?

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

    А как в 550 после этого восстанавливать ответ, если я хочу узнать, какие именно вершины брать?

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

      Не знаю, может вот здесь написано: http://en.wikipedia.org/wiki/Dilworth's_theorem

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

      Тоже очень интересует этот вопрос.

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

        Придумал craus.

        Сразу дополним граф до транзитивно замкнутого. Покроем путями. Теперь нужно на каждом пути выбрать ровно одну вершину антицепи (если на одном пути две вершины — они конфликтуют, если ноль — их мало).

        Сначала выберем все вершины, являющиеся нижними концами путей. Теперь, пока в множестве выбранных есть конфликт — пара вершин (A,B) такая, что существует ребро из A в B — заменяем вершину B на ее непосредственного предка в пути.

        Почему это корретно? В частности, почему мы уверены, что вершина B никогда не оказывается верхней в пути при попытке обращения к ее предку? Заметим, что любая операция замены была обязательной. Это значит, что если на каком-то шаге вершину B пришлось заменить на предка, то B не может принадлежать никакой наибольшей антицепи (можно доказать по индукции). Получается, что если на каком-то шаге мы не можем совершить операцию замены, то на пути этой вершины вообще нельзя выбрать элемент антицепи, что противоречит Dilworth's theorem.

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

Что неправильного в моём решении 550: в топологическом порядке запускаем от ещё не рассмотренной вершины dfs и добавляем эту вершину в ответ, если на неё никто не сослался в процессе обхода?

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

В 550 заходит перебор. Только у меня была лишняя оптимизация, из-за которой TL. И даже очевидно почему. Вот отстой.

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

    А как перебирал?

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

      Просто ищем антиклику. Надо запоминать + перебирать по порядку. Дает .( — это логарифм от map). Это видимо где-то на границе прохода Поэтому я зачем-то дописал выбор вершины после котрой останется самая маленькая маска. Но я тормаз, и при этом к чертям ломается оценка. А так проходит.

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

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

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

          Без какого-нибудь перемешивания вершин такое все равно опасно сдавать.

          Вот, например, нехороший тест

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

            Этот тест был в челленджах? Просто у меня 37 мс на макс время, мне Ваня сказал

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

              Видимо не было, если решение зашло.

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

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

    А не такое, ли решение должно зайти? И как увидеть почему задача слетела?

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

    Ага, я взял код из условия одной задачи Burunduk1 с его тура в Харькове в 2011 году, добавил туда мап, случайно перемешал вершины и оно прошло c макс временем работы 78мс.

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

    Зачелленджил решение в практис руме, неужели оно проходило систем тесты? Сам сначала написал довольно медленный перебор, потом сделал ресабмит, чтобы его ускорить, но в итоге добавил тупой баг.

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

Мой слив