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

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

Условия: http://contests.snarknews.info/files/snws11/probs/day5.pdf 
Результаты: http://contests.snarknews.info/index.cgi?data=snws11/standing5&menu=index&head=index&mod=snws11&class=snws11 

Задача А.
Сначала заменим все числа на A%mod, так как понятно нас интересует только остаток, затем добавляем сначала все числа с одним остатком, затем с другим итд. Допустим, что сейчас добавляются числа с отстатком m, а до этого уже были добавлены какие-то числа с другими остатками. Поддерживаем динамику d от двух параметров, где d[v][q] = количество последовательностей из уже добавленных чисел таких, что есть ровно v пар чисел с одинаковым остатком, НЕ равным m, стоящих рядом, и q пар чисел с остатком, равным m, стоящих рядом.
Кроме того, двигаясь вправо поддерживаем: n - сколько уже вообще добавлено чисел, и r - сколько уже вообще добавлено чисел с текущим остатком. Теперь, закрепим v и q. У нас есть три опции:
1. Поставить число между двумя одинаковыми числами, не имеющими остаток m. Таких вариантов, очевидно, v, и такое действие уменьшит v
nd[v-1][q] += d[v][q] * v
2. Поставить число между или рядом с числом с остатком m. Это увеличит q. Таких вариантов, если подумать, 2*r-q:
nd[v][q+1] += d[v][q] * (r*2-q)
Наконец, поставить число в любую другую позицию. Это не изменит ни q ни v. Это все оставшиеся варианты, то есть n+1 - v - (r*2-q)
nd[v][q] += d[v][q] * ( n + 1 - v - (r*2-q) ).
Потом, когда остаток от деления меняется, добавляем числа с предыдущим остатком к старым:
nd[v+q][0] += d[v][q];
В конце ответ будет в d[0][0] - потому что не должно быть никаких чисел с равным остатком рядом.


Задача B.
Я занумеровал вершины в порядке выхода из DFS, и вывел их по убыванию этой величины.

Задача C.
Единственное ограничение, данное нам -- это то, что кратность ребер не превышает четырех. В частном слуачае, когда вес всех ребер равен единице, это будет задача на матричную теорему Кирхгофа, которая решается за N^3.
Я упускаю что-то очень важное :о)

Задача F.
Очевидно, сами числа не важны, важна только их длина. Нам надо понять, сколько битов понадобится, чтобы представить число с записью 10^K в системе счисления B. Это, если я правильно помню, равно floor( K*log(B)/log(2)+1 ).

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Текст не соответствует заголовку. В заголовке нет задачи C.
14 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
Глупый вопрос по решению Саши задачи B. Для обхода графа типа 1->2->3->4, с остальными обратными ребрами (3->1, 4->2, 4->1) каким образом условие будет выполняться для первой и четвертой вершины?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Потому что я по-моему решение не той задачи написал.

    Сейчас посмотрю в системе как я решал на самом деле...

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

      Нет, все правильно оказалось.

      В предыдущей правке мои неверные мысли и неверный код который прошел все тесты :О)

      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        > Идея в том, что если мы начали из какого-то игрока DFS и дошли до какого-то другого, то мы можем смело второго игрока вывести после первого.

        Необходимые условия для того чтобы A можно было поставить выше B в ответе:
        1) несредственная связь типа A>B
        2)
        или существует Z такой, что A>Z>B

        Если мы дошли от игрока A до игрока B в DFS, то это значит только то, что существует цепочка A>X_1>X_2>...>X_n>B, при этом необязательно выполнение условий 1) или 2).

        Контрпример yaro остается в силе.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я неверно понимал условие :о)
          Значит мое решение неверное, а тесты плохие :о)
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Странно. У меня во время контеста, топологическая соритровка получила WA9. Причем решение почти один в один с этим.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Задача B.
Я делал так: построил новый граф на тех же вершинах, в котором провел ребро B->A, в том случае, если А не выиграл у В и не существует С такого, что А выиграл у С и С выиграл у В. Иными словами я провел ребро в новом графе от В к А, если А не может стоять раньше В в искомом списке. Затем упорядочил вершины с помощью топологической сортировки.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Дело в том, что С в итоговом списке должен стоять между A и B. Иначе подходит просто сортировка по очкам
    • 14 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      Очень похоже на то, что тесты были очень слабые. Во время контеста я не заметил необходимость того, чтобы C стояло между A и B, и просто вывел в порядке убывания полустепеней выхода (при таком условии легко показать, что это правильный ответ).

      А правильно решать, видимо, следовало как-то так:
      Пусть для n <= m мы строить ответ умеем. Положим n = m + 1.
      Выберем некоторую вершину v. Пусть A -- множество вершин, из которых есть дуга в v, B -- в которые есть дуга из v (тут ещё стоит напомнить, что для всех отличных от v вершин u либо u->v, либо v->u). Построим ответы для A и В -- эти последовательности обозначим за Ans(A) и Ans(B).  Утверждается, что последовательность Ans(A)vAns(B) является ответом для всего графа (в этом несложно убедиться).
      База: n = 1 -- очевидна.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вопрос по задаче F. Как эту формулу уложить в точность. Неужели просто в double проходит?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Проходит. Более того, с небольшим порядком EPS. То есть либо тесты, опять же, слабые, либо мы верим, что log_2(A) * B очень близко к целым не подбирается при установленных в задаче ограничениях.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А по задаче E. UFO, какие есть идеи?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну я пытался на контесте впихнуть квадродерево. У меня не получилось  - упорно либо WA7 либо TL15. Правда после контеста нашел баги, но это ничего не изменило и вдорешивании те же WA7 и TL15. 
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Я не сдал эту задачу, потому что не смог себе ответить на два вопроса:

    1. как понять, какие из треугольников брать с плюсом, а какие с минусом.

    2. как понять (по двум углам) какой из двух секторов взять.

    Когда-то давно я эту задачу так сдавал, сейчас не могу вспомнить как решал обе описанные проблемы. Возможно, надо сортировать не относительно центра окружности, а относительно центра масс всех выбранных точек. Тогда, видимо, будет немного сложнее считать площадь фигур, у которых одна из сторон - дуга (они больше не будут секторами), но зато многие ответы на вопросы саморазрешатся. Надо будет попробовать на дорешке сдать так.