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

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

Примерно через 25 минут начинается очередной SRM. До закрытия регистрации еще 10 минут.

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

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

OK :(

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

как решается div1 500?

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

    Возьмём множество из всех атомов. Найдём отсутствующее ребро, у которого оба атома в множестве. Понятно, один из них надо исключить, переберём какой, уходим в рекурсию. Если всё ок — берём сумму атомов во множестве и улучшаем ответ.

    Так как мы можем исключить всего 16 атомов (50/3) , то и ветвлений всего 2^16.

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

    Должен работать такой перебор: Берем все вершины и находим наименьшую пару (i, j) что между i и j нет ребра. Рекурсивно перебираем, выкинув либо i либо j. Т.к. глубина не больше n/3, получаем O(2^(n/3))

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

      Еще можно или даже

      Будем решать задачу на дополнении. Тогда это найти вершинное покрытие размера не более чем. Тогда вершину степени <= 1 мы точно не возьмем. А иначе можно либо взять, либо не взять. Тогда удаляется либо вершина либо два соседа. Получаем рекурентность на Фибоначчи.

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

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

Посоны, посоны, алгоритм с Википедии заходит? Говорят, работает за O(3^(n/3)), у меня два дефенда и единственная выжившая 500-ка в комнате.

UPD. Не заходит :(

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

    где n — количество максклик(которые нельзя увеличить)
    автор ниже прав, я не умею читать :(

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

    У меня алгоритм Брона-Кербоша зашел в практике после отсечения (если кандидатов не хватит на достаточно большую клику), максимум 684 мс. Подскажите, это дырка в тестах или правда этого отсечения достаточно? http://pastebin.com/icARB4fb

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

Из моего кода в 250-ке внезапно пропала строчка, которая добавляла .mp3 в конец всех названий. То есть, сначала я действительно ее не добавил, но потом добавил и отослал. У кого-нибудь что-нибудь подобное было? Пользуюсь kawigi.

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

    compile нажимал, или только run tests?

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

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

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

Буду благодарен если напишете Div2-1000 :)

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

    я так понимаю она идентична div1 500? Она обсуждаеться выше

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

    Для начала создадим порядок в обходе всех ребер. Теперь пустим рекурсию по состоянию. В начале у нас пустое множество. Пусть на каком-то шаге у нас образовалось мн-во А, |A| = t. Найдем все ребра вершины которых не лежат в A. Если таких ребер не нашлось, то из вершин не лежащих в А возьмем k-t вершин с максимальным весом добавим и обновим ответ. Иначе возьмем первое ребро и закинем сперва первую вершину, а затем вторую. В итоге у нас получается О(n * n * 2^k).

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

Кто-нибудь умеет доказывать такое решение 500ки: 20К раз пошафлим вершины и жадно наберем клику?

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

    Казалось бы, падает на полном графе, в котором удалено штук десять ребер.