Wataru

Это задача о многомерном рюкзаке (multi-dimensional knapsack). Каких-то простых трюков, как с обычным одномерным рюкзаком тут нет. Только перебор с отсечениями.

Еще можно свести задачу к целочисленному линейному программированию. Вводите переменные - сколько штук каждого пункта съели, составляете линейные уравнения. Потом можно это все скормить какому-нибудь решателю. Сейчас много библиотек и они довольно быстро такие задачи щелкают. Гуглите "integer linear programming solver".

Вы наткнулись на важное свойство ассимптотического анализа. O(n^2) -означает, что на достаточно больших n, время работы будет примерно n^2 с точностью до константы. Эта самая константа может быть хоть 0.5, хоть 10000000.

Сравните 2 алгоритма:

// n(n-1)/2 инкремента.
for(i = 0; i < n; ++i){
  for (j = i+1; j < n; j++) {
    cnt1++;
  }
}
// n^2 инкремента.
for(i = 0; i < n; ++i){
  for (j =0; j < n; j++) {
    cnt2++;
  }
}

Оба алгоритма имеют O(n^2) сложность, но один делает примерно в 2 раза меньше операций.

Суть в том, что хоть алгоритмы и работают с одинаковой ассимптотикой, они могут работать разное время! Особые странности могут быть при маленьких n. O(n log n) алгоритм часто может быть медленнее O(n^2) алгоритма. Поэтому все настоящие реализации сортировок для маленьких массивов запускают более тупые квадратичные алгоритмы.

Если же вы хотите показать только ассимптотику, то возьмите n побольше, и тогда эти 30% будут незаметны по сравнению с десятикратным замедлением O(n^2) относительно O(n log n). Или нормируйте ваши сортировки. Искуственно ускорьте одни алгоритмы и замедлите другие, чтобы получить именно тот результат, который вы хотите. Но это как-то нечестно что ли. Если же вы все-таки хотите именно этого, назначьте каждой сортировке время C\*n^2 или С\*n\*log n миллисекунд. Прогоните алгоритмы сортировки без визуализации, подсчитайте, сколько операций замедления вы бы сделали (тот же самый код, что у вас, только вместо usleep() делайте sleep_count++). В конце подсчитайте коэффициент замедления - сколько каждый usleep должен спать, чтобы суммарно sleep_count их спал заданное время. И запускайте каждую сортировку уже с подсчитанными параметрами для usleep.

Еще есть вариант (если у вас все слова разные) - подсчитайте сколько раз каждая длина встречается в наборе.

Если вы видите, что у вас однобуквенных слов меньше, чем букв в алфавите - то можно выдать однобуквенное слово. Иначе, если двух-буквенных слов меньше |alphabet|^2, то можно выдать двубуквенное слово. И так далее. Вот нашли вы минимальную длину.

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

Пример. Алфавит - {a,b}. Слова: "a", "b", "aa", "ab", "bb".

Мы видим 2 однобуквенных слова. Никак. 3 двухбуквенных, но 3 < 2^2 - значит можно выдать двубуквенную строку.

У нас 2 символа в алфавите, интерпретируем a=0, b=1. "aa" = 0, "ab" = 1, "bb" =3. В битмапе останется пустым индекс 2. Это 10 в двоичной системе или "ba" в строках - это и есть ответ. Да еще и лексикографически минимальный.

Если слова могут повторятся, то можно чуть изменить решение: точно также перенумеруйте все возможные слова в вашем алфавите. Сначала будут однобуквенные, потом двубуквенные и т.д. При переводе строки в индекс - также переводите из |alphabet|-ичной системы счисления. Но для слова из l символов прибавляйте смещение |alphabet|^(l-1)+|alphabet|^(l-2)+... |alphabet|^1. Точно так же, если в процессе вычисления видно, что индекс не поместится в битмапу (больше количества строк), то можно забить на эту строку. Поэтому же можно сразу пропускать слишком длинные слова.

Опять же, помечайте бит в битмапе. Потом найдите первый нулевой бит. И назад преобразуйте в строку - сначала найдите смещение (суммируйте степени |alphabet|, пока они не перевалят за текущий индекс). Так вы поймете, сколько символов у вас в строке. Вычтите смещение и переводите индекс в |alphabet|-ичную систему счисления.

Этот вариант в среднем может работать чуть дольше, но все так же очень быстро.

Еще, оба эти варианта самые экономные по памяти.

Куча ошибок. Вы читаете запросы в массив B и больше нигде не используете. Конструкция A{m<i] вообще удивительна. Массив надо отсортировать.

У вас простой DFS. Если ему не повезет пойти не по отрицательному циклу, но при этом обойти какие-то его вершины, то вы запорите перебор и этот цикл никогда не найдется.

Чтобы через DFS найти отрицательный цикл - придется перебирать ВСЕ циклы. Для этого надо не помечать вершины как visited. Правда, работать будет очень медленно и почти гарантированно не пройдет по time limit, ибо циклов в гарфе может быть экспоненциально много.

Edit, вот вам пример. В графе только один отрицательный цикл 1->2->3->1. Но есть еще ребро 1->3. Если вы начнете из 1-ой вершины, потом возьмете ребро 1->3, то дальше вы из вершины 3 никуда не сможете пойти, уберете ее из стека и пометите как visited. Далее вы рассмотрите ребро 1->2 а потом из вершины 2 ребро 2->3 вы пропустите, потому что вершина 3 уже visited.

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

Проблема в том, что GCD(0,1000) = 1000. А у вас цикл ни разу не выполнится и не найдет ничего.

Ваше решение не работет, если отрезок вертикальный или горизонтальный. Ответ должен быть 0, вы же выведите что-то другое.

Но, когда вы это исправите, ваше решение скорее всего не пройдет по времени. Ищите наибольший общий делитель алгоритмом евклида.

Вы правильно поняли, какого вида числа будут в последовательности (перемноженные степени 2, 3 и 5).

Проблема в том, что вы, например, пропустите число 2^23, которое входит в первые 10000.

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

Но скорее всего, придется поменять алгоритм. Поскольку ограничения маленькие, то тут можно делать что-то типа BFS. Вы вычисляйте числа в последовательности по порядку. И поддерживайте множество возможных следующих чисел. Каждый раз дописывайте минимальное число из кандидатов к последовательности и добавляйте к кандидатам это новое число, умноженное на 2, на 3 или на 5. Это будет квадратичный алгоритм. Можно использовать heap или какой-нибудь set, тогда будет за O(n log n).

Еще есть линейный алгоритм. Он получается из предыдущего так: все кандидаты разбейте на 3 множества - те, которые получены домножением на 2, на 3 и на 5. Каждое такое множество в итоге будет тупо сама же последовательность, домноженная на 2, 3 или 5. Поэтому единственное, что вам надо знать для полного описания кандидатов - это какое число из последовательности было домножено на 2,3 или 5. Это три индекса.

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

Простой в реализации метод: держите отрезки в каждом элементе отсортированными и непересекающимеся (если два отрезка пересекаются - объедените их).

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

Если же список очень длинный, а ответ ожидается маленький, то есть более быстрый метод. Но он сложный в реализации. Нужно реализовать персистентное дерево поиска. Можно его реализовать на основе персистентного дерева отрезков. Это такая структура, в которую можно добавлять элементы, и удалять их за O(log n). Также можно обходить все элементы за O(log n + (их количество)). Кроме того, сохраняются все версии дерева после каждой операции и общее количество памяти будет O(к log n), где к - количество операций.

Эта структура будет использоватся для хранения предподсчитанных ответов. Если все ваши отрезки нарисовать на одной прямой, то она разобъется на O(n) отрезков, все точки которого будут давать один и тот же ответ при запросе. Мы эти все ответы компактно сохраним.

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

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

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

Это решение требует O(n log n) памяти (где n - количество всех отрезков) и O(n log n) времени на предподсчет и O( log n + (ответ)) времени на обработку ответа.

Более простое решение, где ответы считаются так же сканирующей прямой, но сохраняются просто в виде списков, а не версий персистентного дерева, может требовать O(n^2) памяти. Но будет работать быстрее, конечно.

Сначала инвертируйте число (битовое не). Теперь надо найти самый правый единичный бит.
Можно вычесть из числа 1, тогда поменяются все биты вплоть до этого искомого. Значит xor изначального числа и его же минус 1 даст нам столько единичных бит на конце, каков был номер искомого бита.

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

// пусть x = 00001011b
x = ~x;  // 11110100b
x = x ^ (x-1);  // 11110100 xor 11110011 = 00000111
x = ((x >> 1) & 01010101b)+(x & 01010101b);  // 00 00 01 10
x = ((x >> 2) & 00110011b)+(x & 00110011b);  // 0000 0011
x = ((x >> 4) & 00001111b)+(x & 00001111b);  // 00000011 = 2
x -= 1; // индексация с 0

Отдельно надо проверить, вдруг изначальное число было 255 - в таком случае искомого бита нет, но этот код вернет 7.

Можно сделать для большего количества бит, надо только еще операций добавить и маски расширить. Для 32-битных чисел надо будет добавить еще 2 операции.

Еще есть вариант с ассемблером в x86 есть операция popcnt.

Что вы подразумеваете под словом "эффективный"?

Проблема в том, что циклов в графе из n вершин может быть O(n!) (n-факториал): представьте клику - граф, где есть ребра между всеми парами вершин. Любое подмножество вершин, да еще и в любом порядке, задает элементарный цикл.

Обычно под словом "эффективный" подразумевают полиномиальный алгоритм. Такой алгоритм тут, очевидно, не существует (потому что надо перебрать экспоненциальное количество объектов).

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

Используйте функцию max.

Значение в каждой ячейке будет

max(0, (тукущее значение) - max(0, (платеж) - (сумма всех следующих ячеек)))

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

Простейшая задача на bfs. Без кода сложно сказать, где накосячено.

Никакого переполнения быть не может, bigInteger вам не нужен. Даже long не нужен: максимальная длина пути - 10000.