Задача A (div2):
Очевидно, что нам необходимо делать последовательность ходов вида: 1, 2, 1, 2, ...
Ответ будет примерно равен 2 * n / 3. После этого у нас останется 0, 1 или 2 камня. Если у нас осталось 0 камней, то все закончилось, иначе у нас осталось либо 1, либо 2 камня и очевидно, что мы можем в этих случаях взять только 1 камень.
Итоговый ответ: 2 * n / 3 + (n % 3 != 0 ? 1 : 0);
Задача B (div2):
Мы можем просто симулировать поведение кузнечика и отмечать все позиции, на которых он был. Очевидно, что таких различных позиций будет O(n). Если кузнечик попадет на клетку, где он уже был, то мы попали в цикл, и ответ — INFINITE. Иначе — FINITE.
Задача A(div1)/C(div2):
Давайте заведем 2 матрицы: a, idx. В матрице a мы будем хранить NULL для ячеек, о которых мы ничего не знаем или значение, если мы уже его определили. idx будет инициализировано как idx[i][j] = {i, j}; Затем просто просимулируем процесс для матрицы idx. Для запросов 3-его типа мы можем просто присвоить значение в матрице a, так как мы знаем исходную позицию по матрице idx.
Задача B(div1)/D(div2):
Основная идея задачи в том, что относительный порядок элементов в четных позициях и в нечетных позициях не меняется при выполнении команд с точностью до циклического сдвига.
Давайте хранить позицию для 1ого и 2ого мальчика. После 1ой операции мы сдвинем эти позиции на X или -X. Вторая операция просто поменяет позиции местами (поменяются местами все четные и нечетные позиции, но мы нам это не важно, так как по 1ому и 2ому мальчику можно все восстановить). В конце просто восстановим четные и нечетные позиции независимо и объединим ответ.
Задача C(div1)
Сперва решим обратную задачу: найдем минимум (максимум) от двух распределений. Воспользуемся формулами:
P(a = k) = P(a <= k) — P(a <= k-1) P(max(a, b) <= k) = P(a <= k) * P(b <= k)
Соответственно для минимума:
P(min(a, b) >= k) = P(a >= k) * P(b >= k) = (1 — P(a <= k-1)) *(1 — P(b <= k-1))
Теперь в наших формулах из условия минимум и максимум определяют систему квадратных уравнений для каждой пары P(a <= k), P(b <= k).
Если решить эти уравнения, мы получим P(a<=k), P(b<=k) = (u + v ± sqrt((u + v)^2 — 4u)) / 2, где u = P(max(a,b) <= k), v = P(min(a,b) <= k). Теперь можно заметить, что если ответ существует, то мы тогда существует ответ, когда мы выберем знаки для каждой пары одинаково. (смотри комментарий)
Задача D(div1)/E(div2):
Существует много способов решать задачу. Один из них — SQRT-декомпозиция. Сперва сожмем все времена. Для каждого блока в декомпозиции мы будем хранить баланс для каждого элемента независимо. Ответ вычисляется просто как сумма балансов в блоках меньше того, где находится наше время плюс все балансы в текущем блоке до нашего времени для данного элемента.
Другой способ — воспользоваться структурой данных описаной здесь. Для каждого элемента будем хранить два дерева — дерево времен удалений и добавлений. Тогда по порядковому номеру времени запроса в этих деревьях легко найти ответ.
Задача E(div1):
Построим для обеих формул граф импликаций и найдем компоненты сильной связности в графе. Если обе формулы несовместны, то ответ SIMILAR. Если только одна формула несовместна, то ответ — ответ для второй формулы.
Допустим обе формулы совместны. Построим транзитивное замыкание для графов. Будем называть переменную X фиксированной в формуле F, если существует путь из -> x или (x -> ). Если есть фикированная переменная в одной формуле, но не в другой (или фиксированная, но имеет другое значение) мы можем найти ответ для второй формулы с противоположным значение этой переменной — это и будет ответом. Если мы не смогли найти эти переменные — удалим их все. В оставшемся графе нет фиксированных переменных. Найдем такое ребро u->v, которе есть в одном графе, но отсутствует в другом. Найдем решение для формулы без этого ребра, когда u = 1 и v = 0 (мы всегда можем найти решение). Это и будет ответ.
Задача F(div1):
Будем называть k-клику B потомком k-клики A, если B можно получить из A последовательностью следующих операций: добавить в клику вершину, связанную со всеми вершинами кликами в описании графа и выкинуть ровно одну другую вершину. Посчитаем динамику по состояниям (k-клика, разбиение ее вершин на компоненты), означающую следующее — количество остовных лесов в графе, индуцированном самой кликой и всеми ее потомками таких, что клика разделится по разным компонентам связности согласно заданному разбиению вершин (а все остальные вершины будут связаны с какой-нибудь из этих компонент). Для этого предпросчитаем все разбиения из k и k+1 элементов и переходы:
1) (разбиение k+1 вершин) x (разбиение k+1 вершин) -> (разбиение k+1 вершин | null), переводящее пару разбиений — лесов в набор компонент связности их объединения, или null если появится цикл
2) (разбиение k+1 вершин) x (вершина) -> (разбиение k+1 вершин | null), переводящее лес в новый лес, образованный добавлением ребра из вершины в вершину k+1 (или null, если образуется цикл)
3) (разбиение k+1 вершин) -> (разбиение k вершин | null), проецирующее разбиение на первые k вершин (или null, если k+1-ая вершина образовывает отдельную компоненту)
Детали реализации можно посмотреть в решении автора.
In first problem the formula is (2 * n) / 3 + (n % 3 != 0 ? 1 : 0)
fixed, thank you!
Also in problem E we can create map <int, SegmentTree>, where segment tree is sparse (indexes as time and values as{-1, 0, 1}). If we have query "add/delete value x in time t", we just update tree x in position t by value 1/-1. And "count query x in time t" will be sum of tree x in segment [1,t]. Code.
Auto comment: topic has been updated by AlexFetisov (previous revision, new revision, compare).
Кто-нибуть может сказать за какую сложность работает код?
На КФ отрабатывает за 1.6с
У вектора разве есть запас слева?
Из-за этого прогорели на взломе. В итоге решение прошло.
O(N2)
Но memcpy работает быстрее, чем вы думаете.
Только memcpy, а так да.
memcmp тоже работает быстрее, чем вы думаете :)
deleted
Problem E can easily be done with a Fenwick Tree with a map stored in each node, after compressing the values of time.
Code
It's not necessary to compress values of time. Check this solution.
But that solution's complexity is O(nlog2n), instead O(nlogn) for the solution with compression.
i think that the code provided by zscoder is O(n log^2(n)) how it can be reduced to O(n log(n))?
You can compress the time values to a more feasible rank (let's say [0..n]), and do the same for the rank of numbers added or removed from each time value. Then you can create the Fenwick Trees as arrays, doing queries in log(n) like an usual Fenwick Tree query.
Very sad that we needed to consider discriminant to be less than epsilon(1e-9).It is first time that I met such trick with precision double problem. When I change double to long double it gives unexpected behavior.
"Now we can notice that if there exists an answer, then there exists an answer when we chose the signs for each pair equally" Can you explain this in detail? The comment in the link is in Russian...
I think the reason is the following:
You have computed two values for each k:
big[k]=(u + v + sqrt((u + v)^2 — 4u))) / 2
small[k]=(u + v — sqrt((u + v)^2 — 4u))) / 2
It is clear that big[k]>=small[k].
For each k you know for sure that either P(a<=k)=big[k] and P(b<=k)=small[k], or P(a<=k)=small[k] and P(b<=k)=big[k]. In fact, it follows that big[k]=max(P(a<=k),P(b<=k)) and small[k]=min(P(a<=k),P(b<=k)). You have to make the election for all k so that P(a<=k-1)<=P(a<=k) and P(b<=k-1)<=P(b<=k). Some correct election for all k exists because the statement says that there exists a correct probability. It follows that big[k-1]<=big[k] and small[k-1]<=small[k]. Thus, by choosing P(a<=k)=big[k] and P(b<=k)=small[k] for all k we are done.
Are you going to post the editorial for the last problem?
Yeah, should be out soon
what that swapping means in div2 D? and how it relates,,, posof_1^=1 and posof_2^=2?
но мы нам это не важно,то мы тогда существует ответ, когда,... это гугл переводчик?)Problem B (div2): can't a position repeat without having a loop? if the grasshopper jumps in a pattern in which starting position and ending position isn't same it will eventually jump out of bound!
What's the meaning of "if there is a path -> x or( x -> )" in the solution of Problem E(div.1)?