Как решить задачу с CodeWars Simple Fun #159: Middle Permutation?

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

Но это в питоне. В какой-нибудь java пришлось бы использовать специальный BigInt, потому что стандартные целые тоже фиксированной длины.

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

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

Из предложенного решения ничего не выкинуть, даже для 10-ти контейнеров.

Как решить задачу с CodeWars Simple Fun #159: Middle Permutation?

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

Если символов четно - то ответ средний символ, а за ним все остальные по убыванию. Например, "cfedba"
Если символов нечетно, то овтет средний символ, предыдущий, а за нимим все остальные по убыванию. например "nmzyxwvutsrqpolkjigfedcba"

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

Ничего не понятно. Приведите пример входных данных и ожидаемый ответ. Минимальное количество контейнеров, это тех которые используем? Длина чего у вас должна быть минимальная? Какая метрика приоритетнее (т.е. что лучше - решение покороче но с большим количеством контейнеров или подлиннее но с меньшим)?

Как хранить граф с большим количеством вершин?

dalbio,
Построить просто - для каждого ребра u,v делайте next[u].push_back(v);. Если граф неориентированный, то симметрично добавляйте u в вектор для v.
Сначала не забудте выделить сам вектор: next.resize(n+1);

Обход Binary-Tree, как сделать быстрее?

> сравниваем именно упорядоченный результат обхода. В одном цикле можно, с двумя очередями, но это другая реализация того же самого алгоритма: получаем последовательность. Точно ведь линейно?

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

Точно линейно! Каждую вершину обойдете не более одного раза, вершин линейно.

> Есть основания полагать, что интервьюер таки умный и это я чего-то не понял.

Если интервьювер действительно ругался на вот этот ваш код, считая что он нелинеен, то он "чего-то не понял":

def tree_walk(node):
    yield from tree_walk(node.left)
    yield node.value
    yield from tree_walk(node.right)

От сбалансированности меняется глубина дерева. У сбалансированного она - O(log N). У не сбалансированного она - O(N). Это имеет значение тольуо если вы не обходите ВСЕ дерево, а спускаетесь один раз, например, ища заданный элемент в дереве поиска. В задаче сравнения двух деревьев вы будете делать ПОЛНЫЙ обход дерева: вы же их целиком сравниваете, да?

Лишние тупики - НЕТ! Что в несбалансированном дереве из N вершин будет N+1 "тупиков", что и в сбалансированном их будет столко же. Это просто доказать. Сколько всего left и right у всех N вершин? 2N. Сколько из них ведут не в тупики? Ровно N-1 - каждая из вершин, кроме корня, занимает чей-то left или right. Вот и получается, что тупиков будет ровно 2N-N+1 = N+1. Еще раз, неважно, как ваше дерево устроено: палка ли, сбалансированное ли - тупиков всегда одинаково. И обход будет занимать ровно то же самое время - O(N) (если смотреть на худший случай. Так-то, при правельной реализации вы можете прекратить обход заранее, например, если корни не совпали).

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

Обход Binary-Tree, как сделать быстрее?

Максим Булатов,

Интервьювер - дурак был. Рекомендую отправить рекрутеру жалобу. Просто, что бы ему стадно было. Тут никаким боком ни N log N, ни N^2 вылезти не могут. У вас самый обычный DFS написан - работает за O(n).
Тут другая проблема: если node.left нет, то вы вызываетесь от Null (или None, или что там в питоне) и при попытке уже от этого взять node.left программа упадет с ошибкой.

Но если это исправить (добавив if node: в начало функции, например, или как вы с проверкой node.left перед вызовом, что почти то же самое, лишь чуть чуть сэкономит на вызовах функции), то работать будет так же - за O(n).

> Вопрос такой: DFS он ведь за O(n), а если два раза вызвать, то ведь все равно O(n), правильно?

Будет O(2n) = O(n). Но вам не надо 2 раза вызывать BFS! Вы один раз вызываете, но одновременно по двум деревьям, с двумя параметрами! и двигаете одновременно оба параметра или влево или вправо.

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

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

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

Если аккуратно подсчитать количество итераций, то будет 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 тоже увеличивает счетчик.