691A - Берляндская мода
Задачу предложил и подготовил Артур Яворски KingArthur.
В задаче нужно было просто сделать то, что написано в условии.
Сложность: O(n).
691B - s-палиндром
Задачу предложил Никита Мельников nickmeller.
В задаче нужно было аккуратно по картинке определить симметричные буквы, а также заметить, что пары букв (b, d) и (p, q) являются зеркальными отражениями.
Сложность: O(n).
691C - Экспоненциальная запись
Задачу предложил пользователь blowUpTheStonySilence.
Эта реализационная задача. Нужно было сделать ровно то, что написано в условии задачи. На мой взгляд, проще всего было найти позицию первой ненулевой цифры и позицию точки. Разность этих двух позиций равна числу b (если значение положительно нужно вычесть единичку).
Сложность: O(n).
691D - Свопы в перестановке
Задачу предложил Zi Song Yeoh zscoder.
Рассмотрим граф из n вершин, рёбрами которого являются заданные пары позиций. В каждой компоненте связности этого графа мы можем поменять значения в любых двух позициях. Соответственно мы можем все значения отсортировать в порядке убывания. Легко видеть, что полученная перестановка является лексикографически максимальной.
Сложность: O(n + m).
691E - Xor-последовательности
Задачу предложил Zi Song Yeoh zscoder.
Пусть zij — количество xor-последовательностей длины i с последним элементом aj. Пусть gij равно 1 если содержит количество единиц в бинарном представлении кратное трём, и равно 0 в противном случае. Расмотрим векторы чисел zi = {zij}, zi - 1 = {zi - 1, j} и матрицу G = {gij}. Легко видеть, что zi = G × zi - 1. Соответственно, zn = Gn × z0. В силу ассоциативности операции матричного умножения можно сначала вычислать Gn бинарным возведением в степень матрицы и затем умножить полученную матрицу на z0.
Сложность: O(n3logk).
691F - Couple Cover
Задачу предложил Michael Kirsche mkirsche.
Будем считать количество пар с произведением меньшим p. Получить количество не меньших, можно вычитая из общего количества пар n·(n - 1) количество меньших. Пусть cnti количество чисел в a раных i, а zj — количество пар из a с произведением равным j. Для подсчета массива z можно воспользоваться по сути решетом Эратосфена: переберём первое число a, а также кратное ему b = ka и увеличим zb на величину cnta·cntk. После предподсчёта массива z достаточно предподсчитать массив его частичных сумм, чтобы отвечать на запросы о количество пар меньших p.
Сложность: O(n + XlogX), где X — наибольшее значение в массиве p.
For problem D,
Though not necessary , even has a larger complexity and even dsu can be used in a better way to lower complexity I always wanted to use some kind of heuristic in my code 19211367.
Got WA in contest due to some minor major mistake( A mistake that is so minor but changes everything you are doing :P ).
Вопрос по задаче 691D: Как можно доказать, что в связном графе всегда можно отсортировать вершины?
Попробуй доказать это пузырьковой сортировкой. Принцип абсолютно такой же
In case someone faced the same issue. For problem E, my O(n3logk) solution in C# was getting TLE, so I parallelized matrix multiplication and got AC. 19309384
Е можно решать и двоичным подъёмом.
Apologies all for what is probably a silly question.
The solution to 691D includes the line: const int N = 1200300; pti a[N];
I can't find any documentation for a pti datatype. I assume this is an abbreviation commonly used in codeforces solutions? If so can someone link me to an explanation of what this is? Or a solution where the abbreviation is defined.
I had never seen this abbreviation before, but looking through Edvard's submissions, for example, 19489538 you can see it means
pair <int, int>
.I think that problem 691D - Swaps in Permutation have the same concept as problem 500B - New Year Permutation. I use dsu to solve both of these two problems.
Anyway, D is still very good problems I think so. Thanks zscoder.
I think the complexity of problem D is wrong. did you mention the sorting complexity?
why the answer for "mm" is NIE in problem B? isn't "mm" symmetric by the middle? or is it should be odd length string? from where can i infer that from the passage?
Right top corner of 'm' is round but left top corner of 'm' is not round. That's why "mm" is not symmetric.