Wataru

Бинпоиск - правильная идея. Но вот вы плохо считаете, сколько шариков один работник надует за заданное время. Вы линейно по одному шарику надуваете, а можно за 2 действия: поделите время на ti*zi+ci - узнаете, сколько полных групп шариков надуется. Остаток отдельно подсчитайте, поделив на ti. Учтите только, что оставшееся время может быть прервано на отдыхе - не насчитайте там больше zi шаров по ощибке.

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

Выведите 6^2, 66^2 и так далее. N до 20 хотя бы. Посмотрите на числа. Можете ли вы угадать цифру на заданной позиции без подсчета всего числа?

Подсказка, вы получите вот такие вот числа:

36
4356
443556
44435556
4444355556
444443555556
44444435555556
4444444355555556
444444443555555556
44444444435555555556
4444444444355555555556
444444444443555555555556
44444444444435555555555556
4444444444444355555555555556
444444444444443555555555555556
44444444444444435555555555555556
4444444444444444355555555555555556
444444444444444443555555555555555556
44444444444444444435555555555555555556
4444444444444444444355555555555555555556

Этот паттерн можно и доказать. Надо лишь представить возводимое в квадрат число как (10**n-1)2/3 и применить чуть-чуть элементарной алгебры, вроде формулы квадрата разности.

Вы не правы. Двумерный массив считает, можно ли набрать вес i используя первые j предметов. А не j-ый предмет.
Далее, обычно можно сэкономить память храня и пересчитывая только одну строку этого массива, но ДП все еще остается двумерным. Также числа Фибоначчи можно считать храня лишь 2 последних числа, но на самом деле там массив на n элементов в дп.

Этот трюк не всегда возможен. Например, если вам надо не только максимальный вес/цену найти, а еще и набор предметов. Восстановление ответа не всегда можно сделать лишь по последней строке.

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

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

Кстати, у вас матрица инцидентности неправильная: должно быть по 2 числа в каждой строке. Обычно ставят -цену у начальной вершины и +цену у конечной.

Ошибка в том, что у вас граф криво задан. У вас там ровно 6 списков. А размер графа - 7. Поэтому в MakeStep вы обращаетесь к graph[6], а это undefined behavior. А там непонятно, что происходит. Может вы таблицу портите каким-то значениями и никогда положительного значения не получаете. Скорее всего корраптите память через обращение к мусорным adj в std::array (который на стеке лежит) и получаете мусор в каких-то локальных переменных.

Во-первых, у вас цикл от 0 до 32 включительно. Т.е. вы на последней, 33-ей итерации пытаетесь преобразовать 0b100000 в bitset, фактически, второй раз учитывая вариант со всеми нолями. Вот почему вы получаете 33 а не 32.

Во-вторых, у вас ошибка с тем, что вы из bitmask берете биты, которые есть числа 0 и 1 и проводите над ними битовые операции, а не логические. И это у вас там 32-битные числа же! Для | и & оно еще совпадает с вашими ожиданиями, а вот ~ обращает ВСЕ 32 бита числа.

Поэтому ~(bitset[E] | bOrD) всегда выдаст или -1 или -2. Вы потом это пропустите через or, получите опять же -1 или -2 и в конце преобразуете это в bool. И вот тут-то оно всегда и станет true.

Чтобы это исправить, или используйте логические операции (||, &&, !), или вместо ~x используйте x^1, или в самом конце возвращайте результат с &1, чтобы значения остальных бит ни на что не влияли.

Посмотрите на ограничения в задаче. Введите вашей программе максимальный тест: 15 монеток и сумму примерно в 1000000000. Ваша программа попробует съесть дюжину гигабайт памяти и упадет.

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

В самом конце можно списки объединить. Последовательно. Или с критической секцией. Каждый поток должен получить первый и последний элемент списка. За две операции добавить список к глобальному и изменить последний элемент в глобальном списке. Ну, это если std::list использовать.

Вообще, если один раз в конце собирать все ответы, то можно их и в vector в критической секции складывать. Это все займет не больше времени, чем один раз ответ вывести.

Это обобщенная задача коммивояжора Multiple Traveling Salesman Problem.

Надо будет построить граф. Взять все точки доставки и склад как вершины и каким-нибудь google maps найти расстояние и пути между каждой парой точек. Эти длины пути надо записать в ребра.

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

Если у вас точек и куръеров действительно мало (не более 25 точек, не более 3 куръеров), то можно попробовать решать через динамическое программирование F(M, c1, c2, c3) - минимальная стоимость развезти товары из множества M так, что 3 куръера остаются в вершинах c1, c2 и c3. Переход - перебрать куръера и откуда он пришел из множества M. Посмотрите в википедии алгоритм для одного куръера, на трех это легко обобщается. Будет это работать за O(n^(c+1)2^n), где c - количество куръеров. n - количество вершин в графе. Сильно много куръеров или точек на карте этот алгоритм не переварит.

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

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

В вашем рассуждении ошибка в том, что вы не домножаете условную вероятность 2/6 на вероятность условия. Вы же полную вероятность считатете а P(A) = P(A|B)*P(B)+P(A|!B)*P(!B). У вас P(A|B) = 0, как вы заметили - если они встретились в первом туре, то во втором уже не встретятся. Но все-равно надо 2/6 домножать на P(!B) - вероятность того, что они не встретились в первом туре. А это 1-1/7 = 6/7. В итоге получается все то же 2/6*6/7=2/7.

Но рассуждения автора проще. Можно рассмотреть все независимые элементарные исходы "где в сетке оказался второй игрок". Их 7, они равновероятны по симметрии. Дальше надо домножить на вероятность, что они начиная так встретятся (выиграют свои матчи).

У вас решениe за O(n^3), ибо у вас там 2 вложенных цикла до n, а внутри еще и постоянно вызываются min/max, которые проходятся по всему массиву.

Ограничения же в задаче n<10^5. С такими ограничениями максимум O(n log n) решение уложится в 3 секунды.

Подумайте, как его можно изменить, чтобы работало сильно быстрее? Подсказка: сначала вы берете 1 минимальный элемент, потом 2 самых маленьких, потом 3, и т.д. На второй итерации вам уже как бы не надо искать минимум- вы его уже знаете. Вас интересуют только оставшиеся числа. На третьей итерации у вас уже 2 числа раньше найдены. Надо как-то переиспользовать предыдущие вычисления.

Что можно сделать с входным массивом, чтобы можно было получать несколько самых маленьких элементов быстро? Помните, что вам надо уложиться в O(n log n).

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

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

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

Более сложный вариант - когда у вас сразу запускаются все волны. Опять же, без лидера совсем сложно будет.
Тут, наверно стоит сначала в каждом отдельном параграфе найти все компоненты связности отдельно. Это будут промежуточные варианты.

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

Когда сервер получает сообщение о номере по призначному ребру, если этот номер меньше текущего у компоненты, она перекрашивается. И сообщение рассылается по всем остальным призрачным ребрам, торчащим из этой компоненты. Рано или поздно, все вершины одной компоненты по всем серверам будут помечены минимальным номером.

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

Обе книги классные. Мне Кормен показался попроще и по-понятнее. Кнут покрывает больше тем. Я бы начал с Кормена.