Блог пользователя Edvard

Автор Edvard, история, 8 лет назад, По-русски

691A - Берляндская мода

Задачу предложил и подготовил Артур Яворски KingArthur.

В задаче нужно было просто сделать то, что написано в условии.

Решение на С++

Сложность: O(n).

691B - s-палиндром

Задачу предложил Никита Мельников nickmeller.

В задаче нужно было аккуратно по картинке определить симметричные буквы, а также заметить, что пары букв (b, d) и (p, q) являются зеркальными отражениями.

Решение на C++

Сложность: O(n).

691C - Экспоненциальная запись

Задачу предложил пользователь blowUpTheStonySilence.

Эта реализационная задача. Нужно было сделать ровно то, что написано в условии задачи. На мой взгляд, проще всего было найти позицию первой ненулевой цифры и позицию точки. Разность этих двух позиций равна числу b (если значение положительно нужно вычесть единичку).

Решение на C++

Сложность: O(n).

691D - Свопы в перестановке

Задачу предложил Zi Song Yeoh zscoder.

Рассмотрим граф из n вершин, рёбрами которого являются заданные пары позиций. В каждой компоненте связности этого графа мы можем поменять значения в любых двух позициях. Соответственно мы можем все значения отсортировать в порядке убывания. Легко видеть, что полученная перестановка является лексикографически максимальной.

Решение на C++

Сложность: 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.

Решение на C++

Сложность: 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.

Решение на C++

Сложность: O(n + XlogX), где X — наибольшее значение в массиве p.

Разбор задач Educational Codeforces Round 14
  • Проголосовать: нравится
  • +47
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 ).

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Вопрос по задаче 691D: Как можно доказать, что в связном графе всегда можно отсортировать вершины?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Попробуй доказать это пузырьковой сортировкой. Принцип абсолютно такой же

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Е можно решать и двоичным подъёмом.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I had never seen this abbreviation before, but looking through Edvard's submissions, for example, 19489538 you can see it means pair <int, int>.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think the complexity of problem D is wrong. did you mention the sorting complexity?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Right top corner of 'm' is round but left top corner of 'm' is not round. That's why "mm" is not symmetric.