Wataru

Проверка на малых числах не всегда работает. там фибоначи, квадрат и черт знает что похожи.

Если у вас там что-то вроде for "i=1...n do for j = i..n do" или каике-то еще 2 вложенных цикла, где внутренняя переменная бежит от или до внешней переменной, то точное количество итераций будет n(n+1)/2, что есть O(N^2).

Ваше последнее суждение - верно.

Если у вас задача - что в выбраных наугад картах есть хотя бы один туз и хотя бы одна черва, то надо найти Count(>0 червей И >0 тузов). Можно это инвертировать, считая все плохие варианты, вычев их из всех вариантов:

Count(>0 червей И >0 тузов) = Count() - Count(0 червей ИЛИ 0 тузов)

Дальше, COUNT(A или B) можно разложить на Count(A) + Count(B) - count(A И B).

Финальная формула для ответа:

Count() - Count(0 червей) - Count(0 тузов) + Count(0 червей И 0 тузов)

Фактически, это форомула включения-исключения. Но в итоговой формеле все просто счиатать:

Count() = C(5,36) - все варинты: сочетания по 5 из 36.

Count(0 тузов) = С(5, 32) - нельзя брать тузы

Count(0 червей) = С(5, 27) - нельзя брать 9 червей

Count(0 червей И 0 тузов) = С(5, 24) - нельзя брать 9 червей и 3 оставшихся туза.

Подсчитайте через фаториалы и сложите с правильными знаками.

Если же задача - ровно один туз и ровно одна черва, то тут 2 варианта. Или туз-черва взят, или это две разные карты.

В первом случае оставшиеся 4 карты - любые из 24 карт не-тузов-не-черв, т.е. эта часть - C(4,24). Во втором случае, вы берете какой-то из 3 тузов, какой-то из 8 черв и оставльные 3 карты из не-тузов-не-червей, т.е. ответ 3*8*C(3,24). Обе части просуммируйте.

Вы говорите, что пытаетесь брать числа, чтобы "портить" меньшие биты, но ведь это может быть не так.
Если у вас числа 4,4,4,4,5,6,1,1 - то выгодно брать именно 6, потому что оно сделает второй бит единицей, что никак невозможно сделать, взяв 5.
У вас неправильное решение задачи.

Правильное решение такое: Найдите самый старший бит, в котором нечетное количество единиц в массиве a.

Если таких нет - то ответ Draw. Потому что, если в каком-то разряде единиц четное количество, и x из них достанется первому игроку, то второму достанется 2k-x, что будет иметь ту же четность, что и x. А значит в этом разряде итоговые значения отличаться не могут вообще. Как числа не распределяй, даже если игроки могут делать разное количество ходов.

Теперь мы знаем, что в этом разряде различие точно будет. Потому что нельзя нечетное количество единиц распределить на 2 группы с одинаковой четностью. Победа определяется только этим разрядом, ведь он самый старший из различий. Теперь у нас есть 2k+1 чисел c 1 в этом разряде и n-2k-1 чисел с 0 в этом разряде. На биты дальше смотреть не надо - кто возьмет нечетное количество чисел из 2*k+1 - тот победил.

Т.е. вам дальше надо решить совсем простую задачу: Дана пара чисел (i,j), i - нечетно, есть i нужных объектов и j ненужных, игроки по-очереди берут объекты. Кто возьмет нечетное количество нужных объектов - тот и победил.

Тут для вывода решения можно написать динамическое программирование, которое для пары (i,j) - будет говорить, сможет ли игрок взять четное/нечетное количество нужных чисел, если их i, и еще есть j ненужных. При расчете перебирайте варианты, какой из типов объектов берется и смотрите, а сможет ли оппонент вам четность испортить на меньшей задаче.

Дальше надо посмотреть на паттерн на маленьких числах и составить решение, потому что вся эта динамика у вас по времени не зайдет для данных ограничений.

Мне лень решать дальше задачу, но похоже, что при i=1 ответ - WIN, при i>0 - ответ Win, если i+j=n - четно. Иначе - Lose.

У вас неправильно в коде - надо считать count() не на всем массиве, а только между low и high.

Тогда сложность всего алгоритма будет O(n log n). То, что у вас сейчас сделано будет иметь сложность O(n^2).

Избавиться от подсчета в данном решении никак нельзя.

Тут мало выбирать только первое число и гнать обычный бинарный поиск. Важное ограничение - вы не можете использовать один и тот же цвет дважды. Есть еще спецэффект, что случаи c=n-1 и с=n можно разделить только перекрасившисть с 1 на n или наоборот. Т.е. вы не имеете права краситься в 1 или n-1, только если не знаете точно, что C меньше n или что С одно из двух крайних значений.

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

Детали зависят от конкретной реализации, но обычно все основано на leaky bucket.

В целом, роутер считает, сколько байт он пропустил, и если видит, что байт слишком много в еденицу времени, лишние пакеты просто дропаются (отбрасываются без пересылки их дальше). А дальше уже источник трафика как-то подстраивается. Если трафик TCP - то отправитель замечая потери будет снижать скорость отправления пока потери не прекратятся. Если же используется UDP, и приложение не надстроило над ним каких-то rate-control механизмов, то так и будет посылать лишние пакеты, которые будут уничтожатся роутером. До него трафик будет без ограничения скорости, а дальше пойдет уже ограниченный.

Обычное k-d дерево, как по ссылке у freeExec тут будет работать неплохо и будет потреблять сравнительно мало памяти. Но оно не дает гарантию времени выполнения. Может так получится, что вы обойдете почти все вершины в дереве (то же O(n), n - количество точек), даже если в прямоугольник не попала ни одна точка. Правда для этого нужно иметь весьма специфическую конфигурацию точек и очень прямоугольник с большим периметром. Я думаю, этот вариант вам лучше всего подходит, если точки более менее случайно разбросаны и экран занимает лишь маленькую, более менее квадратную область.

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

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

Дерево отрезков, оно же segment tree - это структура данных, которая делит все пространство координат на половинки, пока не получит в листах по одной координате.

Дерево поиска - это сбалансированное двоичное дерево поиска. Типа avl, красно-черных или декартовых деревьев. Возможно стандартный Set из JS или его аналог тут подойдет.

Суть решения такая - вы разбиватете все пространство по одной координате (скажем, y) деревом отрезков. Каждая вершина этого дерева отвечает за некоторую горизонтальную полосу c фиксированными y координатами и ханит в себе Set всех точек, которые в эту полосу попадают. В Set храните какие-то ссылки на точки (допустим, их id в массиве всех точек), упорядоченные по x координате, а потом по y координате, а потом по id.

Это фактически 2D дерево отрезков, но наивная реализация требовала бы MaxW*MaxH памяти, что слишком много. Замена внутренних деревьев отрезков на Set позволяет сильно сэкономить в памяти.

При добавлении/удалении точки надо в дереве отрезков найти все вершины, которые покрывают ее y координату (их будет Log MaxH) и в их сетах удалить/добавить вершину с заданными (x,y) координатами.

Важно, что set упорядочен по x координате, не той же по которой упорядочено дерево отрезков.

Для получения всех точек в прямоугольнике стандартным обходом дерева отрезков найдите log(MaxH) вершин покрывающих прямоугольник по y координате. Теперь для каждого из найденных Set() найдите upper_bound левой границы. Теперь обойдите точки в Set, начиная с этой, пока не выйдете за правую границу прямоугольника и рисуйте их.

Эта структрура данных найдет все точки в прямоугольнике за O(k + log(MaxW) * log N), где k - количество точек в прямоугольнике, MaxW - высота пространства, N - общее количество точек. При этом каждая точка будет хранится ровно log(MaxW) раз, т.е. по памяти эта структура данных не такая и прожорливая - O(n log(MaxW)).

Единственная проблема: похоже стандартный Set в JS не умеет делать upper_bound. Если точки не меняются часто, то можно вместо Set хранить массив точек отсортированный по x и бинарным поиском искать левую границу при обходе прямоугольника. Иначе же используйте вместо Set более продвинутую реализацию дерева поиска, которая поддерживает upper_bound. Возможно даже есть что-то стандартное в JS или есть готовые библиотеки - я не специалист.

Вам обязательно отвечать на вопрос об электричесвте в конкретном доме по мере добавления ребер/вершин в граф?
Если вам только тесты надо делать, то можно сначала создать весь мир, а потом поспрашивать его о статусах домов. При чем сами вычисления (обход графа) можно сделать только один раз, получить данные по всем домам и потом их проверить.

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

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

Можно сделать гораздо быстрее. Если связи между домами только добавляются (но ни в коем случае не удаляются), то можно использовать систему непересекающихся множеств (DSU). Изначально каждый дом и электростанция - сами себе множество. В каждом множестве поддерживайте счетчик активных электростанций (изначально у домов - 0, у электростанций - 1). Это просто в реализации: у вас есть какой-то массив ссылок root, элеметы которого указывают сами на себя только в корне множества. Заведите второй массив, который будет по тем же индексам хранить счетчики для элементов. Точно также в вики по ссылке выше поддерживатеся rank.

При добавлении провода вы должны слить 2 множества. При этом пересчитайте счетчик (прибавьте счетчик нижнего множества к счетчику верхнего множества).

При запросе на статус дома возьмите счетчик активных станций для его множества и проверьте, что он положителен. При выключении/включении электростанции измените счетчик соответствующего множества на +1 или на -1.

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

У вас при вычислении cache числа не берутся по модулю. А значит очень быстро переполняют long long и случается фигня. Ведь цикл может начаться на очень больших числах. Вам надо всегда при вычислении брать по модулю m.

И, очевидная оптимизация - так как у вас fib() вызывается от увеличивающихся по порядку индексов, вы вместо функции делайте сразу же seq.push_back((seq[i-2]+seq[i-1]) % m);

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

Можно хранить список взятых чисел в глобальном массвие/списке. Но надо аккуратно его откатывать. Перед рекурсивным вызовом, если добавили новое число, то после вызова его из массива/списка удалите. Так будет потребление памяти O(n) вместо O(n^2).

Что-то типа такого:

void Generate(int n, int next, int sum, vector<int> taken) {
  if (next > n || sum > n) return;
  if (sum == n) {
   Output(taken);
  }
  Generate(n, next+1, sum, taken);
  taken.push_back(next);
  Generate(n, next+1, sum+next, taken);
}

...

Generate(n, 1, 0, {});

Но это решение будет не самым быстрым - ибо оно будет заходить в длинные "тупики".

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

Заведите двумерный массив n x (n+1). d[i][j] будет хранить, можно ли собрать сумму j используя числа от 1 до i.

База - d[0][0] = true (нет чисел - ноль набрать можно), d[i][0] = false (нет чисел. Не ноль набрать нельзя).

пересчет: d[i][j] = d[i-1][j-i] or d[i-1][j] (или берем текущее число или нет)
Естественно, первый вариант рассматривается только если i<=j. Можно подсчитать этот массив или рекурсивной функцией с запоминанием или просто тупо двумя вложенными циклами.

Потом модифицируем нашу рекурсивную функцию из первого варианта. Теперь она будет как бы идти с конца и параметры будут - сколько первых чисел мы можем использовать, какую сумму должны набрать и какие бОльшие числа уже взяли. В функции опять 2 варианта - или берем текущее число или нет. Но при этом смотрим в массиве d[][], а можем ли мы вообще набрать нужную сумму данными нам числами. Если нет - сразу возвращаемся. Когда пришли к оставшейся сумме в 0, выводим набранные числа.

Оба решения имеют временную сложность O(2^n), но второе будет в несколько раз быстрее, потому что не перебирает никаких тупиков. Возможно, если еще подумать можно избваиться от динамического программирования и вообще вывести формулу, когда из чисел от 1 до i можно собрать заданное число k (может там формула типа i*(i+1)/2 <= k).

Если у вас задача стоит не вывести все наборы (их много! Порядка 2^n), а подсчитать их количество, то тут не надо рекурсивного перебора, а можно подифицировать динамическое программирование, которое будет вместо true/false считать сколько способов собрать из i чисел сумму j. будет формула вида d[i][j] = d[i-1][j] + d[i-1][j-i]. Тогда все решение будет за O(n^2) по времени и можно сделать его O(n) по памяти, если немного подумать (и хранить только две или одну строку матрицы d).

Давайте составим рекурентное соотношение. Пусть F(n) - сколько работает ваша функция при входе в n элементов.

В функции:
- Выделяется новый массив: n операций
- Вызывается функция для укороченного массива: F(n-1) операций
- Цикл по всем перестановкам n-1 элемента: (n-1)! повторений
- Вложенный цикл по позициям: n*(n-1)! = n! повторений
- вложенное в циклы построение новой перестановки: n*n! операций

Итого F(n) = n + F(n-1) +n*n!

Можно раскрыть рекурсивно и получим:
F(n) = 1 + 2 + 3 + ... + n + n*n! + (n-1)*(n-1)! + (n-2)*(n-2)! + ... +1
Аккуратно посмотрев на это можно понять, что все члены, начиная от (n-1)*(n-1)!, cумарно меньше n*n!, а первые n членов вообще мизерные и их можно отбросить.
В итоге, F(n) = O(n*n!).

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

Сложность по памяти такая же - ведь вы там в итоге храните все перестановки, их n! и каждая занимает n. Но это оценка ассимптотики - O(n*n!). На самом деле будет чуть больше n*n! элементов, потому что хранится список ответ и список для меньших перестановок, плюс стек и промежуточные массивы при конкатенации.

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

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

Вместо ceil(a/b) используйте (a+b-1)//b
Вместо floor(a/b) или, когда делится без остатка используйте a//b

В логике решения ошибки я не вижу.

Это классическая задача о рюкзаке.

Можно составить такое ДП: F(c, k) - максимальное количество страниц, которые можно набрать из первых k книг общей стоимостью ровно c.

База: F(0,0) = 0, F(0,*) = F(*,0) = -infinity.
Пересчет:

F(c, k) = max(F(c-cost[k], k-1) + pages[k], F(c,k-1))

Это ДП приведено в википедии, например. Ответ - максимум по всем c F(c,k).

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

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