Wataru

Есть решение, но оно на плохих тестах, если не повезет, не влезет в лимит.
Чтобы вам повезло, можно "перемешать" входные данные случайным образом. Заведите случайную перестановку. Далее внизу я про нее как бы забуду, но когда я говорю спросить про элементы i и j вы должны справшивать про p[i] и p[j]. Как только вы найдете, что 0 в p[k] - про эту случайную перестановку можно забыть и далее использовать элемент p[k] для востановления перестановки.

Спросите про элементы 0 и 1. Запомните a[0] | a[1].

Вот у вас есть 2 элемента каких-то, вы знаете их позиции и a[i]|a[j]. Мы будет добавлять к ним элементы 2..n-1 по одному, все время выбрасывая один или несколько, в которых нуля точно нет.

Вот есть у вас элеметы x, y и вы знаете a=x|y. возьмем новый элемент z и спросим b=y|z.

Мог ли 0 быть в x? тогда бы a = x|y=0|y = y. Т.е. предыдущее значение a должно вкладываться в новое b как множество единиц. Аналогичный критерий для возможности z быть нулем - b вкладывается в a.

Eсть 4 взаимоисключающих варианта, как множества бит a и b соотносятся:
1) a целиком вкладывается в b, или a|b == b, a != b, например 5 вкладывается в 7.
2) b целиком вкладывается в a, или a|b == a, a != b
3) a == b
4) ничего из выше перечисленного, например, 3 и 6.

Мы уже становили, что x может быть 0 только в случаях 1) и 3). z может быть нулем только в случаях 2) и 3).

В каких случаях может быть нулем y? только в 1), 2) и 4)

Теперь алгоритм, если выпал случай 1), то мы выбрасываем z. При этом значение текущего OR уменьшилось как множество.

Если выпал случай 2), то мы выбрасываем x. При этом значение текущего OR уменьшилось как множество.

Если выпал вариант 3), то мы выбрасываем y и нам придется спросить x|z, ведь нам надо знать OR оставшихся элеметов. Это плохо тем, что мы спросили 2 раза, рассморев один новый элемент. В неудачном случае мы бы задали 2n вопросов только ища 0 и у нас не осталось бы квоты на восстановление самой перестановки.

Но тут есть 2 подварианта. 3а) Если значение x|z стало меньше, как множество, то ок. 3б) Но оно еще могло бы остаться таким же, т.е. x|y=y|z=x|z. Но в этом случае, по аналогичным рассуждениям нуля не может быть нигде среди этих трех элементов! А значит мы можем выкинуть и их все, избавившись от двух элементов за два вопроса.

Если выпал вариант 4), то мы выбрасываем x или z.

Таким образом задав от n до 2n (в самом неудачном случае) мы получаем в конце 2 элемента в одном из которых точно 0, а второй - a.

Чтобы восстановить кто из двух оставшихся элементов кто: по ходу отсеивания, задавая любой вопрос запоминайте для какой пары чисел вы видели нулевой бит в каждом разряде. (Т.е. спросили про i|j получили ответ 5. Тут второй бит 0, значит запомнили, что i|j дает 0 в бите 2. И поддерживайте массив для всех разрядов).
Если вам хоть сколько-нибудь повезет. вы наберете достаточно таких примеров.

Теперь пройдитесь по всем примерам, что вы ранее видели и выберите тот, который имел 0 в разряде, где у a стоит 1. пусть это были элементы i и j. Теперь спросите x|i. Если и там этот разряд 0, то x=0, иначе у=0.

Тут почти нарисовался строго убывающий инвариант - размер множетсва бит в OR для текущих кандидатов, но пункт 3б) его ломает, ведь мы получаем 2 новых элемента и множество может стать любым. Но случайный порядок вопросов должен сделать этот вариант маловаероятным. У вас запас примерно 150 впоросов на максимальном тесте. Возможно тут можно придумать какую-то строгую схему, где какой-то инвариант строго убывает на лишних вопросах и может убывать не более 100 раз.

У вас проблема в решении в том, что вы сравниваете 2 обхода. Это неверно для, как вам уже приводили в пример, этих двух деревьев:

1
 \
  2
   \
    3

    3
   /
  2
 /
1

Тут оба обхода вернут 1,2,3.

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

Но есть лучшее решение, через DFS или BFS: вы делайте обход одновременно на двух деревьях. Т.е. у вас параметр функции dfs или в очереди в bfs лежат сразу 2 вершины - по одной из каждого дерева. Вы проверяете, что у них значения одинаковые и что у них у обеих одновременно есть или нет левого и правого ребенка. Потом вызываетесь/кладете в очередь одновременно левых детей и одновременно правых детей. Если в процессе обхода вершины оказались разными, или где-то есть ребенок, а где-то нет - то деревья не равны.

Очень логично реализовывается в виде DFS (ниже псевдокод):

Equals(t1, t2):
   // обработать случай null одного или обоих деревьев.
   return t1.v == t2.v && Equals(t1.left, t2.left) && Equals(t1.right, t2.right)

Все предельно логично - 2 дерева равны, если у них равны корни, левые поддеревья и правые поддеревья.

Кстати, ваше решение, если его исправить, тоже будет за O(n).

Я, правда, не понимаю, почему нельзя просто объединить все массивы в один (будет просто список уникальных элементов). Возможно вам нужно максимальное количество массивов.

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

Суть в том, чтобы построить граф, где все различные элементы всех массивов будут вершинами. Ребра есть между двумя вершинами, если соответствующие им элементы присутствуют в одном и том же входном массиве.

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

Чуть проще и быстрее будет работать решение через систему непересекающихся множеств (DSU). Сначала пройдитесь по всем массивам и, как и в первом решении, перенумеруйте все уникальные элементы. Заведите DSU, где каждый элемент - сам себе множество.

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

В зависимости от уровня задающего задание, ваш ответ правильный или не совсем правильный.
Да, именно if-ов сравнений 2N. Но внутри цикла for тоже закопано N сравнений. Как цикл-то работает? У него есть переменная счетчик и он ее сравнивает с граничным условием. Это хорошо видно на блок схеме - блок-цикл имеет 2 выхода. Значит в нем есть ветвление и, следовательно, сравнения.

Так что более точный ответ 3N. Еще более точный ответ 4 N. Потому что функция readln тоже должна какие-то сравнения делать, чтобы остановить ввод на конце строки, но это уже nitpick, который от вас почти точно не ожидается.

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

Пусть общее количество карт - N.

Для простоты понимания, давайте забудем про колоду, просто карты раздаются как-то в 2 кучки по N/2 карт. Это пригодится попозже. Удобнее не вероятность считать, а количество способов раздать карты. Потом надо будет поделить количество хороших способов на все способы.

Сразу комбинаторно подсчитаем, сколько всего способов есть. Это просто количество всех различных колод. Гуглите "перестановки с повторениями". Формула будет такой:
N!/ a[1]! ... a[n]!
Раз мы на это число в конце будем делить, то сразу же считайте перевернутую формулу: подсчитайте факториал числа всех карт по модулю, обратите, умножьте на все маленькие факториалы.

Теперь самое главное, подсчитаем количество способов раздать карты так, что у всех поровну уникальных карт.
Динамическое программирование DP(k, t, i, j) - сколько способов раздать первые k типов карт так, что у первого игрока t карт всего, из них i уникальных, а у второго игрока j уникальных карт (при этом мы знаем, сколько у него всего карт - a[1]+...+a[k] - t).

База:

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

Ответ:
sum {i=1..n} DP(n, N/2, i, i)

Пересчет:

DP(k,t,i,j) = sum{v=0..min(a[k],t)} DP(k-1, t-v, i - {v>0}, j-{v < a[k]}) * C(t, v) * C(a[1]+a[2]+...+a[k]-t, a[k]-v)

Тут надо объяснить: мы перебираем, сколько карт последнего типа досталось первому игроку: v. Это все разные колоды, поэтому их надо суммировать. Как бы убираем все карты этого последнего типа из рассмотрения. Что остается? То же самое ДП, но типов на 1 меньше, у первого игрока на v карт меньше и уникальные карты надо уменьшить на 1, если какому-то игроку хоть одна карта досталась. Но есть еще множители - это количество сочетаний. Эти самые v карт последнего типа могут быть на любом из t мест в колоде у первого игрока. Аналогично для второго игрока. Тут надо умножать, потому что любую колоду из предыдущего состояния ДП можно разбавить картами последнего типа в разных позициях и все эти способы дадут разные результирующие колоды. Надо домножить на оба сочетания, потому что мы независимо можем тасовать карты у первого и второго игрока.

Сочетания считаются факториалами С(n,k) = n!/ k! (n-k)!.
Я бы посоветовал предподсчитать все факториалы до 500 по модулю в массив, а так же обратные к ним.

Еще, если не будет влезать по памяти, обратите внимание, что в ДП достаточно хранить лишь 2 слоя по первому параметру. Т.е. надо места для 2*500*50*50 элементов, что для 4-х байтных значений будет занимать ~10mb памяти. Может даже long long можно хранить. Но тут надо переписать ДП снизу вверх, а не рекурсивно. Просто посмотрите, какие состояния куда плюсуются и с какими множителями. В этом случае вы будете не убирать карты последнего типа, а добавлять карты нового типа. Опять же, перебирайте сколько кому этих карт достанется. Надо только осторожно смотреть множители - С(сколько карт после добавления, сколько добавили).

Теперь прикинем на коленке сложность вычислений таким алгоритмом.
Само ДП имеет состояний 50*500*50*50 и пересчет 11 вариантов. Если все перемножить, получается что-то меньше 700 миллионов - в одну-две секунды должно влезать.

Полный перебор у вас, занимает что-то типа 11^50 - никогда не дождетесь на сколько нибудь не тривиальном тесте.

Ваша программа ломается, если X=Y, например.
Чтобы ее исправить, вместо веса edge и сравнения его со стоимостью товара, передавайте в функцию число от 1 до 3. Если число <=1, то можно брать x и передавать 1. Если <=2 - то можно брать y и передавать 2, и т.д.

Однозначного ответа на Ваш вопрос в такой формулировке нет.

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

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

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

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

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

(если речь про двудольный граф)

Ищите parallel dfs или parallel maximum flow.

Собственно, параллелизации поиска паросочетаний я нигде не видел. Слишком специфичная задача.

Однако, есть алгоритм поиска через максимальный поток.
Если добавить в граф исток, соединенный с левой долей, и исток, соединенный с правой долей, а пропускные способности сделать по 1, то любой поток тут будет равнозначен паросочетанию. Есть алгоритм Форда-фолкерсона, там основная работа - это делать dfs в графе для поиска пути из истока в сток. Собственно, можно распараллелить этот dfs. Это более популярная задача и алгоритмы гуглятся легко.

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

г) не правильно подсчитано.

Составьте уравнение. Вот есть у вас функция времени для n входных данных f(n) на компе B. На компе A время выполнения будет - f(n)/100, ведь он в 100 раз быстрее.

Теперь обозначьте за x объем данных на компе A, который надо найти. Тогда у вас f(x)/100 = f(n). Подставьте нужную функцию вместо f() и найдите x. Спойлер, будет похоже, но не то, что у вас в вопросе указано.