Посмотрим на матрицу, домножением на которую является это преобразование. По каким-то причинам, в ее степенях вида 2^k в каждой строке и столбце не более, чем 2 не нуля. (видимо примерно по тем, которые ты описал). Значит, ее можно возводить в квадарт за линию. Перемножить получится за O(logT * n), если перемножать со столбцом, а не матрицы между собой и потом на столбец.

Я думаю, все же речь идет о гамильтоновом пути, а не о эйлеровом. Мы сдали такое, напишем обычный перебор, только перебирая очередной переход, сначала пытаемся выбрать такие, которые добавляют в маску единичку, а потом только убирают. Как-то так

OOPS: Задачка оказалась проще, а мы находили гамильтонов путь, в графе, где ребра это вершины и наоборот =)

Обычный эйлеров путь заходит, если не перебирать в каждой вершине 18 исходящих ребер (что работает за 18² * 2¹⁸), а сразу удалять использованные ребра. Наверное, еще возможны проблемы с большим выводом.

Проще всего пройти все переключатели кодом Грея, затем идти по нему же назад, проходя в каждой вершине по всем ребрам, не принадлежащим коду Грея, вперед и назад.

Мы написали честный эйлеров цикл: обходим весь граф dfs'ом (2¹⁸ вершин), при выходе из вершины добавляем ребро, по которому выходим, в ответ. Так как для каждого ребра есть симметричное, то всё равно, идти ли по обратным или по прямым.

У нас еще локально падал стэк, написали dfs на ручном стэке.

Мы писали следущее: Будем поддерживать точку в виде линейной комбинации x0,y0,1. Проецируем честно n раз. Далее решаем гаусса 3 на 3(условие того, что мы пришли в исходную точку и что точка лежит на исходной прямой)

Простой тернарный поиск проходит. Тернарный поиск запускаем по x-координате первой прямой. Если же первая прямая имеет вид x=C, то запускаем по y-координате.

Задаем точку-ответ параметрически по первой прямой: At+B. Проецируем n раз, получаем уравнение A_n*t + B_n = A*t + B, оно линейно по t, решаем.

UPD: t = (B.x — B_n.x) / (A_n.x — A.x) если (A_n.x — A.x != 0)

1. Можно не удалять вершину, а помечать ее 0/1, и считать сумму на пути до корня.

2. Первым проходом сделаем все операции с деревом, не обращая внимания на глубины.

3. От полученного дерева построим структуру данных, которая за logn умеет изменять вес вершины и за те же logn искать сумму на пути до корня. Например изменить вес вершины: += к поддереву, а это += на отрезке.

Мы честно хранили эйлеров обход в декартовом дереве. Тогда высота — это сумма на префиксе. А все операции это какие-то доваления/удаления ребер.

Напишем перебор =) Можно доказать, что есть всего два варианта перехода: взять предыдущий элемент, который мы уже взяли или взять 2S + 1, где S текущая набранная сумма. Ну и, естественно, мы отсекаемся, когда S становится больше N.

код

PS: Ну и первым всегда берем 1.

Вот так

Если подробнее. В отсортированном ответе каждое число равно либо предыдущему, либо удвоенной сумме предыдущих + 1.

Почему это так. Из чисел любого префикса можно получить все до суммы. По индукции. Почему не подходит другое. Если очередное число больше, то нельзя получить N — 2*sum — 1. Если меньше, то x — Sum можно получить двумя способами.

Перебор отрабатывает быстро, потому что написали и проверили.

Каждое новое число, не равное предыдущему, равно 2S + 1, где S~--- сумма всех предыдущих. Это значит, что N = S + k(2S + 1), или 2N + 1 = (2k + 1)(2S + 1). Поскольку первые числа дают хорошее множество с суммой S, верно, что 2S + 1 = (2k' + 1)(2S' + 1), и т.д. В итоге 2N + 1 = (2k + 1)(2k' + 1)(2k" + 1)..., т.е. какое-то разложение 2N + 1 на нечетные множители. Поскольку длина ответа равна k + k' + k" + ..., и мы ее минимизируем, это разложение на простые множители в каком-то порядке.

Пример: N = 52, 2N + 1 = 105 = 3 × 5 × 7.

52 = 1 + 3 + 3 + 15 + 15 + 15

52 = 1 + 3 + 3 + 3 + 21 + 21

52 = 1 + 1 + 5 + 15 + 15 + 15

52 = 1 + 1 + 5 + 5 + 5 + 35

52 = 1 + 1 + 1 + 7 + 21 + 21

52 = 1 + 1 + 1 + 7 + 7 + 35

С задачей А меня больше всего убивает тот факт, что она решается абсолютно так же, как и задача про гирьки с прошлогоднего же ICL с точностью до косметических изменений.

Её вполне можно решить без перебора. Рассуждаем следующим образом. Упорядочим веса существующих гирек по возрастанию — w₁, w₂, ..., w_k. Пусть гирек веса w_i у нас a_i штук. Тогда любое состояние весов описывается вектором (x₁, x₂, ..., x_k), где  - a_i ≤ x_i ≤ a_i, причём по условию соответствие взаимно однозначное. С одной стороны мы должны уметь взвесить все веса от  - N до N, которых 2N + 1 штук. С другой, всевозможных векторов — (2a₁ + 1)(2a₂ + 1)... (2a_k + 1). Значит, 2N + 1 = (2a₁ + 1)(2a₂ + 1)... (2a_k + 1).

Дальше замечаем, что при фиксированных a₁, a₂, ..., a_k веса w₁, w₂, ..., w_k восстанавливаются однозначно (w₁ = 1, а каждый последующий должен быть на единицу больше удвоенного максимального веса, который можно получить предыдущими).

Значит, нам надо найти все разбиения, при которых . С другой стороны, каждое разбиние — это какое-то разложение 2N + 1 на множители. Теперь надо понять, что для минимизации суммарного количества гирек множители в разложении должны быть простыми. Это следует из следующего неравенства: пусть у нас есть множитель (2a_i + 1) = (2x + 1)(2y + 1). Заменим это a_i на x и y — тогда , т. е. выгодно разбить составной множитель на два простых.

Ну и выходит, что каждое разбиение однозначно соответствует какой-то перестановке строки p₁, p₂, ... p_u, состоящей из простых множителей 2N + 1 с учётом кратности. По перестановке ответ восстанавливается простым проходом за O(u). Получилось решение за факторизацию плюс перебор перестановок простых множителей.

Мне очень нравится эта красивая математическая конструкция, только не очень нравится тот факт, что я дословно те же рассуждения проводил год назад, писал дословно то же решение, и даже исправлял по ходу написания те же баги :-)

У меня вот был какой-то не совсем перебор.

Факт 1: Всегда нужно взять 1.
Док-во: Иначе мы не сможем взвесить N-1.

Факт 2: Если отсортировать гирьки по неубыванию веса, то первая гирька — 1, а (k+1)-ая либо равна k-ой, либо равна 2S+1, где S — сумма префикса длины k.
Док-во: Будем доказывать по индукции, попутно поддерживая тот факт (2*), что гирьками с префикса можно единственным образом взвесить все массы до S включительно.
База индукции верна (из факта 1). Пусть k-ая гирька была веса Х, мы хотим поставить гирьку веса Y. Нам нужно показать, что либо Y=X, либо Y=2S+1. Очевидно, Y>=X. Пусть Y>2S+1. Тогда мы не сможем взвесить N-(2S+1). Пусть X<Y<2S+1, тогда либо Y, либо Y-S представимо не одним способом. Док-во (2*) очевидно.

Теперь пусть мы поставили k единиц (а затем не единицу). Тогда по индукции очевидно, что далее на любом префиксе S = k (mod (2k+1) ), а так же любой последующий элемент делится на (2k+1). Если N-k не делится на (2k+1), то для такого k решений нет. Иначе выкинем все единицы, а так же разделим все на (2k+1).
Теперь нам нужно решить ту же самую задачу для (N-k)/(2k+1).
Напишем ленивую динамику, получим АС.

Я решал в общем виде, вычисляя операции, которые необходимо провести со списком бактерий, чтобы получить позицию через 2^k секунд. Пример для пяти бактерий:

При этом каждая следующая операция вычисляется применением предыдущей операции к самой себе. Например, если мы применим a0+a2 (третья строка) к самой последовательности, то получим a0 + a2 + a0 + a4 = a2 + a4. Итоговый ответ получается последовательным применением операций для нужных степеней двойки к исходной последовательности бактерий.

В задаче M нами была обнаружена предположительная ошибка в тестах. В условии сказано, что до символа ':' цифр нет. Мы парсили через istringstream путем замены всех не цифр на пробелы. С правильным решением получали WA 2. После контеста мы считывали числа после ':' и получили OK. Проверили assert-ом наличие цифр до двоеточия и оказалось что они там есть. Подали апелляцию на эту задачу, надеюсь на rejudge.