Wataru

Вам же минимальный по объему паралеллипипед нужен? Это довольно сложная задача. Даже на плоскости искать прямоугольник не очень приятно.

Кажется, есть эффективное решение через численную оптимизацию и троичный поиск.

Введем функцию f(a,b) - минимальный объем параллелипипеда, повернутого на угол a вдоль оси oz и потом угол b вдоль ox. Ну или это эйлеровы углы, если хотите.

Вам надо найти минимум этой функции. Утверждение: если зафиксировать a, то двигая b функция будет переодическая с двумя экстремумами. Ну, потому что поворот на 90 градусов взвращает все как было, только оси местами меняются. Значит, на ней можно что-то вроде тернарного поиска запускать (об этом дальше).

Если же ввести функцию g(a) =Min_b(f(a,b)), то она, похоже будет такая же. По ней тоже можно такой же поиск запустить.

Итого, 2 вложенных тернарных поиска, в внутри легче все точки повернуть на -b и -a градусов и потом взять обрамляющий параллелипипед, параллельный осям координат (min/max по трем координатам за 1 проход).

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

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

Это будет что-то вроде O(n log^2 n).

Или можно просто случайным образом или с малым шагом перебирать разные углы поворота. Поворачивать все точки и искать параллельный осям координат параллелипипед (просто беря min/max по трем координатам). Для 800 точек можно 10000 углов перебрать и это займет лишь 100мс на современном железе.

Это сильно проще в реализации и, хоть и не найдет самый оптимальный параллелипипед, на глаз будет сложно это заметить.

Edit: вообще, кажется, там 3 угла, а не 2. Ну появляется еще третья функция t(a,b,c). и лишний Log n в сложности. Перебирать углы становится еще хуже, но все еще возмоно.

Вообще, вот алгоритм для произвольных слов: https://e-maxx.ru/algo/longest_increasing_subseq_log

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

Какие у вас там ограничения: длины строк и количество повторений?

Вот эти побитовые сдвиги работли бы, если бы вы хранили число в двоичной системе счисления. Допустим, по 16 бит в каждом int. В таком виде вычисления побыстрее будут немного, но при выводе надо переводить число в 10-ую систему счисления. Судя по примеру ответа, вы храните по 3 десятичных знака в каждой ячейке. Т.е. у вас основание системы счисления 1000. И тут нужны сдвиги не битовые, а тысячные (которых не существует).

Вообще, основной цикл умножения должен быть примерно такой:

for (i = 0; i < len1; ++i)
  for (j = 0; j < len2; ++j) 
    c[i+j] += a[i]*b[j];

И потом надо сделать все переносы. Вот тут и происходят сдвиг на i позиций (в системе счисления 1000) - это то самое +i в индексе у массива результата. И вместо выполнения прибавления, когда бит равен 1, тут происходит умножение на a[i]. В битовом случае оно как раз вырождается в умножение на 1 или 0 - прибавление или пропуск прибавления.

Это работает даже если вы в массивах a,b храните по несколько бит в каждой ячейке, или даже десятичных знаков. Это просто умножение в столбик в произвольной системе счисления.

Правда, тут проблема, что вот такое вот умножение, если вы храните по 32 бита, оно переполнится, и ответ надо в 64-битном типе получать. И даже если вы храните по 16 бит, то сумма может переполниться из-за большого количества слагаемых. Ну это решается выполнением переноса сразу же:

const int BASE = 1000; // База системы счисления. Оно же максимальное число в ячейке +1.
for (i = 0; i < len1; ++i) {
  int carry = 0;
  for (j = 0; j < len2; ++j) {
    carry += c[i+j] + a[i]*b[j];
    c[i+j] = carry % BASE; 
    carry /= BASE;
  }
  int i = len1+len2-1;
  while (carry > 0) {
    carry += c[i];
    c[i] = carry % BASE;
    carry /= BASE;
    ++i;
  }
}

Линейная. O(N+M). Ибо там цикл по i от 0 до startMedianIndex и вся остальная мишура на i вообще никак не влияет. Больше циклов в программе нет. Не понимаю, что тут может быть непонятного.

Итак, у вас ключи - какая-то древовидная структура и вам надо быстро определять, а есть ли такая структура в таблице. Я правильно понял?

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

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

Или можно тупо записать вашу структуру данных в строку (Например, расставив скобки вокруг каждого поддерева вроде "(a(b)(ccc(dd))" - это узел a, у которого есть дети b и ccc, у последнего есть ребенок dd) и потом как угодно хешировать уже строку, тогда ничего самостоятельно реализовавать ничего вообще не надо (to_json и hash от строки возможно уже есть).