В K мои сокомандники сдали решение за O(n²logn) так, что куб наверное не предполагался.

Я полконтеста пытался подобрать тест против куба — не получилось :( Возможно даже, что его и нет. Авторское решение работает за

по K — да, тесты оказались отстоем, мне стыдно. Сейчас сломал некоторые кубические решения.

Все-таки смогли завалить решение за куб. Возможно этот тест появится в дорешке.

Как в J хранить предков, они же в 64MB памяти не влезают?

В J можно не хранить предков, а сразу поддерживать ответ, благо множество взятых "предметов" помещается в двух лонгах

Вы же её сдали? Из каждой вершины запускаем Дейкстру за квадрат. Смотрим те рёбра которые ведут в разные поддеревья корня дерева кратчайших путей или в корень, и ими апдейтим ответ.

У нас вероятностное решение. Выберем вершину, будем временно удалять ребра из нее с вероятностью 1/2 и пускать Дейкстру. После этого пробуем идти по дереву кратчайших путей и возвращаться по одному из удаленных ребер. Каждая итерация находит правильный ответ с вероятностью как минимум 1/2.

А как получить? Можете хотя бы вкратце описать решение?

Наше решение, видимо, чересчур сложное, но использует лишь памяти (если точно, то 2¹⁴·2⁶ long long-ов), решим сперва для полностью пустой полоски:

1. Пусть n = 2k + 1. Заметим, что стоящие рядом числа отличаются по крайней мере в два раза. Отсюда следует, что числа k + 1, k + 2, ..., 2k + 1 ("большие") стоят на нечётных позициях, числа 1, 2, ..., k ("маленькие") на чётных.
2. Заметим, что любое число, не большее ни на что не влияет — куда бы на чётную позицию мы его не поставили, противоречия это не создаст. Назовём такие маленькие числа "плохими", остальные маленькие "хорошими". Хороших 6 для n = 27.
3. Будем ставить большие числа на нечётные позиции в убывающем порядке и делать динамику dp[mask][mask_good] — количество способов получить из уже поставленной позиции корректную, где mask — маска уже занятых нечётных позиций, mask_good — маска использованных хороших чисел. Когда мы ставим очередное число, оно минимальное среди уже поставленных. Это значит, что содержимое чётной позиции можно определять, когда оба соседа уже поставлены и оно будет ограничено половиной только что поставленного соседа. Соответственно, когда ставим большое число на какую-то нечётную позицию, смотрим, какие из соседних чётных позиций стали иметь двух занятых соседей и перебираем, что мы на эти позиции поставим — плохое число (неважно какое, они (пока) все для нас одинаковы, а оставшееся их количество из mask и mask_good определяется однозначно) или одно из свободных хороших.
4. Таким образом, мы решили задачу для пустой изначальной доски. Для непустой изначальной доски надо аккуратно перебирать, кого мы поставим, чтобы случайно не пропустить заработанное противоречие (мы поставили не того, кого должны были или поставили какое-то плохое число не туда и не отследили этого, так как помнили только их количество).
5. Памяти , времени c небольшой константой.

Есть очень простое решение за 2^k

Если мы узнаем число, загаданное сервером — сможем легко выиграть.

Чтобы узнать число, загаданное сервером, достаточно сыграть около 40 раз — мы получим последовательность проигрышей и выигрышей, которая однозначно задает число (конечно, в связи со спецификой генератора чисел).

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

Binary search do not work in this problem. Say for 1,1,100,100 and w=103 you can choose l=2, but for l=3 it won't fit

https://www.dropbox.com/s/gulwb6ec5drwftx/problems-e-010342.pdf?dl=0

O can be solved in O(1) by precalculations (only 512 answers) or O(n) finding solution directly. cycling from 1 to 2500000 and count how much acceptable integer founded. In C++ checking int would look like this:

while(i!=0)
{
	if(abs(i%10 - ((i/10)%10))!=1 && i/10!=0)
		return false;
	i/=10;
}
	return true;

Q is simple DP with checking for traps. dp[i] = min {dp[i-j], ..., dp[i-1]}+1

Notice that a + b and a - b have the same parity. Let S = 1 + 2 + .. + n, then x and S should give the same remainder mod 2. And x must be not greater that n, because |a - b| ≤ max(a, b) for any positive integers a, b.