Плюсую за 35. Сам заслал Монте-Карло на последних минутах от безысходности.

В 35 я взял и расписал всё нафиг. Но это такой отстой...

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

Оптимизация с куба до квадрата на запрос:

1. Самый вложенный цикл у меня зависит только от a₃ и какой-то внешней константы (если разделить на два слагаемых, а одно домножить потом). Предподсчитаем эти два слагаемых.
2. Получили квадрат плюс квадрат на запрос.

Ну 35 я попробовал решить так.

Посчитаем величины cnt[i][j][k] = сколько пар (x, y), таких что x+y=i, существует, причем никакое из чисел x и y не равно никакому из чисел j и k.

Тогда посчитаем величины bad и total — плохие для нас расклады и общее количество. Просто просуммируем все значения cnt[sum][c1][c2], где sum>c1+c2, а случай, когда выигрывают по наибольшей карте, разберем циклом фор отдельно.

Ну а дальше обычная магия — умножим bad на 3, потому что 3 игрока против нас играют, значит вероятность проиграть в 3 раза больше.

Это дает нам на третий сэмпл вероятность проигрыша 0.6, а значит вероятность выигрыша 0.4.

Ну в итоге формула выходит: if (3 * total — 12 * bad > 0) then "B" else "F"

35 я делал немного необычно. Для одной пары можно написать ДП(i, i1, i2, i3) — какую карту смотрим, какие уже у соперников, ну или 0 если еще нету или 101, если уже у них пара. Динамика хранит сколько комбинаций таких, что выиграем мы.

Возьмем и бин поиском найдем самую галимую пару, которая несет профит. Забьем константу. Теперь просто сверим пару на входе и найденную ранее. Так для каждого Н.

Ну 40 довольно тупая. Заметим, что в вершину i можно добавлять ребра только из таких вершины j, что j<i и a[a[a[...a[j]...]]]=a[i]. Значит есть 2^(количество таких)-1 вариантов — но нужно ведь ещё, чтобы не было такой вершины ближе, значит нужно вычесть 2^(количество таких j<i, что a[a[a[...]]]=k)-1 для каждого k<i, что a[k]=a[i] — это мы перебираем ту, которая будет ближе.

40 — нам дают дерево, надо посчитать количество способов сделать новый граф весьма странным образом. Если подумать, разрешается добавлять рёбра в из вершины в поддерево её предка в дереве, но при этом не должно оказаться, что все эти рёбра только в одном поддереве какого-то из детей предка. Т.е. если обозначить c_x количество вершин в поддереве вершины x, ответ умножается на (ну, +-1, не забываем про пустое множество), ну или как-то так.

35 — фиг знает как честно решать, я засабмитил лажу за n⁵, написанную на плюсах; как ни странно, довольно быстро работала. Т.е. я для каждого запроса просто перебрал одного из оппонентов, а для оставшихся 2х посчитал всё за линейный проход включениями-исключениями.

40 там несколько решений. Одно из решений -- вершину a, для которой все пути должны идти через b, надо либо подцепить непосредственно к b, либо к двум вершинам из двух разных поддеревьев b. После этого ее можно дополнительно соединить с любым множеством вершин из поддерева с корнем в b. Это делается динамикой. Я сам решал немного иначе, но у меня int вместо long long, так что там все понятно :о)

Моё решение по 35. В качестве главной морали позволю процитировать yeputons : "В 35 я взял и расписал всё нафиг. Но это такой отстой..."

Зафиксируем N, X, Y и одного противника. Пускай его карты A < B. У нас есть 6 вариантов:

           X    Y
   lose AB
   lose  A   B
depends  A        B
depends      AB
    win      A    B
    win           AB

Нас интересуют только первые 4. Соответственно при данном N, X, Y перебираем все 64 варианта по типу руки у соперника. Нам надо чтобы все три соперника нам проиграли 3й и 4й делаем ДП преподсчётом (при этом в ДП добавляем измерение количества взятых пар), чтобы оставить только проигрышные варианты. 3е ДП простое, 4е ДП посложнее. Вспомогательная картинка (если перебираем по позициям B — то прямоугольники это доступные позиции для А). Теперь можно для фиксированного N, X, Y в обоих случаях сделать ДП a[cnt][last] — количество вариантов выбрать cnt пар, проигрывающих нам, при этом последний невыбранный B — last. В случае второй половины варианта 4, и вариантов 1 & 2; нам известно количество свободных карт в каждой группе, и мы можем необходимое домножить на C-шки, так как нам годится любая комбинация из них, и там можно просто аккуратно (ключевое слово всей задачи) домножить всё. Ну и получаем кол-во выйгрышных раскладов и проверяем является ли эта величина умноженная на 4 больше общего числа вариантов. Асимптотика: O(P * N^5 + T * Q * 4^P), где P — количество игроков. На всякий, код.

Расскажу своё решение 35, оно разбирает один случай за O(n) и даёт точный ответ (число выигрышных комбинаций).

Используется формула включения-исключения: берётся куб числа способов выбрать вторую пару и из него аккуратно вычитаются те комбинации, в которых пары перекрываются. Вначале для каждого i посчитаем число таких j ≤ i, что j ≠ c1, c2. Теперь число способов выбрать две перекрывающиеся пары считается легко: перебираем общий элемент, для каждого значения прибавляем квадрат числа способов дополнить этот элемент до пары. Те комбинации, где перекрываются оба элемента, будут учтены по два раза, придётся скорректировать. Остались случаи, когда перекрываются все три пары. Здесь есть три варианта: "пропеллер", "треугольник" и "цепочка". Третий вариант — самый сложный, расскажу, как делать его. Считается вспомогательная динамика: для каждого i число таких j, что i ≠ j и пара (i, j) нас не обыгрывает. По этой динамике считаются частичные суммы. Теперь перебираем один из средних элементов цепочки. Число способов выбрать один крайний элемент — первая динамика, число способов выбрать оставшиеся два элемента — вторая динамика. В результат будут (ошибочно) входить цепочки, в которых некоторые (не соседние) элементы совпадают, но это либо "треугольники", либо более короткие цепочки — таким образом, всё, что нужно, чтобы отсеять эти варианты, уже посчитано. Осталось правильно подобрать коэффициенты.

Поскольку все динамики полиномиальные (а не экспоненциальные, в смысле значений), а условия достаточно простые, я сильно подозреваю, что для этой задачи можно найти явную формулу (или несколько, в зависимости от условий вида c1 + c2 < n).

Я хотел писать не одно решение, но находил контр-примеры. Думаю, немало упадет.

Problem 3 is solvable in O(N log² N) time (UPD: WRONG). All that we need is to keep track of sizes of subtrees. Let build an heavy light decomposition on the whole tree (with all N vertices). Then after processing vertex i, we will add it to the tree. Adding vertex is equivalent to increasing by one all sizes on the path from the root to this vertex.

Of course, for this problem it is an overkill and during the competition I've implemented O(N²) one :)

You can solve Problem 2 with dynamic programming in O(n). You can count the remaining three pairs from those with higher maximum numbers towards lower. Let's say that pair (x, y), x < y will be the largest. If you fix y, you can choose x from somewhere in the range 1..x'. When you'll have to choose the next pair (a, b), b<y, you know that the range of possible values for a will be 1..a', x' ≤ a'. Therefore, it doesn't matter which x was chosen in the previous step, only how many pairs were chosen before.

In fact you're solving a generalized problem f(k, n) of choosing k pairs from numbers 1..n such that their sum is at most c₁ + c₂. Time complexity is just O(kn). You either use n as a part of the largest pair or not. There are a couple of things to consider, like how to handle used values c₁, c₂ and make sure that x < y, but it can be done.