Wataru

На пальцах - можно и складывать и брать большее. Но последнее - более точная оценка. Но на самом деле надо формально расписать по определению. Что значит первая часть O(N)? Для некоторых чисел N1 и С1, при N>N1 первая часть алгоритма делает менее С1*N операций. Аналогично, при N>N2, вторая часть выполняет менее С2*log(N) операций.

Итого имеем, при N>max(N1,N2), всего выполняется менее C1*N+C2*logN операций. Если взять C = max(C1, C2), то можно сверху ограничить количество операций C*(N+log N). Т.е. мы доказали, что ваш алгоритм - O(N+log N). Далее, начиная с какого-то N>N3 N > log(N). Т.е. при N> max(N1,N2,N3) можно ограничить время работы как C*(N+N) = 2*C*N = C'*N. А это уже означает, что весь алгоритм - O(N).

Из этих рассуждений должно быть понятно, что при сумме константного количество шагов можно брать O() для самого тяжелого шага. Но, если количество шагов зависит от N, то так делать нельзя, потому что в последнем шаге вылезет не константный множитель (как 2 выше), а что-то зависящее от N.

Очень мешает ограничение на фиксированный выходной алфавит, если в этом алфавите не степень двойки символов (как для цифр от 0 до 9). Так-то многие алгоритмы сжатия пользуются тем, что можно записать минимально возможную единицу информации - один бит. Иначе неэффективно сжимается. А на случайных данных без какой-то структуры и с большой энтропией и так все хреново работает.

Советую посмотреть в сторону Burrows-Wheeler transform и потом попробовать RLE или LZ присобачить сверху. Может, ваши данные будут им хорошо сжиматься.

Еще вам тут сильно помогло бы что-то вроде Base64 encode/decode. Допустим у вас k символов в алфавите. Значит каждый символ несет log_2(k) бит. И если у вас символов N, то ваша входная строка содержит N*log_2(k) бит информации. Округлите это число вверх и сгенерируйте столько битов. Это фактически преобразование из k-ичной системы счисления в двоичную. На больших строках будет тормозить, потому что пока мне не очевидно, как для произвольного k делать преобразование быстро, а не делить большое число на 2 с остатком. Если только у вас k не степень двойки, тогда как в base64 можно быстро преобразовывать по блокам.

Потом можно эту битовую строку сжать каким угодно алгоритмом (разбить на блоки, скажем, 8 бит и хоть хаффманом, хоть lz). Потом надо сжатую битовую строку преобразовать назад в k-ичную систему счисления.

Можно комбинировать сжатие на исходном тексте и запись произвольной битовой строки в вашем алфавите. Например после BW-transform вы гоните LZ на тексте из цифр. LZ для эффективности надо уметь писать произвольные битовые строки. Вот вы где-то в памяти отдельно собираете новые символы, которые замыкают новые строки-эталоны (цифры в вашем примере), и отдельно битовую строку. Потом эту строку переведите в k-ичную систему счисления и запишите перед просто символами (как-то закодировав ее длину в скольки-то первых символах заголовка).

Читайте строку std::string. Проверяйте,что в ней максимум 1 '-' в самом начале, далее первая цифра не '0' (если второй не ',', есть максимум один символ ',' и он не первый. Потом используйте stringstream чтобы прочитать double.

Чтобы сделать бинарный поиск, вам нужен массив объектов с ценами и названиями. Что-то вроде

[1=>{cost:1, name:"name1"} .... 117=>{cost:55233, name:"name555"}]

(не уверен, что правильно описал на js).

Но, по идее, все нормальные языки умеют что-то вроде lower_bound для ассоциативных массивов. Именно эту функцию и надо вызвать. А дальше выбрать лучший из текущего и предыдущего или следующего элемента (в зависимости, как в вашем языке lower_bound работает).

Можно поискать какие-нибудь js библиотеки с нормальным ассоциативным массивом, который это умеет.
Будет также работать за логарифм.

| - это побитовое ИЛИ. & - побитовое И. Т.е. каждый разряд отдельно обрабатывается и, в случае ИЛИ, если хоть одно число имеет единицу в данном разряде, то и результат будет 1. Соответственно, 00001 | 00010 = 00011.

Степени двойки - это числа, где единица стоит только в одном бите. Если несколько таких чисел про-ИЛИ-ть - то получится число, где стоят единицы во всех нужных разрядах. Фактически, вы назначаете каждому состоянию свой разряд. Потом, где в числе стоят единицы - те состояния и есть.

Чтобы проверить, что бит в числе установлен, надо взять побитовое И и убедиться, что результат не 0 (он может быть либо 0 либо какой-то степенью двойки.

Вы уже задавали этот вопрос.

Я там вам ответил, что это класическая задача на нахождение компонет связности в графе. Гуглите DFS, компоненты связности, графы. Я там даже технических деталей кучу привел.

*offtopic* Лет 15 назад делал такое для записывания анимешных сериалов на CD-диски, только там было сложнее, потому что сериалы можно разбивать по нескольким дискам и записывать можно толко сериалы целиком. Эх... было время. Сейчас эти 300 дисков даже и прочитать-то нечем. И исходники пропали лет 10 назад =(.

Как вам уже написали - эта задача о мульти-рюкзаке. Простого и эффективного решения у нее нет.

Однако, на практике, скорее всего, вам не нужно оптимальное решение - нужна лишь его некоторая аппроксимация. Посмотрите задачу о рюкзаке. Там есть очень простое динамическое программирование с параметрами вида "можно ли используя файлы с 1 по i-ый заполнить ровно k (мега|кило)байт"

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

Удалите файлы определенные на эту флешку из рассмотрения и повторяйте процесс.

Можно навесить сверху полный перебор с отсечениями. Из массива ДП идля задачи о рюкзаке можно случайным образом получить несколько хороших заполнений.

Потом в переборе пробуйте разные варианты, запускайтесь рекурсивно. Какой-то ответ будет найден моментально. Выходите из перебора, если текущее количество флешек/общее свободное место/сумма квадратов свободных мест превысило оптимальное найденное пока что.

Для ускорения можно округлить размеры файлов до мегабайта. Чем меньше разрешение - тем быстрее будет работать ДП. Еще можно отдавать предпочтение большим файлам в начале.

Альтернативно - составьте задачу целочисленного линейного программирование (integer linear programming) и натравите на нее какой-то из солверов. Они сейчас очень продвинутые. Правда тут уж как повезет. Может на вашей задаче вы ответа так и не дождетесь. В качестве переменных берите, что такой-то файл относится к такой-то флешке. Сумма по каждому файлу - ровно один. По каждой флешке сумма размеров файлов * на переменные <= размер флешки. Сумма свободных мест - минимизируется.

Возможно, можно составить квадратичную целевую функцию, я не знаю, что сейчас солверы умеют. Гуглите quadratic integer programming solver.

Если хотите минимизировать количество флешек, то можно завести еще переменные - занята ли флешка. Уравнения тут - эта переменная >= всех индикаторынх переменных для всех файлов для этой флешки. Целевая функция - сумма всех переменных занятости флешек.

У вас сильно наворочено - много где можно ошибиться. Какие-то indexOf() используете кучу раз, хотя можно просто сравнивать символы через CharAt(), субстиринги везде. Советую переписать ваше решение с нуля, искать в нем ошибки невозможно.

В задаче надо рассмотреть важный случай, когда заняты все буквы алфавита, в этом случае, если строчки не одинаковые - то ответ 0. У вас, похоже, решение будет использовать символ вне алфавита.

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

Что-то вроде этого (читайте как псевдокод, я джаву не особо знаю):

public static int isEqual(String firstString, String secondString) {
  int used = 0;
  int[] first = new int[256], second = new int[256];
  if (firstString == secondString) return 1;
  if (firstString.length() != secondString.length()) return 0;
  for (i = 0; i < firstString.lengt(); ++i) {
    int ch1 = Character.getNumericValue(firstString.charAt(i));
    int ch2 = Character.getNumericValue(secondString.charAt(i));
    if (first[ch1] == 0) {
      used++;
    }
    if (first[ch1] != second[ch2]) return 0;
    first[ch1] = i+1;  // +1, потому что изначальные 0 означают "символ не встречался"
    second[ch2] = i+1; 
  }
  if (used == 33) return 0;
  return 1;

Возможно лучше переписать с Map, я не знаю, что там с кодировками будет, может символы не однобайтовые и 256 в таблицах не хватит.

Вот алгоритм для перемешивания массива, если у вас есть детерминированная функция rand(), которую вы каким-то seed проинициализровали.

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

Можно использовать что-то вроде функции, предложенной twobomb, но именно той функцией пользоваться не советую - она выдаст максимум 67 различных вариантов, а на самом деле сильно меньше. Используйте, например, параметры отсюда:

function rand(){
 	seed = (16,807*seed) % 2,147,483,647;
 	return seed/2,147,483,647;
}

тут много проблем.

1) не надо в конце part менять местами 0-ой и i-ый элементы. Это бессмысленно. Вы поддерживаете вариант, что элементы с 0 по i-ый <=x, c j-ого и дальше >=x

2) У вас у part() параметр m передается по значению. Изменение его в конце функции не видно из места вызова. Вы каждый раз, независимо от того, как разбиение произошло, рекурсивно запускаетесь половин массива разделенных ровно по середине.

3) Что у вас с рекурсивными вызовами твориться? Вы хвостовую рекурсию руками схлопнули что ли? А зачем выбирать, с какой стороны рекурсивно вызваться, а с какую дальше в цикле обрабатывать? Там у вас что-то с вычислениями напутанно, всякие +-1 неверно распиханы. Вы там делаете k -= left+1 и k -= right+1. По логике в одной половине left элементов, в другой - right. Тогда почему вы -1 еще делаете и там и там?

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

Перенумеруйте все емейлы и всех пользователей.
Код будет проще, если емейлы и пользователи хранятся в одном и том же пространстве номеров.
Это реализуется с одним hashMap, который будет давать номер по строке, и одним массивом строк, который будет хранить изначальную строку по номеру. Вам еще понадобится булевый массив, чтобы хранить, является ли данная вершина пользователем или мейлом. При вводе получаете какую-то строку, и вызываете от нее функцию GetID(s, is_user), которая проверяет, есть ли данная строка в мапе. Если есть, возвращает номер. Если нет - дописывает строку в массив строк, записывает ее индекс в мап и возвращает его.

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

Заведите массив пометок "обойденности" для всех вершин. Он будет int. 0 - непосещенные вершины, иначе номер компоненты связности.
Запустите на этом графе DFS/BFS от каждой пока не обойденной вершины в цикле и помечайте все достижимые вершины новым числом (можно передавать вторым параметром в DFS). Можно сразу же во время обхода заполнять структуру ответ - один номер для пользователя и список для емейлов. Или можно после цикла с DFS завести массив списков для ответа, пройтись по массиву и распихать номера вершин по спискам. Используйте булевый массив, чтобы понять какая вершина пользователь, а какая - мейл. Из пользователей возьмите только одного предстваителя, а все емейлы запихайте в список в ответ. Потом выводите, преобразуя номера в строки с помощью имеющегося массива.

Если зависимость может быть любая (например, числа фиббоначи) - то никак. Можно поискать последовательность на oeis.org

Если же возможна только зависимость вида +a_0, +a_1, +a_2,..., +a_k, +a_0, +a_1... т.е. повторяющийся фиксированный паттерн приращений, то есть быстрое и простое решение.

Во первых, если вам дано 10 чисел, то всегда можно сказать, что есть паттерн длиной в 9 приращений.
Но можно найти кратчайший паттерн с помощью алгоритма поиска периода в строке. Буквально, по определению, нужный вам кратчайший паттерн (типа {+3, -2} для второго примера) будет периодом строки. Правда, тут не строка, а массив чисел, но это вообще никак не меняет алгоритмы. Просто у вас алфавит нестандартный.

Сначала от массива чисел перейдите к массиву приращений.

Потом можно применить жадное наивное решение - просто перебираете все возможные значения периода от 1 до n/2 и проверяете, что a[i] == a[i+str] для всех i. Как только все совпало - вы нашли период. Это решение за квадрат. Если чисел вам задано много, то можно применить префикс функцию: найдите значение префикс функции (p) для всей строки и, если ее значение больше половины длины строки, то у строки есть период n-p. Это будет линейное решение.

Еще можно применить алгоритм Дюваля. Тоже линейное решение, но более сложное в реализации и понимании.

Ваше решение не работает на примере "аб аа".

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

Но в ваше решение еще не рассматривает крайний случай - использованы все 33 буквы алфавита и есть надо что-то менять. Тут ответ 0, потому что замены делать никак не получится - после любой замены 2 разные типа букв станут одинаковыми и перемешаются. Разделить их после этого уже не получится.

Если вы эти косяки исправите, ваше решение может не пройти по времени, потому что оно у вас за квадрат. Лучшее решение - пройтись по строкам одновременно одним циклом и запоминать в массиве, индексированном символами, (или мапе), какая буква алфавита во втором слове соответствует букве алфавита в первом слове. Если встречаете противоречие (в массиве уже что-то записано не такое как вы видите сейчас), то ответ 0.

И еще. Не надо разбивать строки через .split(''). В JavaScript можно узнать длину строк и обратиться к i-ому символу не преобразуя в массив.