Кубок существует в реальности, будет отправлен как-то (по итогу контеста решим, как).

Изначально планировался опенкап, но в силу некоторых причин опенкап не случился. Систему проведения "зеркала" не поменяли, можно сказать по привычке.

Потому-что на Codeforces и так проводилось много разнообразных чемпионатов,от них все уже сильно устали. Хотя да, на КФе было бы гораздо лучше.

Yes.

No.

Now you can find link in the post.

Добавили ссылку в пост. Контест заливался вчера-сегодня.

аналогично

The same.

Everyone here is experiencing the same problem.

Условия доступны в посте

My solution is O(nx³). It is obvious, that we should start by solving tasks, that will add 0 to utility. Only after that we will start solving other ones. The order doesn't matter for the first part and for the second part we should solve the one with higher a. Now, let's just iterate over the debt X after first part and calculate the best result with DP[i][j][k] — best utility that we can get by solving tasks starting with i, so that we reduce debt for the first part to j and to k for the second part having the debt after the first part exactly X.

F: по каждому циклу отдельно, там внутри вполне очевидный Фурье. Не забыть хранить "свёрнутые" Q-шки по разным длинам, их там не так много, а лишний N^2 получить не хочется.

H: Подвесим дерево. Для каждой вершины вычислим сколько раз 1-ая технология встречается по пути от корня до неё, пусть это F(X). Научимся находить кол-во первой технологии на пути от неких A до B: пусть общий предок C и его родитель D, тогда кол-во первой технологии будет f(A) + f(B)-f(C)-f(D). Получается нам нужны пути у которых это выражение равно единице. Обобщаем на M технологий: для каждой технологии берём некое случайное hash(X), и в каждой вершине храним суммы этой функций по всем технологиям встречающимся от корня. Нам нужен путь у которого выражение будет равно сумме всех этих случайных значений. Его можно найти динамикой по поддеревьям с слиянием меньшего множества к большему.

BTW, it can be solved using only integer arithmetics.

Хоть бы ссылку дал :) Не все же знают, кого ты цитируешь.

Заметим, что вероятность выигрыша Саши, при условии что мы знаем всего его карты и выбранный им цвет color, зависит только от количества карт цвета 0 и цвета color у него в руке. Чтобы посчитать эту вероятность, нужно перебрать количество карт цвета 0 и цвета color среди открытых y верхних карт колоды и просуммировать вероятности тех событий, при которых Саша выиграет.

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

Замечания:

• итоговая асимптотика O(n⁴), где n -- общее количество карт в колоде;
• понятно, что для сравнения вероятностей недостаточно считать по модулю 10⁹ + 7;
• вероятности выигрыша могут быть одинаковыми — договоримся, что Саша выбирает минимальный по номеру цвет и исправим решение;
• вероятности выигрыша могут отличаться меньше чем на 1e-12 (или даже еще меньше) — либо считать абсолютно точно в рациональных числах с длинной арифметикой, либо считать в double и при сравнении на равенство проверить равенство по модулю 10⁹ + 7
• у жюри есть решение на джаве с длинной арифметики; кстати, оно работает быстро и укладывается в TL.

Да. Но недели через две-три — программный комитет разъехался в отпуска, а там есть некоторая работа по вёрстка html для тимуса.

This is how I solved.
F(0) = 0; F(1) = 1; F(n) = F(n — 2) + F(n — 1). Then matrix 2x2:

F(n — 1) F(n)
F(n) F(n+1)

is n-power of matrix:

0 1
1 1

There is property: det(AB) = det(A)*det(B), if A and B — same size square matrixes.
det([0 1; 1 1]) = -1 => det(([0 1; 1 1])^n) = (-1)^n => F(n)*F(n) — F(n — 1)*F(n+1) = (-1)^n
We are given p and x. If x = F(n) the we need find F(n + 1) = F(n — 1) + F(n). Assume F(n) = x. Then we've got modular equation:

a*(a+x) — x*x = (+/-)1 (mod p)
a*a + a*x = x*x (+/-) 1 (mod p) | *4
4*a*a + 4*a*x = 4*x*x (+/-) 4 (mod p) | +x^2
4*a*a + 4*a*x + x^2 = 5*x^2 (+/-) 4 (mod p)
(2*a+x)^2 = 5*x^2 (+/-) 4 (mod p)

Now we need find sqrt(A) mod p. This is standart algorithm. This. O(sqrt(p)*log(sqrt(p))).

This is how we find at most four values for a. Then we need to check whether matrix
[a x; x (x + a) mod p] power of [0 1; 1 1] mod p. This is standart algorithm too (This. Brute-force says power can be at most 2*p. O(sqrt(p)*log(sqrt(p))).

So we found all values of a.

P.S. There are two corner cases: p = 2; p = 5. (Both algorithms works on odd prime p. For p = 5 power can be at most 4*p).
P.P.S. There is more easy way?

Problem link : http://acm.timus.ru/problem.aspx?space=1&num=2085