@Proshka17

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

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

Я придумал несколько решений, но все они так или иначе n^2 по сложности.
Например, можно использовать односвязный список и хэш таблицу с указателями на ноды списка для шифрования. Но чтобы получить номер нода в списке, придется пройтись по списку, а это уже n^2.
Можно ли решить эту задачу быстрее?
  • Вопрос задан
  • 308 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Есть за O(n log m) решение, но оно технически сложноватое. Реализуется через балансированное бинарное дерево поиска с неявным ключем. Грубо говоря, если в каждой вершине балансированного дерева хранить сколько всего вершин в поддереве, то в такой структуре можно искать вершину по номеру. Можно так же в это дерево вставлять вершину на заданную позицию.

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

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

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

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

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

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

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

При дешифровании вы находите к-ую еденицу, выводите соответствующий ей символ и перемещаете еденицу левее остальных.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Сложность тут линейная: O(n)
Шифрование/дешифрование - однопроходные.

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

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

PS:
Но чтобы получить номер нода в списке, придется пройтись по списку, а это уже n^2.
нужно добавить ещё одну грань до куба с векторами смещений.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы