Как перемешать массив одинаково для всех?

twobomb, Что уж там, тогда делайте просто function rand() {return 0;} Тоже в некотором смысле перемешано будет. Хоть вариант и всего один будет.

Но в вопросе указано:

Но при этом результат должен быть уникальным, не таким каким был с предыдущим числом.

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

Как перемешать массив одинаково для всех?

Во-первых, не надо сортировке выдавать самопротиворечивую функцию сравнения.
Она и в O(N^2) может запросто скатиться, а то и повиснуть. И может выдавать разные результаты при одинаковых входных данных:

compareFunction(a, b) must always return the same value when given a specific pair of elements a and b as its two arguments. If inconsistent results are returned, then the sort order is undefined.

Во-вторых, раз уж у вас есть rand() с seed, то можно перемешать массив вот этим стандартным методом, что 100% быстрее и без возможных спец-эффектов:

for (i = 1; i<arr.length; ++i) {
 let j = floor(rand()*(i+1));
 let tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
}

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

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

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

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

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

Какой выбрать язык для криптографии?

Лентюй, Если вам нужна скорость, то вопрос выбора языка перед вами не стоит вообще. Берете готовую библиотеку к языку в вашего проекта. Или выбираете язык по каким-то вашим критериям.

Сама же библиотека будет на С, вылизанная с ассемблерными вставками, и обернута в интерфейс для вашего языка.

Почему неправильно работает такая реализация алгоритма быстрой сортировки?

AnT, Когда у вас глубина рекурсии достигает ~N в неоптимизированной реализации, то у вас сортировка, даже с вашей оптимизацией, будет работать за O(N^2). Если N такое большое, что O(N) памяти в стеке страшно завести, то вам в любом случае уже сильно поплохеет. Даже без оптимизации рекурсии.

А, раз человек не может разобраться с кодом, оптимизации можно для начала и исключить.

Почему неправильно работает такая реализация алгоритма быстрой сортировки?

Потому что фигню сделали в quicksort(). Мало цикл закомментировать, надо всегда делать 2 рекурсивных вызова. А у вас один будет - в какой-то ветке if-else. Сравните с этим кодом.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как понять условие задачи?

Proshka17, Да, вызов не правильный же. Надо только один раз вызвать. Это раньше надо было перебирать, сколько карт им досталось. Теперь же достаточно просто зафиксировать разницу в 0. Т.е ответ - это просто один вызов.

Как понять условие задачи?

Proshka17, Похоже фигня вот тут:
DP(k - 1, t - v, i - (v > 0) - (v < a[k]), a, N)

В пересчете i флаги должы идти с разными знаками. Если первому игроку досталась карта - то +1, если второму, то -1 (ну, или наоборот). У вас же оба флага вычитаются.

Как понять условие задачи?

условие на i<0, j<0 в первой проверке можно заменить на проверку, что разница по модулю не больше k. Ведь если у вас k типов карт роздано, то вы сможете получить от -k...k перевеса, отдав все или ни одной уникальнойкарты первому игроку

Второе условие - это база, когда роздано 0 типов карт. В этом случае перевеса нет и у первого игрока 0 карт. Т.е. условие t==0 && i==0. Тогда ответ 1. Иначе - 0.