Как решить задачу на C++ быстрее чем за n^2?

Question

[Proshka17]

Текст задачи (большие изображения!)

Я придумал несколько решений, но все они так или иначе n^2 по сложности.
Например, можно использовать односвязный список и хэш таблицу с указателями на ноды списка для шифрования. Но чтобы получить номер нода в списке, придется пройтись по списку, а это уже n^2.
Можно ли решить эту задачу быстрее?

Comments

[Wataru]

Советую такие вопросы в тег "алгоритмы пихать".

[Роман]

А в условии есть еще примеры ввода и вывода?

Answer 1

[Wataru]

Есть за O(n log m) решение, но оно технически сложноватое. Реализуется через балансированное бинарное дерево поиска с неявным ключем. Грубо говоря, если в каждой вершине балансированного дерева хранить сколько всего вершин в поддереве, то в такой структуре можно искать вершину по номеру. Можно так же в это дерево вставлять вершину на заданную позицию.

Еще для шифрования надо поддерживать массив указателей для каждого числа на вершину в дереве, где оно хранится. Еще надо поддерживать указатели на вершину отца.

При шифровании, получив число, вы по указателю находите, где вершина в дереве. Поднимаясь вверх, проверяя из правого или левого поддерева вы пришли можно подсчитать какая ваша начальная вершина в дереве по счету. Это число и выводите в ответ. Потом удаляете вершину из дерева и вствляете в начало.

При расшифровке - прочитанное число указывает на порядковый номер вершины в дереве. Находите вершину, ее значение пишите в ответ, удаляете вершину и добавляете в начало.

Edit: тут было неправильное решение через недо-skip-list.

Есть чуть более простое в реализации решение, но на той же идее. Вместо бинарного дерева поиска используйте дерево отрезков.

Заведите отрезок на n+m элементов. Кадому символу в алфавите будет соответствовать еденица где-то в этом отрезке. Изначально они занимают n самых правых позиций. Их порядок - это будет та самая перестановка из условия. Дервево отрезков будет считать сумму. В таком дереве можно за логарифм найти k-ую еденицу (рекурсивный спуск) и узнать какой по порядку является данная еденица (запрос на сумму на отрезке 0..i-1). Еще для каждого символа алфавита храните, где именно на отрезке лежит соответствующая ему еденица, а для каждого элемента на отрезке, какому символу он соответствует.

При шифровании вы находите еденицу для символа алфавита, считаете какая она по порядку и выводите это число. потом перемещаете эту еденицу левее всех едениц. Это делается просто - на i-ой операции надо втыкать еденицу в позицию m-i+1.

При дешифровании вы находите к-ую еденицу, выводите соответствующий ей символ и перемещаете еденицу левее остальных.

Comments

[Роман]

не могли бы вы помочь определить сложность варианта из моего ответа?

[Wataru]

Роман, n^2. Введите текст на шифррвку состоящий из всех букв в убывающей последовательности. Ровно квадрат операций у вас выполнится.

[xmoonlight]

wataru,

Есть за O(n log m) решение

откуда такая сложность?!

[Wataru]

xmoonlight, Происходит n итераций шифрования/дешифрования, каждая итерация ищет, удаляет и добавляет элемент в балансированное дерево в котором m элементов.

У второго решения (с деревом отрезков) сложность O(n log(n+m)), потому что в отрезке n+m элементов.

[xmoonlight]

wataru,

каждая итерация ищет

так ключи и значения в массиве имеют однозначное соответствие. Что там искать?

[Wataru]

так ключи и значения в массиве имеют однозначное соответствие. Что там искать?

Еще раз повторю. Дерево по неявному ключу. Эта структура позволяет за логарифм искать k-ый по порядку элемент, вставлять элемент в i-ое место и удалять элементы, не меняя относительный порядок остальных элементов. Все, что для этого нужно - хранить сколько вершин в поддереве в каждой вершине.

Вы храните перестановку в такой структуре. Еще есть обратный массив, который для каждого числа указывает, где оно в дереве хранится (указатель на вершину).

При шифровании надо узнать, какой "ключ" у заданного элемента. Это тоже реализуется проходом по дереву от вершины вверх. Потом перестановка элемента в начало - это log m + log m операций (удалить и вставить в начало).

При дешифровании надо узнать, какой элемент на k-ом месте и потом опять переставить элемент.

Второе решение, которое я сегодня дописал с деревом отрезков, возможно понятнее.

[Wataru]

xmoonlight, Вот ссылка на стурктуру данных.

[xmoonlight]

wataru,

Вот ссылка на стурктуру данных.

Согласен. Это именно она.
Из чего видно, что каждая перестановка однозначно определена в таком дереве.

Это означает, что как для прямого поиска (при шифровке), так и для обратного поиска (при дешифровке), существует некая формализованная и строго однозначная зависимость в виде f(s,m,n), определяющая точный порядок соответствия в обе стороны.
А реализация после нахождения этой формулы - это уже линейная сложность.
(Верно?)

[Wataru]

xmoonlight, Да, если формула вам дана, то общее решение - линейно.

Вот только как эту формулу считать быстрее, чем за log m в таком или подобном дереве, мне неизвестно.

Ваш ответ недостаточно детально раскрывает вашу идею и мне не понятно, как оно работает.

[Proshka17]

wataru, Добрый день!
Нашел реализацию дерева поиска с индексацией. Все работает, но получаю Time Limit, хотя все операции вроде за log.
Данная реализация дерева использует в виде ключей строки, поэтому в начале кода я перегрузил операторы сравнения для строк, вот так:

bool operator> (string& a, string& b) {
  long long d1 = stoll(a);
  long long d2 = stoll(b);
  return d1 > d2;
}

bool operator< (string& a, string& b) {
  long long d1 = stoll(a);
  long long d2 = stoll(b);
  return d1 < d2;
}

bool operator== (string& a, string& b) {
  long long d1 = stoll(a);
  long long d2 = stoll(b);
  return d1 == d2;
}

И чтобы вставить в начало списка(самым левым в дереве) я уменьшаю глобальный счетчик на 1 и использую to_string(счетчик) как ключ.
Вот ссылка на дерево:
https://github.com/dvjdjvu/bntree/tree/master/src

Код программы main:

int main()
{

  ifstream f("input.txt");
  bntree b;
  long long count;
  f >> count;
  long long power;
  f >> power;
  long long type;
  f >> type;


  
  

  for (long long i = 1; i <= power; ++i) {
    string key = to_string(sch);
    string val = to_string(i);
    b.insert(key,val);
    mp.emplace(i,key);
    sch++;
  }
  sch = -1;

  if (type == 1) {
    for (long long i = 0; i < count; ++i) {
      long long one;
      f >> one;
      string key = mp[one];
      long long ind = b.search(key);
      cout << ind + 1 << " ";
      b.erase(ind);

      string newkey = to_string(sch);
      sch--;
      string strval = to_string(one);
      b.insert(newkey, strval);
      mp[one] = newkey;
    }
  }
  else {
    for (long long i = 0; i < count; ++i) {
      long long one;
      f >> one;
      string key = b.get(one-1)->key;
      string res = b.get(one-1)->val;
      cout << res << " ";
      b.erase(key);
      string newkey = to_string(sch);
      sch--;
      b.insert(newkey,res);
    }
  }


  return 0;
}

У вас нету идей, как можно ускорить?

[xmoonlight]

wataru, кстати, я не увидел письма от Вас. Вы вчера писали мне?

[Wataru]

Proshka17, Перепишите дерево, чтобы вместо строк инты везде были.

[Wataru]

xmoonlight, Нет, вчера не писал. Сейчас написал.

[xmoonlight]

wataru, ок, ответил.

[Proshka17]

wataru, Переписал.
Теперь Time Limit на 11 тесте, а раньше был на 7. Чуть чуть продвинулся)

int main()
{
 std::ios_base::sync_with_stdio(false);
  ifstream f("input.txt");
  bntree b;
  long long count;
  f >> count;
  long long power;
  f >> power;
  long long type;
  f >> type;
  long long sch = 1;
  unordered_map<long long, long long> mp;
  
  

  for (long long i = 1; i <= power; ++i) {
      string val = to_string(i);
      b.insert(sch, val);
      mp.emplace(i, sch);
      sch++;
  }
  sch = -1;



  if (type == 1) {
    for (long long i = 0; i < count; ++i) {
      long long one;
      f >> one;
      long long key = mp[one];
      long long ind = b.search(key);
      cout << ind + 1 << " ";
      b.eraseI(ind);
      string strval = to_string(one);
      b.insert(sch, strval);
      mp[one] = sch;
      sch--;
    }
  }
  else {
    for (long long i = 0; i < count; ++i) {
      long long one;
      f >> one;
      long long key = b.getI(one - 1)->key;
      string res = b.getI(one - 1)->val;
      cout << res << " ";
      b.erase(key);
      b.insert(sch, res);
      sch--;
    }
  }


  return 0;
}

[Wataru]

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

Далее, как я писал, заведите отрезок на n+m элементов и в последние m положите 1 - для каждого символа алфавита. И массив заведите второй, который будет для каждой позиции в отрезке говорить, какой символ там лежит. И еще один массив (what), который для каждого символа говорит, где он лежит в отрезке (where).

Потом, при шифровании, чтобы узнать, какой символ по счету, получаете его позицию в отрезке из вспомогательного массива и вызываете sum(0, where[one]-1). Потом перезаписываете where[one] в дереве отрезков на 0 и кладете 1 левее всех элементов (по счетчику, как у вас уже ключ уменьшается каждый раз на 1, только начинайте не с -1, а с n).

При дешифровке чуть сложнее. Надо будет как тут искать k-ую единицу. Потом вывести what[] от этой позиции и перенести единицу левее.

При переносе единицы не забудьте обновить what[] и where[].

[Proshka17]

wataru, работает, спасибо!

[Wataru]

Proshka17, И как в итоге сделали, дерево отрезков или сбалансированным бинарным деревом?

[Proshka17]

wataru, дерево отрезков.
Я протестировал и получилось в среднем в 2 раза быстрее, чем код выше

Answer 2

[xmoonlight]

Сложность тут линейная: O(n)
Шифрование/дешифрование - однопроходные.

При шифровании:
Слева - сам символ (его код), справа - символ с кодом его позиции.
(в центре - "смесь")

Расшифровка - в обратном порядке.

PS:

Но чтобы получить номер нода в списке, придется пройтись по списку, а это уже n^2.

нужно добавить ещё одну грань до куба с векторами смещений.

Comments

[Wataru]

нужно добавить ещё одну грань до куба с векторами смещений.

Можно поподробнее?

[Роман]

во второй попытке как раз пытался реализовать через смещения, но вышел на O(log n), к O(n) так и не смог привести. Так что поддержу wataru, можно поподробнее?

[xmoonlight]

Роман, на каком шаге непонятно? (распиши подробнее шаги: как ты понимаешь).
Уточню: три грани куба: входной символ, позиция имеющегося символа, порядковый номер входного (шаг итерации). Их общее пересечение однозначно определяет следующий символ на каждом шаге. Определив однократно зависимости таких сочетаний, используем куб для линейного шифрования и дешифрования текста.

[Роман]

xmoonlight, не совсем так, при озвученных вами условиях надо при перемещении любого символа в начало либо устанавливать данные вектора не только для данного символа, но и для для некоторого количества других символов, либо же следовать по ближайшим вершинам опять же некоторого количества других символов при получении актуального вектора. И одно и другое добавляют некоторое количество итераций во внутреннем цикле, что приводит к стоимости алгоритма равной приблизительно O(log n)

ход мыслей (неверный/незавершенный)

Данный пример не рабочий, но шаги описывает

// линейный массив, описывающий 3-х мерны вектор
    const data = Array.apply(null, {length: amount+1}).map((v,i)=>({char: i, index: i, offset: 0}));

    // массив в который складываем преобразованные буквы
    const a = [];

    // общее смещение
    let offset = 0;


    // цикл по тексту
    for(var k=0; k<length; k++){

        const char = text[k];
        const item = data[char];

        const index =  item.index + offset - (item.offset - offset); // => 1 + item.index - (1 - offset)

        if (char != data[1-offset]) {
            item.offset = offset;
            offset++;
            item.index = 1-offset;
            data[item.index] = item;
        }
        a.push(index);
    }
    return a;
}

console.log( alise(7, 3, 1, [2,3,1,2,1,1,1]).join(',') );

[xmoonlight]

Роман, номер позиции "выдавлеваемого" (в начало списка) символа всегда соответствует входному символу. Что означает, что "цепь" на каждом шаге (при новом входном символе) - постоянна и однозначна в обе стороны.
При шифровании нам нужно скоммутировать между собой значения нужных пересечения граней внутри куба в одну непрерывную "цепь", и мы получим путь следования как для шифрования, так и для дешифровки за O(n).

v1: {a,b,c}=>A -> {a,b,c}=>B, 
v2: {a,b,c}=>C -> {a,b,c}=>D,
....
и т.д.

v1,v2,..,vN - это готовый путь пересечений граней внутри куба для шифрования/дешифрования текста.

[Роман]

xmoonlight, да, но вы не учитываете число итераций для удаления элемента по старому индексу

[xmoonlight]

Роман, откуда удаление? я сразу проставляю нужные элементы в свои позиции. В этом весь фокус.

[Wataru]

xmoonlight, Я правильно понимаю, что составляется некоторая таблица, в которой ключ - тройка чисел (какой символ надо зашифровать, где этот символ в текущей перестановке, номер итерации), так? Я точно что-то путаю же?

Могли бы вы показать работу вашего алгоритма по шагам (приведите то, что вы называете "кубом") для примера из трех символов в алфавите. Зашифруйте, пожалуйста, текст "3 1 2 3" (ответ "3 2 3 3") и "3 1 1 3" (ответ "3 2 1 2").