Wataru

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

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

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

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

Edit: тут было неправильное решение через недо-skip-list.

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

Заведите отрезок на n+m элементов. Кадому символу в алфавите будет соответствовать еденица где-то в этом отрезке. Изначально они занимают n самых правых позиций. Их порядок - это будет та самая перестановка из условия. Дервево отрезков будет считать сумму. В таком дереве можно за логарифм найти k-ую еденицу (рекурсивный спуск) и узнать какой по порядку является данная еденица (запрос на сумму на отрезке 0..i-1). Еще для каждого символа алфавита храните, где именно на отрезке лежит соответствующая ему еденица, а для каждого элемента на отрезке, какому символу он соответствует.

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

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

Похоже, на строке "abcdef" у вас выдаст d=0, а может и вообще d не напишет.

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

Еще, я бы вместо последовательного обновления коэффициента в previous считал его явно. i-ый символ встречается ровно в (i+1)*(n-i) подстроках.

Не понимаю, в чем проблема вообще. Забудьте, что это строки или числа. Все что нужно для бинпоиска - это уметь спрашивать < или = искомая штука и штука в массиве по заданной позиции.

В питоне есть массивы (доступ по индексу) и строки он сравнивает автоматом через операторы == и <.

Т.е. можно написать тот же абсолютно код, что и для бинпоиска по числам и он будет работать на строках. Правда, надо помнить, что сложность у бинпоиска по строкам будет не O(log n), а O(L log n), где L - максимальная длина строк.

Попробуйте читать через scanf.

Я вижу, вы делаете через sync_with_stdio(0), но я не уверен, что это 100% помогает.

Потом, вместо set vis достаточно передавать в dfs предыдущую вершину и не ходить в нее.

А еше у вас ошибка, при делении ребра пополам нельзя делить пополам cnt*w. Если cnt четное, а w нечетное, вы потереяете округление. Надо пихать в кучу пару cnt, w, и брать максимальное cnt*ceil(w/2). И еще, вы пихаете в кучу цену ребра, помноженную на количество листьев по этому ребру и всем предыдущем в текущей вершине! Надо там не cur брать, а значение dfs.

И еще, оно скорее всего виснет из-за переполнения. При умножении cur*c.second может получиться отрицательное число, вы же int-ы перемножаете, и только потом к long long приводите.

Во-первых, перенесите центр системы координат в центр элипса - вычтите его из всех координат точек касания. В самом конце надо будет сделать обратный переход и подставить x=x-x0, y=y-y0 в уравнение.

При выборе правильной системы координат, эллипс становится окружностью, ведь его уравнение x^2/a^2+y^2/b^2=1. Все остальное - это от переноса центра координат и поворота эллипса.

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

с- cos(угол), s=sin(угол) k- коэффициент сжатия.

Тогда новая система координат - {kc,ks}, {s,-c}. Преобразуем в эту систему координат тички касания и вектора касательных. Они так и останутся касающимися нашего эллипса, ведь преобразования поворота и сжатия оставит прямые прямыми, а эллипс - эллипсом (или кругом).

Если x1,y1 - точка касания, а {xv, yv} - вектор касательной, то:

x1' = x1*kc+y1*ks

y1' = x1*s-y1*c

xv' = xv*kc+yv*ks

yv' = xv*s-yv*c

Это просто формулы перобразования между системами координат. Аналогично можно сделать для x2', y2', xw,' yw'.

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

Если аккуратно расписать x1'*x1'+y1'*y1'-x2'*x2'-y2'*y2' = 0, и заменить c^2=1-s^2, то будет:

(y1*y1-y2*y2-x1*x1+x2*x2)*kkss + (2*x1*y1-2*x2*y2)kkcs + (x1*x1-x2*x2-y1*y1+y2*y2)ss +(2*x2*y2-2*x1*y1)*cs +(x1*x1-x2*x2)*kk+(y1*y1-y2*y2)=0

Советую не верить мне тут с коэффициентами, а пепроверить их самостоятельно.

Аналогичные уравнения для касательных x1'*xv'+y1'*yv' = 0:
(y1*yv-x1*xv)*kkss + (x1*yv+y1*xv)kkcs + (x1*xv-y1*yv)ss +(-x1*yv-y1*xv)*cs +(x1*xv)*kk-y1*yv=0

Важно заметить, что у нас тут 3 уравнения вида:

A*kkss+B*kkcs-Ass-Bcs+Ckk+D=0, где константые коэффициенты A,B,C,D (разные в трех уравнениях) и 3 переменные k,s,c. Еще есть дополнительное условие s*s+c*c=1, это же синусы/косинусы угла, и k!=0. k может быть и отрицательным, это означало бы отражение и сжатие системы координат. Под наши цели подходит.

Обратите внимание, 3-е и 4-ое слагаемые идут с теми же коээфициентами, что и 1-е и 2-е, но с обратными знаками. Можно подобрать такие коээфициенты для первых двух уравнений, что если их прибавить к тертьему уравнению, то коэффициенты перед kkss,kkcs,ss,cs - все станут равны нулю. Это надо решить систему из двух линейных уравнений.
Пусть коээфициенты в уравнениях A1,A2,A3,B1,B2,B3,C1 и т.д. (напоминаю, это константы, вычеслимые через заданные координаты точек и векторов касания). Введем 2 переменные x, y - коээфециенты, с какими прибавлять первые 2 уравнения к тертьему. Условия: A1*x+A2*y+A3=0, B1*x+B2*y+B3=0. Решив эту систему уравнений, найдя коээфициенты и прибавив первые 2 уравнения к тертьему, вы получите уравнение вида

C4*k*k+D4=0

Элементарно решив его, вы найдете k. Подставив его в 2 предыдущих уравнения вы получите 2 уравнения вида:

A4*ss+B4*cs + D4 = 0

Это тригонометрическое уравнение можно решить, дописав множитель cc+ss к D4, получив уравнение вида:

(A4+D4)*ss+B5*cs+D4*cc = 0.

Теперь осталось поделить обе части на с^2 и решить квадратное уровнение для tan(). Еще, правда, надо рассмотреть подходит ли c=0,s=1 (s=-1 рассматривать не надо, Ведь без разницы, в какую сторону вращать на 90 градусов - все равно ось сжатия будет одна и та же).

Теперь зная тангенс найдите косинус и синус (школьные тригонометрические формулы, вроде c=sqrt(1/(1+t^2)).

Все, мы знаем k,c,s. Подставив их в формулы для x1',y1' мы узнаем радиус окрудности (расстояние до нуля). Пусть радиус будет r.

Теперь уравнение эллипса x'^2+y'^2 = r^2.

Подставляем преобразование:

x'=x*k*s+y*k*c, y' = x*s-y*c. Потом не забываем сделать замену x<-x-x0, y<-y-y0, чтобы верунть центр эллипса в заданное место.

Все эти замены надо аккуратно подставить и раскрыть скобки в уравнении x'^2+y'^2 = r^2 и получить ваши коээфициенты в уравнении Ax2+ Bxy + Cy2 + Dx + Ey = F. Потом поделите обе части на F.

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

Edit:

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

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

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

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

Вы говорите, что пытаетесь брать числа, чтобы "портить" меньшие биты, но ведь это может быть не так.
Если у вас числа 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! элементов, потому что хранится список ответ и список для меньших перестановок, плюс стек и промежуточные массивы при конкатенации.

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