Или можно динамикой (наибольшее добавленное число баллов, уже добавленное подмножество 6 чисел, остаток). Идём в порядке увеличения баллов.

Еще можно перебрать перестановку 6 чисел и искать строго возрастающую последовательность баллов двумерной динамикой.

Я вначале писал meet-in-the-middle но не завелось, и мы сдали с перебором перестановок. можешь дать код посмотреть?

Задача имеет решение для всех K, даже нечётных =)

для K=2 ответ

4

rev 1

rev 2

out 1

out 1

Разделим на 2 кучки, в первой K штук, во второй (N — K). В данной задаче N = 18 Пусть в первой перевернутых X штук, тогда во второй — K — X Перевернем все в первой, получим, что в ней K — X перевернутых, и получено решение.

Для этой задачи надо было бы сделать нормальный семпл, мы тоже подумали, что размеры кучек должны быть одинаковыми. Потом третий участник прочитал задачу, и она была сразу же сдана.

B — очень просто

В I мы писали двумерное Фурье.

В G перебор подмасок с некоторыми нетривиальными оптимизациями прошел.

В I команда ИжГТУ находила 10.000 прямоугольников с максимальной суммой, и потом считала сумму по маске в этих прямоугольниках.

В задаче B я писал многочлен Лагранжа. 20 секунд на локальном компьютере.

В I я сдал обычное Фурье посчитанное от всех строк исходной и строк образца... Правда оно еле влезло в ТЛ =/.

Зачем в I двумерное Фурье? Одномерного достаточно — нужно произведение \sum a_{i,j} x^{im+j} и \sum b_{i,j} x^{mn — (im+j)} (где m — ширина большого поля).

А можешь пояснить что ты имеешь в виду под двумерным Фурье? Это обычный Фурье только для полинома получающегося из таблицы выписыванием строк сверху вниз?

Определение вполне случайного графа так и не обнаружилось, зато выяснилось некое важное свойство таких графов. Для вполне случайных графов заходит обычный Кун. Вы конечно можете возразить, что это свойство не графов, а тестов, но разве в див-2 такое возможно?)

Зато история с массовыми ok'ами по этой задаче проясняется)

Сдали за n sqrt(n) log(n), отдельно рассматривая случаи, когда A и B маленькие, и когда хотя бы одно из чисел большое.

Будем рассматривать три возможные нумерации фотографий:

1) исходную

2) такую, чтобы все запросы на +1 были на отрезке (то есть чтобы элементы, которые были на расстоянии A, оказались рядом)

3) аналогично с B.

Во второй нумерации будем хранить sqrt-декомпозицию, позволяющую добавлять на отрезке и узнавать в точке. Третью нумерацию разобьем на отрезки по sqrt(n). Для каждого из них будем поддерживать сумму. Предподсчитаем для каждой пары (отрезок в третьей нумерации, префикс во второй нумерации) количество общих элементов. При запросе на изменение, надо добавить 1 на отрезке во второй нумерации и добавить к каждому отрезку в третьей нумерации размер его пересечения с отрезком запроса. При запросе на сумму, сложим ответы для всех целиком попадающих в отрезок отрезков в третьей нумерации и добавим сумму остальных элументов, пройдя по ним и посмотрев значения в sqrt-декомпозиции. O(N sqrt(N)). Фух, в голове намного проще, чем текстом :)

Сначала вместо sqrt-декомпозиции использовал дерево отрезков, и было O(N sqrt(N) log(N)), не смог запихать.

Меня наоборот улыбнули истории про Иру :D Да и задачи вроде интересные были =)

Мы сдали за N*sqrt(N)*С, где C — обращение к мапу.

Идея предельно простая и выше уже обсуждалась: разобьём запросы на блоки размером sqrt(N).

Тогда вначале каждого блока мы можем пересчитать ответ за линию для всех остатков деления на A и на B.

Тогда при запросе суммы мы уже знаем ответ для всех запросов, которые были до текущего блока запросов, а из этого блока мы можем легко добавить, пробежавшись по этим запросам и взяв из мапа сколько у нас элементов с указанным остатком деления на B пересекаются с остатком деления на A из запроса на добавление.

Фигня, конечно, но зашло. Код: http://pastie.org/3465337

Сдал в дорешке за n*sqrt(n). Рассмотрим 4 случая. Если A, B > sqrt(n) все просто. Если A > sqrt(n), будем бегать через A и плюсовать у встречаемых ост по % B. Если B > sqrt(n), будем хранить для каждого ост по % A, сколько раз его плюсовали, ответ на запрос суммы — пробег с шагом B, суммируя кол-во плюсов у ост по % A. Если A, B < sqrt(n), то найдем для каждого ост по % A, сколько раз встретится каждый ост по % B, если начнем бежать с шагом A от него. Тогда обновление — пробег по массиву встречаемых ост и суммирование кол-ва их встреч.

F — попробуем получить наше число как OR отдельных битов, использующихся в нём. Для получения i-ого бита возьмем все числа, которые его содержат, и возьмем их AND. В результате получится маска, которая содержит i-ый бит и возможно что-то еще. Если это "что-то еще" полностью содержится в числе (является его подмаской), смело берем его. Если это верно для всех битов числа — Yes, иначе — No.

Heard of Nim?

The problem won't change much if you replace K with 18 — K. According to the constraints (K <= 18, output length <= 2^9+36) a simple brute force checker should suffice: binom(18,9)*2^9 ≈ 25 millions, a factor of 18 being avoided by bit hacks