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

Автор phantom11, 13 лет назад, По-английски

This is a gentle reminder to all coders that SRM 537 is going to happen on the coming Saturday i.e. 17th March.This round is sponsered by CITI ,so there is a total purse of 5000 USD.So gear up and get ready for the challenge.You can find the round details and timings here. You can get the exact prize divisions and a bit of discussion on the SRM on vexorian blog here.

A couple of SRM's back ,the registeration limit of 2500 members was reached some 5 minutes before the closing time.So dont be late or else you may miss a chance to grab some money. Good Luck and Best wishes to all :-)

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

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

Please notice, that DST is already in force in USA, hence for most of the world SRM would be one hour earlier then it is common for Saturday SRMs

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

And one hour overlaps with COCI :( http://www.hsin.hr/coci/

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

There are no more spots available =( 2500 registrants.

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

And new MLP episode after challenge phase! YAY!

UPD. mistaken, it was at the same time as SRM :(

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

    Пойду что ли новый вчерашний South Park посмотрю...

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

      Я смотрю любителей антропоморфных пони среди программистов больше чем круглоформатных американских школьников :-)

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

У меня одного весь раунд тупила арена: сначала я не мог посубмитить, потом раз 5 арена просто отрубалась?

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

Как делать middle?

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

    Побитово.

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

    я считала вероятность 1 для каждого бита каждого из чисел надеюсь пройдет по точности

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

    Решаем задачу для каждого разряда в отдельности, т.к. матожидание линейно.

    Считаем динамику — D[k][i] — матожидание значения выбранного разряда i-ой комнаты к k-ому ходу. Оно, очевидно, равно (D[k — 1][prev[i]] + inv(D[k — 1][i])) / 2, где inv(x) это либо 1 — x, если соответствующий разряд в i-ой маске для первого заклинания — единица, либо просто x.

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

      Спасибо. Ацтой, я не знаю очевидных основ теорвера.

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

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

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

          Я бы с радостью, но, увы, у нас теорвер только на втором курсе.

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

    Я писал динпрог по четирем параметрам: f(room, day, bit, value) — какая вероятность того, что количество после day дней bit-ый бит в комнате room будет иметь значение value

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

Как нормально решать первую в div1? Ато вторую написал, а на первую только чушь какая-то в голову приходила.

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

    Перебираем Y. Достаточно, чтобы можно было собрать числа A и B. Проверяем все возможные коэффициенты в линейной комбинации pX + qY до 200 с небольшим.

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

      мда, все так просто...

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

      Чувствую себя идиотом %)

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

      Я запихнул в массив все возможные A*p+B*q до p, q ≤ 200 и проверял Y до 200 =) Почему собрать A и B достаточно?

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

        Потому что, если мы можем собрать А и B, то логично, что мы можем собрать все остальное, что собирается при помощи А и B ;)

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

        Пусть вы собрали A и B, тогда pA+qB вы собрали, взяв в p раз больше "ингредиентов" для А и q — для B

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

          "Чувствую себя идиотом %)"
          Моя очередь...

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

        тогда, подставляя представление для А и В в виде линейных комбинаций X и Y и раскрывая скобки, получаем представление любой линейной комбинации A и B в виде линейной комбинации X и Y

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

    Соображение: достаточно проверить, что не пропала возможность набора у всех чисел до A*B <= 40000. Насчитали вектор достижимости (можно ли взять число или нет) относительно {A, B}. Это делается за A*B. После этого перебираем Y от 1 до 200 и смотрим, что список достижимости не сузился.

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

      такое ведь тл-ится?

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

        40000·200 = 8 * 106? Не думаю. Нам надо 200 раз посчитать достижимость, что делается за A·B

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

        200^3 — восемь миллионов. С чего бы ему ТЛиться.

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

        Почему же? 200 * 40000 — вполне нормально (200 — перебираем Y, 40000 — насчитываем достижимость).

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

        Оно даже прошло систесты.

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

          тесты — ужасны! у меня прошло решение за ~200^4, для которого я знаю очевидный тест, на котором оно TL-ится :(

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

dolphinigle and I collaboratively wrote the problemset together. We hope the problems were interesting for you all :)

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

Ух ты, я впервые в жизни сдал все три задачи!

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

    А как решалась 1000?

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

      Как обычно, рассмотрим граф, где вершины соответствуют числам от 1 до M. Доминошки — ориентированные ребра. Нам нужно найти там самый длинный цикл, проходящий по каждой группе кратных ребер хоть раз. Иными словами, нам нужно выкинуть из графа как можно меньше ребер, чтобы он стал эйлеровым и чтобы в каждой группе кратных ребер осталось хоть одно. Посчитаем для каждой вершины разность между исходящей и входящей степенью. Выкинем по одному ребру из каждой группы. Добавим две вершины — исток и сток. В вершины с положиетельной разностью степеней пустим ребра из истока такой пропускной способности, какова разность; с отрицательной — в сток. Всем ребрам присвоим стоимость 1. Найдем min cost max flow, его стоимость — сколько ребер надо удалить.

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

        каким образом достигается связность полученного эйлерового графа? почему ответ у тебя не получится состоящим из нескольких компонент?

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

          Например за счет условия что всех ребер надо взять по одному.

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

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

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

А я под чертой. Призы первому, я второй. Самая обидная позиция. Приятней было бы третьим в комнате быть, что уж тут... Хотя приятно, что впервые в жизни 2ой в комнате div1 (до этого был только третьим несколько раз), но все же...

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

    Какая разница? Чтобы их получить надо заплатить налогов и за пересылку большую сумму :) Впрочем, за мое первое место видимо вообще на благотворительность пойдет. Тем лучше.

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

      Приятно само ощущение формального приза. Я понимаю, что я могу те же деньги заработать без проблем фрилансом или еще каким-то другим способом, но это "не интересно" :)

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

      Когда я получал, то платил только комисию в банке (вроде как ~ $5)

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

        Может быть. Мне говорили про как минимум подоходный налог США, и N долларов за пересылку. Мне что-то подсказывает, что должны быть какие-то еще местные налоги, хотя не факт.

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

          местные налоги 1 процент скорее всего