Where can we find the problems?

H: Let's find a dfs search forest (from some vertices in each connected component). If it contains a path of length k + 1, print it. Otherwise, color each vertex with it's depth in the corresponding dfs tree.

Any ideas for problem I?

Who has proofed solution of H?

I do not know which solution did you mean, but my solution is proved by design.

Let's start coloring vertices using dfs. Each time we'll try to find such color C that is not used by neighbours, but color (C-1+K)%K is used. When paint vertex in this color C and remember neighbour with color (C-1+K)%K as previous for current vertex.

If we do not fail on such painting process, we have a graph's coloring. Otherwise, we failed on painting of some vertex v. That does mean, it neighbours uses all the colors, including color K-1 (0-based), so there is adjusted vertex u witch has color K-1. Here is some simple path from vertex u which is constructed by walking to previous vertices, and it's length is not less than K-1, so by adding edge u->v we have sought-for path with length K.

Ребята! Подскажите, пожалуйста, как A решать? (div1) Падает на 29ом хоть убей

How to solve C?

E: Main idea: number of ways to divide subset only depends on count of vertices. We can use DP to calculate it for every size.

dp[0] = 1;
for (int i = 2; i <= n; i += 2)
{
	for (int j = 1; j <= i; j++)
	{
		for (int h = j + 1; h <= i; h += 2)
		{
			dp[i] += dp[h - j - 1] * dp[i - (h - j - 1) - 2];
		}
	}
}

Let's find first pair in subset. Sort all possible pairs and iterate over them. We need to know number of ways with this fixed pair in order to choose, take this or not. Number of ways depends only on size of left and right subset. Find this pair and recursively solve at first for left and then for right subsets.

What about I? We had 2^32*const solution, it was too slow, like 45 seconds instead of 5

I've seen several "read a paper" problems in Open Cup but I've never solved it. How do you solve it?

Search, read, understand, and implement a 10-page paper during a contest looks overwhelming to me. Is it important to find an easy-to-read article? Do you know the algorithm beforehand? Are you actually very good at reading papers?

Отвечаю про задачу I (shuffle-twice и упрощённый вариант shuffle-again для Div2). Отдельным комментарием, потому что вопросы на английском, а ответить я сейчас готов только на русском.

Обозначим исходное состояние генератора как x₀, а все последующие как x₁, x₂, x₃, ....

Заметим, что за один shuffle каждое число участвует в одном обязательном swap-е: в тот момент, когда на него указывает индекс цикла. При этом число перемещается на неотрицательное расстояние влево. После этого число может попасть в другие swap-ы, каждый из которых перемещает его на положительное расстояние вправо.

Сначала решим задачу shuffle-again (Div2-версию): как восстановить seed после одного вызова shuffle. Легко понять, что последнее число участвует ровно в одном swap-е. Поэтому его позиция позволяет нам установить x₁₀₀₀₀·10000 div 2³². Более того, если мы обратим последний swap, то по аналогичным причинам предпоследнее число участвовало ровно в одном из оставшихся swap-ов, и мы можем узнать x₉₉₉₉·9999 div 2³², и аналогично далее: x₉₉₉₈·9998 div 2³², x₉₉₉₇·9997 div 2³², ....

Научимся по следующему состоянию генератора находить предыдущее: если x_k + 1 = x_k·a + c, то x_k = (x_k + 1 - c)·a^- 1 (оба равенства — сравнения по модулю 2³²). Для этого нужно всего лишь обратить число a по модулю 2³².

Заметим, что, если мы знаем x₁₀₀₀₀·10000 div 2³², это оставляет нам всего около 2³² / 10000 возможных вариантов для истинного значения x₁₀₀₀₀. Переберём их все. Для каждого будем вычислять x₉₉₉₉, x₉₉₉₈, ... и сразу проверять, что числа x₉₉₉₉·9999 div 2³², x₉₉₉₈·9998 div 2³², ... такие, как у нас получились. Для каждого значения x₁₀₀₀₀ мы либо пройдём все эти проверки, либо очень быстро (за 1-2 шага) найдём проверку, которая выдаст ошибку. Поэтому суммарное время перебора будет близко к 2³² / 10000. Как только мы найдём такое x₁₀₀₀₀, для которого пройдём все проверки, соответствующее ему x₀ и будет искомым значением seed.

Решим теперь задачу shuffle-twice с двойным перемешиванием. Теперь каждое число участвует не менее чем в двух swap-ах. Откуда вообще мы можем получить информацию? Нам хотелось бы найти число, которое редко двигалось — тогда, может быть, мы перебором сможем найти, как именно оно двигалось. Поэтому будем искать такие числа, которые участвуют ровно в двух swap-ах, а не больше. Можно экспериментально проверить, что таких чисел примерно 1 / 6 от общего количества.

Будем рассматривать числа, начиная с конца перестановки. Пусть очередное число не меньше своего индекса, например, p₉₀₀₀ = 9876. Предположим, что число 9876 участвовало ровно в двух swap-ах: в момент 9876 оно переместилось на позицию mid, а в момент 10000 + mid — на позицию 9000. Переберём все возможные значения mid от 9000 до 9876 включительно.

При зафиксированном значении mid у нас есть два сравнения по модулю следующего вида (*):

x₉₈₇₆·9876 div 2³² = mid,

x_{10000 + mid}·mid div 2³² = 9000.

Предположим, мы научимся быстро находить все решения такой системы - а при достаточно больших модулях 9876 и mid их обычно не больше пары сотен. Тогда все x₀, соответствующие этим решениям, являются кандидатами на правильное значение seed. Проверять правильность seed для всех них может всё ещё быть долго, поэтому будем складывать x₀ в set и проверять только для тех, которые попали в set во второй раз. Когда мы в переборе в первый раз найдём две верные гипотезы вида (*), проверка подтвердит правильность найденного x₀, и мы сможем вывести ответ.

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

Возможно, если хорошо организовать перебор на этапе поиска чисел, участвовавших ровно в двух swap-ах, может хватить и медленного решения системы двух сравнений: перебора решений одного сравнения за 2³² / mid и проверки, подходят ли они по второму сравнению.

How to solve G?

Had solved stringy problem 'J' (about timer) with Perl, 127 lines (ideone).

Anyone know how to solve problem I?