Как подсчитать количество операций при работе алгоритма сортировки?

Ах, если бы для достижения логарифма достаточно было гнать внутренний цикл с индекса внешнего...

Если аккуратно подсчитать количество итераций, то будет N(N-1)/2 (потому что N+(N-1)+(N-2)+...+2+1).

Это в точности N^2/2 - N/2, что есть O(N^2). Более того, оно будет $Theta$(N^2). Т.е. не будет O() для чего угодно быстрее N^2.

O(N log N) тут даже близко не пахнет.

Как осуществить поэлементное сравнение множества массивов друг с другом и создание нового массива из лучших пар, троек, четверок и т.д.?

Григорий Грибанов, Формализуйте, пожалуйста, метрику. Как понять, какая пара лучше другой? Приведите формулу или алгоритм сравнения. Например, можно считать количество совпавших единиц. Где больше - та пара и лучше. Или можно считать количество совпавших элементов (и нули, и единицы). Или считать количество совпавших единиц минус количество несовпадений. Но это для пар. Что делать с тройками стульев? С четверками стульев? Например, можно брать минимальное значение метрики для любой пары в группе. Или среднее. Или среднее среди квадратов. Можно считать, сколько материалов используются одновременно во всех стульях группы. Или более половины стульев. Можно еще много как считать. Все это - разные задачи.

Потом, вам надо вывести все сочетания? Или только несколько (или одно) лучшее?

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

Почему алгоритм дейкстры не работает с ненаправленными графами?

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

Почему алгоритм дейкстры не работает с ненаправленными графами?

Fantoner, Бред. Вот на википедии прямо пример работы алгоритма - неориентированный граф с циклами.

Почему алгоритм дейкстры не работает с ненаправленными графами?

Нет. Совсем нет! Дейкстра работает на циклах. Там на каждой итерации выбирается одна вершина, для которой фиксируется минимальное расстояние. Посмотрите на псевдокод в википедии, там внешний цикл с фиксированным количеством итераций! Дейкстра не может зациклится просто физически.

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

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

carp123, Как так вообще? Что вы не можете реализовать? Подсчитать времена в матрице для каждой пары объект-точка можете? Выделить их в отдельный массив и отсортировать? Бинарный поиск написать не можете? Построить матрицу из нулей и единиц, где единицы стоят там, где время не больше заданного? Запустить алгоритм Куна на этой матрице?

Вот пример бинарного поиска.
Только вместо сравнения элементов в условии вам надо запускать вашу функцию, которая строит матрицу из 0 и 1, запускает паросочетание и сравнивает его размер с n.

Вот пример реализации алгоритма Куна Правда, там граф задан списком смежности, а не матрицей смежности, но это просто поменять for в функции try_kuhn. Еще там используется k для правой доли, но у вас там тоже должно быть n.

Быстрая сортировка на Golang, почему правая сторона не сортируется?

Вы посмотрите, что у вас в рекурсии передается в параметрах и подумайте, какой смысл у параметров. Почему вы передаете right в рекурсии, если у вас последний аргумент - длина массива? У вас передаются начало и конец сортируемого куска массива. И да, для первого вызова правильно передается длина массива, потому что кусок-то с начала сортируется.

Почитайте описание алгоритма еще раз - в качестве pivot надо выбрать любой элемент сортируемого куска. Если вы будете делать (b+k)/2, то это будет среднее между k-ым и b-ым элементами - началом и концом сортируемого куска. Как раз середина этого куска.

Это не основная проблема, на самом деле - работать у вас сортировка будет, но медленно, потому что pivot почти всегда будет меньше любого элемента на сортируемом куске - а значит вся сортировка будет работать за квадратичную сложность.

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

Во первых, глаза режет реализация revModFactorial. Просто, если не подсчитано значение, берите ModFactorial и возводите в степень N-2. И сделайте массивы для факториалов до 500, все-таки такие числа попадаются в формулах. Но это придирки.

Попробуйте вместо статических векторов завести глобальные массивы фиксированного размера. Где-то в main() перед всеми вычислениями сделайте memset(array, -1, sizeof(array)).

Попробуйте вместо sumupto() один раз подсчитать глобальный массив частичных сумм b[] и просто обращаться к нему напрямую:

int b [51];
...
b[0] = a[0];
for (i = 1; i < n; i++)
  b[i] = b[i-1] + a[i];

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

Надо по максимуму соптимизировать основной цикл (он у вас по v). Никаких функций кроме DP() внутри быть не должно.

Так-то по сложности должно с лихвой помещаться.

UPD: и уменьшите количество параметров у DP. Входные данные a и N - можно сделать глобальными переменными.

Как выполнить свертку сочетаний?

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

Если нужно не самое оптимальное решение, а просто что-то лучше "каждая тройка - свой изначальный список", то можете делать жадно. Изначально сделайте каждую тройку своим списком и потом пытайтесь к первому списку все остальные тройки (в случайном порядке!) добавить. Добавить можно, если все тройки из расширенного списка есть во входных данных (можно добавить {1,2,4} к {1,2,3}, если есть {1,3,4} и {2,3,4}). Если смогли тройку добавить то все покрытые этим новым списком тройки выбрасывайте из рассмотрения. Когда все тройки прошли, первый список выдавайте в ответ и выбрасывайте. Повторяйте процедуру на оставшихся тройках.

Как выполнить свертку сочетаний?

Дмитрий, Так, стоп, надо уточнить. Задача такая: функция из списка чисел делает список всех сочетаний-по-три. Этой функции скормили несколько списков. ВСЕ тройки даются на вход, надо восстановить изначальные списки. Если вариантов несколько, выдать тот в котором общая длина списков минимальна. Так?

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

Proshka17,
Нет, условие выхода я написал в секции "база:"

DP(0,0,0,0) = 1,
DP(0,*,*,*) = 0

Т.е. должно быть что-то вроде:

if (k == -1) { // у вас индексация с 0, у меня в формулах с 1.
  return (t==0 && j==0 && i == 0) ? 1 : 0;
}

Далее по коду, Тут много нареканий:

Вы где C() считаете, надо после КАЖДОЙ арифметической операции брать по модулю а то будет переполнение. Т.е. надо писать что-то вроде (a*b %z ) * c % z.

Факториалы не надо так считать, выглядит ужасно. делайте лучше push_back((facts.back() * i)%z). И гоните цикл от 1, предварительно сделав facts,push_back(1) и re_facts.push_back(1);

Теперь про динамику. Почитайте что-нибудь про динамическое программирование. Самое важное в рекурсии сделать мемоизацию. Без этого у вас не динамика а почти полный перебор. Вам нужен четырехмерный массив размерностью под максимальные значения четырех параметров функции, который изначально заполнен -1 (это число вы никак в своих вычислениях не получите, они же по модулю). В начале рекурсивной функции вы смотрите на значение массива [k,t,i,j]. Если там не -1, то сразу возвращаете его. Иначе считаете функцию как у вас и в конце, перед return sum (кстати, почему у вас 1 возвращается всегда?) запишите sum в массив. Таким образом для каждого набора параметров ("состояния") вы подсчитаете функцию максимум один раз.

У вас путаница - похоже, вы в каждом вызове DP() суммируете в ответ к задаче, но это же не работает. Вам в ответ надо взять сумму лишь некоторых (Не всех!) Dp(*,*,*,*). Поэтому каждая DP должна считать сумму в локальной переменной и вернуть ее. DP - функция, которая возвращает количество чего-то там, что я в первом ответе написал. В main() вы должны в цикле значения возвращенные DP() просуммировать.

Далее, вы где C() перемножаете и сумму считаете надо, опять же, после каждой операции брать по модулю Z.

Далее вы во втором С() вызываете от N, что неправильно. Посмотрите на мою формулу, там сумма a[1]..a[k], не до n, а до k! Нужно вычитать t из суммы пока что рассмотренных карт. Т.е. vec[0]...vec[k-1]. Можете эти кумулятивные суммы тоже предподсчитать.

Еще, глаза режет - min() в условии цикла вынесите за цикл в локальную переменную.
И цикл надо гнать до этого min() включительно. Т.е должно быть v<=... в условии. Вы можете все карты k-ого типа отдать первому игроку (но не более t).

И еще, вы забыли в конце "поделить" сумму на общее количество вариантов.

НО! Рекурсивная реализация у вас может не зайдет по memory limit exceeded. Потому что вам надо завести массив 51x251x51x51 long (можно хранить и возвращать 4-х байтное, ведь модуль влезает). Это 135mb, может не влезть. Я не знаю ограничения. Если влезет - хорошо. Если нет, попробуйте переписать это как динамику снизу-вверх. Я привел рекурсивное определение, потому что его проще понять, как мне кажется.

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

Proshka17 Надо бы уточнить, что я понимаю трактую "сколько уникальных карт" в условии задачи как "сколько различных типов карт игрок получил". {1,1,2,2,3} - это 3 уникальные карты. Если понимать условие по-другому (сколько типов карт у игрока ровно в одном экземпляре), то надо чуть-чуть подправить вычисления. Вместо условия v>0 будет v==1. Вместо v
Такая трактовка следует из вашего кода, вы там счетчик уникальных увеличиваете, если игроку хоть одна карта досталась.

Теперь ответ на ваш вопрос.
Если v>0, то первый игрок получил хоть одну карту последнего типа (k). Мы же эти карты выбрасываем из рассмотрения. Что остается у первого игрока? Сколько у него будет уникальных? Именно i - {v>0}, ведь с этими последними картами у него i уникальных. Значит если ему досталась хоть одна карта последнего типа, то карты этого типа прибавили 1 к i. Значит, после выкидывания остается i-1. Аналогично у второго игрока. В j последние карты подсчитаны как +1, если хоть одна карта ему досталась. Это в случае, если v

Правильные ли ответы в рамках составления алгоритма?

Опять же, по условию не совсем понятно, о каком счетчике идет речь. Видимо, о k, тогда ответ правильный. Если же вопрос обо всех операциях увеличения любого счетчика, то, также как и со сравнениями, ответ от N до 3N, потому что цикл for тоже увеличивает счетчик.

Как выполнить свертку сочетаний?

Тогда решение такое:
Зная количество троек (n), вы знаете, сколько изначально чисел было (x):
x(x-1)(x-2) = n

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

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

Вот вам пример для x=5: (a,b,c,d,e)
abc, abd, abe, bcd, bce ...

Не важно, что за числа a..e - важно что они в не убывающем порядке. Тогда тройка abc - точно будет самой первой.

Это все если вам на вход подаются ВСЕ тройки. Если же не все, то можно, например, взять все уникальные элементы и, если в какой-то тройке элементы повторяются, то брать эти элементы 2, или 3 раза, если вся тройка состоит из повторений.

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

Proshka17, Вы делаете что-то вроде полного перебора, а тут нужно комбинаторную магию и динамическое программирование применить. Я попозже распишу подробнее. Пока, напишите ограничения в задаче. Сколько карт всего, сколько типом может быть.

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

Какие есть алгоритмы сжатия числа?

Ну сжатий есть 2 вида. С потерями и без потерь. С потерями это у вас же - отрезать 2 младших бита.
Без потерь вам уже советовали - коды хаффмана, RLE, или какой-нибудь стандартный обобщенный сжиматель, типа zlib.

Почему рекурсия неверно отрабатывает?

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

Вот запустите на тесте x=2 y=2 z=1000 w=10.

Правильный ответ - 11 (x может быть взято от 0 до 10 раз, остальное - y). Сколько выдает ваша программа? 1024 небось?

> И вообще при числах 2 2 3 4 отработала верно.

Правильный ответ 3 (2 раза первый подарок; 2 раза второй подарок; первый+второй). Ваша же программа, если я не напутал, выдает 4.

Где найти параллельный алгоритм нахождения максимального паросочетания в графе?

ddd329, А вот это - хорошая статья.

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

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

Где найти параллельный алгоритм нахождения максимального паросочетания в графе?

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

А главное, там параллелизация делается по данным и отсутствует какое-либо объяснение, как они этого добились. Как будто, там граф разбивается на много независимых областей. Проблема только в том, что, если граф связен, таких независимых областей вообще нет. Но у них там граф случайный и с очень маленьким количеством ребер. Т.ч. вполне возможно, что там куча мелких несвязанных между собой компонент. Это очень крайний случай (найдите паросочетание в куче мелких графов сразу). Вся идея - запустить один и тот же алгоритм Куна кучу раз параллельно.

Еще там какой-то бред про итоговую линейную сложность(?!).

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

Почему JS решил задачу на рекурсию гораздо быстрее Python/Lua?

valis, немного оффтопик, но нормальное решение этой задачи будет таким быстрым, что вы разницы не заметите.

Надо просто завести массив на миллион элементов и запоминать в нем подсчитанные значения функции.

Вроде:

function getCollatz(number, iterations=1){
  if(res[number] > 0) return res[number];
  ...
  restult = GetCollatz(...);
  ...
  res[number] = result;
  return result;
}