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

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

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

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

2) Будем смотреть на путь содержащий ровно m вершин. Пусть его длина len. Тогда с вероятностью C_m⁰(1 - p₁)^mp₁⁰ мы потратим ровно len времени на прохождение этого пути. С вероятностью C_m¹(1 - p₁)^m - 1p₁¹ мы потратим ровно len+24 времени на прохождение пути. Считая так и далее найдем то i, для которого сумма C_m⁰(1 - p₁)^mp₁⁰ + C_m¹(1 - p₁)^m - 1p₁¹ + ... + C_mⁱ(1 - p₁)^m - ip₁ⁱ ≥ p. Тогда длительностью данного маршрута будет число len+24i. Выберем минимум по всем путям для различных m и выведем ответ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

У нас такая формула получилась: (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").

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