У Вас есть логин OpenCup? Совершенно точно будет тренировка на сервере OpenCup. Насчёт онлайн-зеркала не уверен.

Видимо онсайтом в Тбилиси

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

Если n четно, у второго игрока есть симметричная стратегия: повторять ходы симметрично относительно центра. Если нечетно, первый игрок ходит в центр и такая же симметричная стратегия.

Мы в I сдали O(10 × T × N × M). Находим самый верхний левый включенный пиксель и перебираем цифру, которую пытаемся поставить туда, теперь повторяем это, но уже с выключенными пикселями. Самое сложное — захардкодить циферки.

Мы без FFT, но с Фенвиком. Восстанавливаем ответ по битам. Пусть мы хотим восстановить бит 2^k - 1, где . Тогда начнём идти слева направо и подсчитывать текущую сумму на префиксе по модулю 2^k. Чтобы сумма на каком-то отрезке получила единицу в нужном бите, нужно, чтобы она была больше или равна 2^k - 1 (по модулю). Теперь после добавления очередного элемента нужно всего лишь посчитать количество сумм на префиксах в каком-то зацикленном отрезке, что делается запросами к дереву Фенвика. Итого с очень хорошей константой и линейной памятью.

Говорят, FFT получало ТЛ.
Мы сдали такое решение: сумма на отрезке [i;j] — s_j - s_i - 1, где s — массив префикс-сумм. Будем решать задачу по каждому биту отдельно, проверять, присутствует ли он в ксор-сумме ответа. Для каждого значения s_j нужно посчитать, сколько есть подходящих i ≤ j. Для этого можно использовать бор: если мы проверяем бит k, то будем добавлять в него младшие k - 1 бит каждого числа s_j, и посчитаем для всех вершин в боре v динамику cnt[v][0|1] — число листьев в поддереве v таких, что k-й с конца бит соответственно равен 0|1. Зная эту величину, можно посчитать число подходящих индексов i, спускаясь по дереву — нужно разобрать несколько случаев. В конце получается что-то вроде такого: если сейчас k-й бит равен x, и спускаемся по ребру, на котором написано y, нужно добавить cnt[v->!y (противоположное ребро)][x ^ y]. Итого — O(nlog²n).

Я писал FFT(2 запуска на тест), и это аксепт. А как за один? З.Ы. Была похожая задача, только там нужно было посчитать

Unable to parse markup [type=CF_TEX]

Unable to parse markup [type=CF_TEX]

1. Любые два непересекающихся по внутренности выпуклых многоугольника можно разделить прямой
2. Прямая высекает на окружности некоторую "шапку", каждая шапка однозначно задаётся своей высотой от 0 до 2R
3. Отдельно для каждого многоугольника найдём минимальную высоту шапки и проверим, что сумма не более 2R
4. Рассмотрим оптимальную шапку. Если на дуге лежит меньше одной вершины многоугольника, то его можно сдвинуть и шапка не минимальна.
5. Если на дуге лежит хотя бы две вершины многоугольника (не обязательно соседние, прошу заметить), то их можно за квадрат перебрать, однозначно восстановить окружность, а потом за линию проверить, что все точки действительно лежат внутри окружности (этого достаточно, чтобы многоугольник лежал внутри). Если это так, то нетрудно показать, что минимальная "шапка" касается окружности с центром в центре изначальной и касающейся нашего многоугольника. То есть нужно найти расстояние от центра окружности до многоугольника и проверить, лежит ли он внутри или снаружи — это делается двумя циклами (один ищет расстояние до сторон, как до отрезков, а второй ищет минимум ориентированного расстояния до сторон многоугольника).
6. Случай попроще. Если ровно одна точка лежит на дуге — то попробуем сдвинуть его влево или вправо, а потом вверх. Если не можем — значит, упёрлись, причём это могло произойти только если вершина многоугольника оказалась в середине дуги. Попробуем повернуть многоугольник. Если получилось, то низ чуть-чуть поднялся и шапка не минимальна, а если не получилось — срез шапки проходит через сторону многоугольника. То есть опять можно за квадрат перебрать пару (вершина, сторона) и попробовать запихнуть многоугольник в конкретную шапку.

Стандартная динамика. Состояние — мы уже восстановили какой-то префикс s, при этом максимальный суффикс, совпадающий с каким-то префиксом BOB имеет длину k (да, как в КМП).

После этого делаем один или два перехода, соответствующие буквам.

Чтобы посчитать динамику один раз и быстро отвечать на запросы, состояние делаем с правильной стороны: уже поставили x букв одного типа и находимся в позиции pos. Количество поставленных букв другого типа автоматически восстанавливается. Чтобы ответить на запрос, нужно взять лучший из ответов для pos = |S| и n - X ≤ x ≤ X, что делается Фенвиком.

Да, мне тоже интересно. Я почему-то думаю, что все сдали перебор, поправьте меня "все", если я не прав. =)

Отсортируем рюкзаки по убыванию веса. Очевидно, что надо использовать несколько самых больших. Будем заполнять сначала самый большой рюкзак, потом следующий и так далее. Динамика для подмножества: количество рюкзаков, которые придется заполнить, и вес, использованный в следующем (минимизируем первое, при равенстве второе). O(n2ⁿ)

Да, может быть, есть какой-то шанс, что контесты будут добавлены здесь в тренировки?

Перейдем от количества в коробках к количествам в префиксе, тогда определить в i коробке будет Si -S(i-1). Префиксов n+1 штука(включая нулевой), даны ребра — веса для перехода. Построить граф, найти на нем остовное дерево.