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

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

Привет всем.

Интересует задача 2 из прошедшего сегодня на OpenCup, Grand Prix of Siberia, Div 2.

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

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

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

Как решались 8 и 10?

В 8й, я решал через хэши, игнорируя символы 2го алфавита, и подсчитывая их соответствие отдельно, но получал wa21.

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

    8 — баян с какой-то заочки. Утверждается, что работает КМП со следующим компаратором: если один из символов из первого алфавита, то сравниваем, как обычно. Иначе сравниваем значение "сколько символов назад был точно такой же, с точностью до того, что, возможно, строку надо было там обрезать". Утверждается, что в доказательстве корректности ничего не меняется и КМП будет работать.

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

    10 — зафиксируем не только конечную вершину, но и длину пути в вершинах. Очевидно, что тогда надо минимизировать путь в обычном смысле. Это делается за квадрат от числа изначальных вершин, так как граф получается ацикличный. Теперь надо для каждой длины посчитать, сколько ожиданий в городах надо прибавить, чтобы сошлась вероятность. Считаем все C(n,k) (взвешенные, с вероятностями p и 1 - p) за квадрат и считаем в каждой строчке, сумма сколько первых вероятностей больше чего надо. После этого перебрали длину ответа и выбрали оптимум.

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

    Задача 10. Можно разбить решение на две части.

    1) Запустим некоторое подобие алгоритма Форда-Беллмана и найдем кратчайшие пути в вершину n, содержащие k вершин для всех k от 1 до n.

    2) Будем смотреть на путь содержащий ровно m вершин. Пусть его длина len. Тогда с вероятностью Cm0(1 - p1)mp10 мы потратим ровно len времени на прохождение этого пути. С вероятностью Cm1(1 - p1)m - 1p11 мы потратим ровно len+24 времени на прохождение пути. Считая так и далее найдем то i, для которого сумма Cm0(1 - p1)mp10 + Cm1(1 - p1)m - 1p11 + ... + Cmi(1 - p1)m - ip1i ≥ p. Тогда длительностью данного маршрута будет число len+24i. Выберем минимум по всем путям для различных m и выведем ответ.

    Проблемы могли возникать с точностью — поэтому мы считали сочетания и степени в логарифмах, а так же нужно было не забыть, что мы могли "тормозить" и в вершине с номером n (иначе ВА 9).

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

      п. 2 можно было сделать проще и не считать в логарифмах. Пусть dp[i][k] -- вероятность, что мы получим в пути длины k ровно i писем. Тогда очевидно, что dp[i][k] = p * dp[i-1][k-1] + (1 — p) * dp[i][k-1].

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

        Действительно, так удобнее и нет проблем с точностью :)

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

    У нас решение с хешами прошло.

    Вначале определяем все возможные вхождения подстроки, игнорируя второй алфавит. Затем проходим "окном" ширины, равной длине подстроки, за линию по строке, пересчитывая ещё один хеш. Устроен этот второй хеш так: скажем, что у первого встретившегося символа из второго алфавита код t (t — константа, не зависящая от символа). Теперь код t+1 присвоим самому левому символу второго алфавита среди тех, что правее текущего в окне и отличаются от первого. Код t+2 следующему впервые встретившемуся символу второго алфавита. И т.д. Ясно, что такие хеши будут равны, скажем, для строк abc и cba, а именно это нам и требуется. Хеш подстроки не меняется, а хеш от окна несложно пересчитывается за размер алфавита.

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

      Хм, странно, вроде бы как раз так и реализовано, только второй хэш немного по-другому считается, видимо из-за этого. Спасибо, попробую вашим способом.

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

    10) А мы были единственной командой которая нарвалась на то, что при P=0 любой тест некоректен?

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

Для решения задачи 2 надо знать формулу площади поверхности крышки сферы высотой h: S = 2·PI·R·h.

Представим, что мы проходим по сфере целую окружность (2·PI·R), тогда если удалить из сферы поверхность, на которой мы все съедаем, сфера распадется на две одинаковые крышки.

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

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

а почему в 4й заходило такое: если n <= 10 считаем определитель, иначе выведем 0?

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

    Хочу сказать больше: если n==1 считаем произведение, иначе выводим 0

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

    Ответ 0 на любом тесте с n>=2, т.к. ранг матрицы не превосходит 1 по одному из определений ранга, а значит (т.к. 1<n) ее определитель 0. Почему — ну... ничего лучше, чем прочитать какую-нибудь книжку по линейной алгебре посоветовать не могу, это стандартная теория.

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

    Понятно, что строки линейно зависимы (видно, из построения самой матрицы) при n > 1 => определитель будет равен 0. Поэтому определитель можно было считать только в одном случае :) Правда, это не помешало нам посчитать определитель во всех случаях :)

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

    Как было сказано в условии задачи 4, холивар обеспечен:)

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

    Какая-то странная задача 4. Заходило все что угодно. Мы не считали определитель вообще. При n четном выводили 0, и даже доказали почему, а при нечетном считали произведение всех элементов и умножали на n. Сдалось

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

В задаче 2 получалось две части — полоска и "шапочка" как на картинке:  .

Обе площади можно было посчитать при помощи следующего интерала:

Для полоски получался интеграл:

где beta - это угол, под которым видно нашу дугу.

Для "шапочки" получался интеграл:

Итоговый ответ считается по формуле:

2R1 + R2

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

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

    В каком случае может получится "шапочка" ? ведь нужно пройти из одной точки в другую поедая все на радиусе eps (из условия). Значит "поеденная" площадь не будет кругом. Или я не понял условие?

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

      "Шапочка" получается в результате объединения "полушапочек" с двух концов полоски (все точки на расстоянии не более чем eps от конца образуют "полушапочку", если полоску мы считаем отдельно). Таким образом вся площадь распадется на две части — полоска + две "полушапочки". Полоску считаем отдельно, и "полушапочки" объединяем в одну.

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

Как решать 9?

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

    Я 3 часа писал жесть, в итоге успел.

    1. Запишем высоты вершин эйлеровым обходом дерева. Тогда, любое поддерево = непрерывный отрезок в таком обходе, а деревья изоморфны, когда у них обходы совпадают.
    2. Поймем, что наша операция = взяли непрерывный отрезок из обхода, поправили в нём высоты, прицепили в другую часть обхода.
    3. Радостно осознаём, что это умеет делать декартово дерево по неявному ключу.
    4. Для определения того, что такое дерево уже было будем в декартовом дереве поддерживать обычный полиномиальный хеш.

    Тогда, всё просто: Взяли отрезок, поправили высоты, прицепили в новоё место, смержили, проверили, что такого хеша уже не было.

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

    Код: http://pastie.org/5361103

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

      Это не жесть, если уметь обращаться с декартовым деревом. Всё это (поддерживать что-то на отрезке, вырезать отрезок и находить номер по вершине) — стандартные операции.

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

      Я это закодил минут за 30, по ощущениям. Разморозят монитор — можно посмотреть поточнее.

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

        Да, понял. Я номера точно так же находил. У меня в решении вершину, которую записываем после выхода из потомка я тоже перемещал = могла переместиться правая граница вершины, поэтому я фиктивную добавил и забил.

        Насчёт времени: ну у нас уровень разный немножко :D

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

      Непонятно зачем высоты. Можно просто при входе в вершину писать '(', при выходе — ')', получим строку вида "(()(()))", а потом на ней уже делаем стандартные операции декартовым деревом.

      Кстати, а если в условии заменить определение "изоморфизма" от авторов задачи на обычный изоморфизм, кто-нибудь умеет такое решать?

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

        Высоты чтобы писать и дебажить 3 часа потом их :(

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

Какая формула в задаче 6?

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

    На разборе рассказывали мутные формулы, они все выводятся из условия. Основные ошибки — кучи возможных делений на 0.

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

      У нас еще вроде возникали проблемы с отрицательными ответами.

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

        Вроде это был WA 2.

        Кстати, во многих задачах, судя по разговорам, неправильные решения валились на первых 10 тестах.

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

        Не совсем. Как только включили мозг, проблемы исчезли)

        Для решения надо заметить, что всегда надо сливать либо в самом начале, либо в самом конце — каждый из этих случаев дает условие вида "надо подождать пока температура жидкости измениться с ta до tb", что (при окружающей температуре 0) происходит за время ln(ta/tb)/k при ta/tb>=1 и не произойдет никогда в противном случае (tb=0 разобрали отдельно — эта температура либо получена сразу же, либо недостижима). В качестве ответа выбираем лучшую из этих двух стратегий.

        Чтобы доказать это надо следить за изменением "энергии системы" (сумма по всем сосудам температура*масса), взять производную, увидеть что для жидкости с параметрами t и m энергия приближается к энергии при "комнатной температуре" со скоростью t*m. Дальше разобрать несколько случаев как расположены относительно друг друга стартовые температуры и энергии. А можно и просто поверить в указанное выше утверждение.

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

          Мы написали тернарный поиск по моменту вливания второй жидкости, а внутри просто бинарный поиск по времени.

          Единственный частный случай, который нам пришлось рассмотреть — это

          Topt = T0

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

    У нас такая формула получилась: (opt * M1 + opt * M2 — M1 * T0 — M2 * T0) = e^(-k*t) * (M1 * T1 — M1 * T0 + M2 * T2 — M2 * T0).

    opt — это температура, которую следует достичь.

    Пусть a = (opt * M1 + opt * M2 — M1 * T0 — M2 * T0) и пусть b = (M1 * T1 — M1 * T0 + M2 * T2 — M2 * T0), тогда:

    t = (-ln(a / b)) / k

    Остается рассмотреть частный случай, когда (a == 0 && b == 0), из которого следует, что t = 0 и при случаях (b == 0 || a == 0 || ( (a<0)&&b>0)) || ((a>0)&&(b<0)) вывести ("Impossible").

    Самое удивительное, что только после контеста, на разборе, оказалось, что мы не совсем внимательно прочитали задачу и решали отличную задачу от данной — находили нужное время, если обе жидкости остывают с самого начала. Но всё зашло :)

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

      У нас та же формула, а вот частный случай другой. Обидно :) Оставалось 15 минут до конца, когда приступили к ней.

      UPD. Вы же ее не сдали... В таблице нет ОК-а по 6-ой у вашей команды...

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

        Я в команде Grodno bl++: Siarhei, Ulezla. Danilchuk, div1. Просто фамилия в другой написана. Задачу сдали на 3:07 с +1.

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

      Замечу, что в этой задаче переход к температурам относительно окружащей среды сильно сокращали формулы, для этого надо было вычесть ее из 3 остальных температур. Еще можно считать массу первой жидкости ненулевой (иначе сразу перелили всю вторую), а также температуру любой из трех жидкостей — положительной (можно умножать все температуры одновременно на -1).

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Еще проще было аккуратно написать функцию время остывания с исходной температуры до нужной (в ней три if). Затем просто или сразу смешиваем и вычисляем эту функцию для оптимальной температуры (смешивание в самом начале), или в качестве нужной температуры берем такую, что при смешивании сразу получаем жидкость оптимальной температуры (смешиваем в самом конце). Из двух этих величин выводим наименьшую (или Impossible если обе бесконечно большие).