Wataru

Странное задание. Какая польза от этого сокращения сравнений, если всего в результате вставки переместится до O(log n) элементов?

Но, если так надо, то вам нужно для каждого числа сначала узнать номер старшего ненулевого бита (most significat bit - MSB), и потом сдвинуть верхнее число вправо на половину разницы в позициях старших битов.

1 = 0000001b, msb = 0
18 = 0010010b, msb = 4

Разность - 4 разряда. Значит, надо сдвигать на 2 разряда вправо:
18 >> 2= 0010010b >> 2 = 00100b = 4

Еще пример: для 4 и 18 msb были бы 2 и 4, разность -2. Сдвинув 18 на 2/2=1 разряд вправо, вы бы получили 9.

Чтобы эта оптимизация давала хоть какую-то пользу, надо находить msb очень быстро. Или предподсчитайте их для всех возможных индексов, или надейтесь, что в вашем языке есть встроенная функция, которая вызывает нужную инструкцию процессора, типа __builtin_clz.

Еще можно подсчитать msb только один раз для правой границы бинпоиска, а потом просто помнить его, ведь у средней точки - это среднее арифметическое (левая граница изначально 1 - у нее msb = 0). А потом в процессе бинпоиска надо просто хранить msb для двух границ и заменять известным значением середины один из концов.

Для предподсчета просто в цикле задавайте msb[i] = msb[i/2] + 1;

TL;DR:

S = Pi*sqrt(3 / [ (1/L1+1/L2+1/L3)^2-2*(1/L1^2+1/L2^2+1/L3^2) ])

тут L1, L2, L3 - квадраты трех измерений.

Вывод формул:
Чуть-чуть аналитической геометрии и куча элементарной алгебры помогут вам вывести эти уравнения.
Если ввести систему координат с осями по главным радиусам эллипса, то уравнение эллипса будет:
x^2/a^2+y^2/b^2 = 1

При этом все точки под углом alpha к большой полуоси будут на луче:

x(t, alpha) = t*cos(alpha)
y(t, alpha) = t*sin(alpha)

Обозначим синус и косинус угла для первого измерения как:
s = sin(a1), c = cos(a1)

Пусть квадраты расстояний - L1, L2, L3.

Если пересечь луч и эллипс, то можно составить уравнение для длины вдоль угла a1 (первое измерение), просто подставив известные x(a1, sqrt(L1)) и y(a1, sqrt(L1)).
1/L1 = c^2/a^2+s^2/b^2

Для остальных измерений надо прибавлять 120 градусов к углу под cos и sin. Если раскрыть cos(120+a1) = cos(120)cos(a1)-sin(120)sin(a1) и sin(120+a1) = cos(120)sin(a1)+sin(120)cos(a1), то можно составить еще 2 уравнения:

1/L2 = (-1/2*c-sqrt(3)/2*s)^2/a^2+(sqrt(3)/2*c-1/2*s)^2/b^2
L3 = (-1/2*c+sqrt(3)/2*s)^2/a^2+(-sqrt(3)/2*c-1/2*s)^2/b^2

Всего с учетом тригонометрического тождества s^2+c^2=1 у нас 4 уравнения на 4 неизвестных a, b, c, s.

Но нам не нужны все значения. Площадь эллипса Pi*a*b, а радиусы эллипса - a и b.

Раскрыв квадраты выше и всячески складывая эти уравнения можно получить в итоге

1/a^2+1/b^2 = 2/3*(1/L1+1/L2+1/L3)
1/a^2*b^2 = [ (1/L1+1/L2+1/L3)^2-2*(1/L1^2+1/L2^2+1/L3^2) ]/3

Отсюда площадь:

S = Pi*ab = Pi*sqrt([ (L1+L2+L3)^2-2*(L1^2+L2^2+L3^2 ]/3)

Чтобы найти радиусы эллипса, вам надо найти a и b. Выше уже даны два уравнения для суммы и произведения 1/a^2 и 1/b^2 - можно из них получить квадратное уравнение для t=1/a^2. Два его решения и будут вашими радиусами эллипса (не забудьте взять корни и обратить). Тут надо аккуратно подставить выражения в школьные формулы для квадратного уравнения.

Не совсем. Форма правильная, но пропорции - нет. График должен начинаться в той же точке, что и u_b. Число 0.5 там не верно. Эта точка значительно ниже 0.5. И точка пересечения двух графиков вовсе не x=4.

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

Можно еще перенести в cpp файл определение шаблонных классов/методов/функций, но для этого надо в хедере указать через forward declaration все используемые специализации шаблона. Например так:

template <>
int Database::RemoveIf<bool>(bool predicate);

Конечно, там должен быть не bool а тип вашего предиката. И надо такие штуки воткнуть в хедер для ВСЕХ типов, которые в других файлах пихаются в шаблон.

Обычно нужно определять функцию прямо в хедере, потому что когда компилятор собирает cpp файл с определением класса, он не видит, как этот шаблон используется в других файлах, поэтому он не может догадаться сгенерировать код для используемых специализаций шаблона. Если же реализовывать функцию в хедере, то реализация будет в том же файле, что и ее использование. Поэтому компилятор сможет выбрать нужные типы. Forward declaration позволяет обойти эту проблему.

Судя по коду, вы хотите, чтобы массив был отсортирован. Но тогда просто менять новый элемент с чем-то в массиве неправильно - его надо туда вставлять, сдвигая все элементы.

Вот пример: уже обновленная и отсортированная часть {1, 2, 3, 5, 6, 7}. Только что обновленный элемент имеет значение 4. lower_bound вернет итератор на 5. Вы поменяете 5 и 4 и получите {1, 2, 3, 4, 6, 7, 5} - не отсортировано уже.

Можно удалить элемент в it и вставить на новое место через insert, но тогда могут быть проблемы с итератором цикла. Можно ручками через swap сдвигать элементы в цикле:

T tmp = it->value;
for (auto cur = std::lower_bound(vector.begin(), it, (*it)); cur < it; ++cur) {
   swap(tmp, cur->value);
}
it->value = tmp;

Это, фактически, будет сортировкой вставкой за O(N^2). lower_bound за логарифм тут на самом деле даже лишнее и только замедляет сортировку. Лучше одним циклом сразу и swap-ать и сравнивать элементы.

Но еще быстрее будет отдельно пройтись по массиву и обновить его целиком и потом вызвать std::sort для сортировки по value.

Нет, тут O(n^2). С чего вы там взяли log?

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

Обрабатывайте все записи в хронологическом порядке.

При приходе in, вы добавляете в стек (через append у list-а) пару (цена, количество).

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

Что-то вроде такого (сам не питонист, возможно придется переписать немного)

def getOstatokLIFO(df):
  stack = [];
  for index, row in df.iterrows():
    if row.operation == "in":
      stack.append([row.price, row.quantity])
      continue
    left = row.quantity
    while left > 0:
      if left >= stack[-1][1]:
        left -= stack[-1][1]
        stack.pop()
      else:
        stack[-1][1] -= left
        left = 0
        
  return stack

Но вообще, DataFrame очень медленно работет при такой последовательной обработке, поэтому я бы посоветовал вам не создавать pandas dataframe изначально, и получить ваши данные в виде списка словарей, touples или объектов. А алгоритм расчета предполагает последовательную обработку.

Перечитайте теорию. Повторите определение нечеткого множества, функии его принадлежности и операции над нечеткими множествами. Что значит НЕ B? Раз вероятность принадлежать B - это f(x), то вероятность не принадлежать, очевидно - 1-f(x). Вот и на рисунке 2 показана функция 1-f(x), где f(x) показана на графике для b.

С пересечениями, наверно, функции перемножаются, а при объединении берется 1-(1-f(x))(1-g(x)).

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

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

Читайте ошибку внимательно. Дело не в массиве.

Вместо SegmentTree tree = new SegmentTree(a, n);
надо
SegmentTree tree(a, n); или SegmentTree *tree = new SegmentTree(a, n);

new - создает указатель. Инициализировать им нужно, соответственно, указатель.

(Полное условие есть в комментариях к вопросу)

Алгоритмически тут такое решение: Постройте граф из n вершин, где есть ребро между всеми парами вершин, которые можно менять местами. Подсчитайте размеры компонент связности и перемножте их факториалы. Так, если компонента всего одна, то ответ будет n! (все возможные перестановки из n чисел можно получить так).

Это работает потому, что в каждой компоненте можно получить любую перестановку. Доказательство: строим остовное дерево в компоненте. Потом берем любой лист и перетаскиваем туда любое число по ребрам остовного дерева. Отрезаем лист от дерева. Повторяем эту операцию пока не останется только одна вершина.

Если нужно именно математическая формула от P, то тут все сложно, осбоенно, когда числа P достаточно большие. Например, M=6, P1=3 P2=4. Из вершин 3 и 4 вообще нет ребер, а ребро P2 есть только между крайними вершинам. Подобным образом можно создать весьма сложные структуры.

Однако, если все P меньше равны половины N, то есть простой ответ. В графе будет GCD(P1+1,...,PM+1) компонент связности - все вершины, дающие один и тот же остаток от деления на наибольший общий делитель P+1. И ответ будет что-то вроде (floor(N/G)!)^G*(floor(N/G)+1)^(N%G) (где G - этот самый наибольший общий делитель всех P, увеличенных на 1).

Это потому, что при достаточно маленьких P, всегда можно отложить их в одну или другую сторону и так в итоге сделать шаг длинной G.

Доказательство примерно такое: Рассмотрим первую половину вершин. Из них можно отложить вправо самое большое P. А потом влево любое из оставшихся P. Так мы фактически отложили от всех этих вершин любую разность двух P вправо. Если сначала отложить вправо меньшее P, а потом максимальное P назад, то мы отложили ту же разность влево. Из соображений симметричности получается, что мы можем отложить любую разность P от всех вершин в любую сторону. Все разности также меньше половины N. Продолжая этот процесс, как в алгоритме эвклида, мы получим, что можно от каждой вершины отложить G, а значит все вершины с одинаковым остатоком от деления на G принадлежат одной и той же компоненте связности.

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

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

Вы там еще очередь pop-аете раньше времени.

Подобно задаче о 4-х шпинделях. Чтобы переместить самый большой диск на последний шпиндель, сначала надо все меньшие диски куда-то деть. Можно их парковать на 2-ом шпинделе или на 8-ом. Потом подвигать последний диск до 7-ого шпинделя, потом перепарковать часть с 8-ого на 6-ой и подвигать последний диск. Потом назад с 6-ого на 8-ой и оставшиеся со 2-ого на 8-ой. И надо перебрать все варианты - сколько дисков куда пихать.

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

Чтобы это работало быстро, надо делать мемоизацию и не считать функцию с одним и тем же набором параметров несколько раз.

Интересно, что ответ растет гораздо медленее, чем для 3-х шпинделей:

6
13
22
36
55
82
117
163
219
289
375
484
623
800
1024
1300
1651
2090
2643
3333

Есть целая наука об этом. "Временные ряды", вроде, называется. Там есть куча всяких моделей, типа ARIMA.

type_traits - это имя параметра шаблона, который задан в родительском классе streambuf.

type_traits::eof() - возвращает код конца файла, для текущего параметра шаблона.

Вся эта шаблонная магия взялась для того, чтобы можно было читать из файла или char, или wchar, или еще черт знает что, в зависимости от кодировки. Раз читаемые символы могут быть какими угодно, то и код конца файла нужен свой собственный для разных типов символов. Поэтому eof() является частью type_traits в streambuf.