Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Сообщения от KADR
ээм
но мы же изменяем в куче элементы
а изменение стоит O(logN)вообще дейкстру с фенвиком проще всего писать
На С++ есть priority_queue. Всегда писал с ней и нормально работало 
А Фенвика еще нужно руками писать. Хоть там кода мало, но все равно занимает время.
// k - 0-based index
inline char* erase(char *s,int k)
{
char *ans=new char[strlen(s)];
memcpy(ans,(string(s).substr(0,k)+string(s).substr(k+1,strlen(s)-k-1)).c_str(),strlen(s));
return ans;
}Правда тут надо еще
#include <string>Ну тогда если так, то не БФС, а Дейкстра с кучей
Почему именно с кучей? Она ведь не всегда работает быстрее Если ребер много, то проще уже писать Флойда - будет работать быстрее чем N Дейкстр с кучей и писать намного быстрее.
Есть замечательный алгоритм Флойда-Уоршалла. Работает за O(N^3), реализация занимает 3 строки.
Ну сжатие путей это понятно! Но и правильно присоединять множество тоже нужно.
Ну если присоединять неправильно, то сложность квадратичной все равно не станет.
Дело в том, что вся эвристика заключается в том, что бы меньшее множество присоединять к большему, так как если к большему прибавлять меньшее то размер множества не увеличится больше чем в два раза, но если присоединить наооброт, то меньшее множество возрастёт во много раз, и теперь проход по нему составит большее кол-во операций. И того получаем эвристику присоединять меньшее множество к большему! Тогда сложность не превзойдёт NlogN.
Так же если не учитывать размеры,а просто присоединять рандомно "random(2)=1 .." то тоже будет достигаться такая же сложность, за счёт балансирования множества рандомом (это общеожидаемый факт). А вот твой первый метод просто берёт всегда первое и конектит ко второму, из-за чего сложность резко возрастает, и приближается к N^2.
Поэтому всегда советуют писать либо рандомную балансировку, или эвристику по рангам (по размерам множества).
Имелось ввиду что findset будет использовать эвристику сжатия путей, по этому квадратичной сложность не станет. Другое дело, она может стать O(NlogN), но опять таки, это в теории.
Можно хранить очереди неявно.
У нас в одной очереди лежат последовательные элементы массива, значит можно просто в каком-то одном массиве хранить все элементы, а вместо очередей поддерживать указатели на начало и конец каждой "виртуальной очереди". Тогда константа будет намного меньше.
Ну тогда нужно еще найти факторизацию. А без разных быстрых методов она как раз работает за O(sqrtN).
Пусть, например у нас N=3, M=12
Стоимость 1-3 минут равна 2, стоимость 4 минуты равна 3, стоимость 5-INF минут равна 10.
Изначально f(0)=0, g(0)=0.
Считаем f(1):
f(1)=f(0)+g(1)=2
Для первой очереди делаем счетчик количества минут равным 1 и добавляем туда число 2-2*0=0.
Состояние очередей:
1) {2}, счетчик 1
2)-... {}, счетчики 0
Состояние первой очереди {2} означает что когда мы будем считать f(2) у нас f(1)+g(1) будет равно 2+счетчик*цену=2+1*2=4.
Считаем f(2):
f(2)=min(f(0)+g(2),f(1)+g(1))=4
Минимальный из предыдущих элементов это 4.
Для первой очереди увеличиваем счетчик на 1 и добавляем туда число 4-2*1=2.
Состояние очередей:
1) {2,2}, счетчик 2
2)-... {}, счетчики 0
Состояние первой очереди {2,2} и счетчик 2 означает что когда мы будем считать f(3) у нас f(1)+g(2) будет равно 2+счетчик*цену=2+2*2=6. Аналогично f(2)+g(1)=6.
Считаем f(3):
f(3)=min(f(0)+g(3),f(1)+g(2),f(2)+g(1))=6.
Минимальный из предыдущих элементов это 6.
Для первой очереди увеличиваем счетчик на 1 и добавляем туда число 6-2*2=2.
Состояние очередей:
1) {2,2,2}, счетчик 3
2)-... {}, счетчики 0
Состояние первой очереди {2,2,2} и счетчик 3 означает что когда мы будем считать f(4) у нас f(1)+g(3) будет равно 2+счетчик*цену=2+3*2=8. Аналогично f(2)+g(2)=f(3)+g(1)=8.
Считаем f(4):
f(4)=min(f(0)+g(4),f(1)+g(3),f(2)+g(2),f(3)+g(1))=8.
Минимальный из предыдущих элементов это 8.
Из первой очереди достаем элемент 2, находим его реальное значение, т.е. 2+3*2=8, переносим его во вторую очередь, прибавляем там счетчик 1 и добавляем туда число 8-3*0=8.
У первой очереди увеличиваем счетчик на 1 и добавляем туда 8-3*2=2.
Состояние очередей:
1) {2,2,2}, счетчик 4
2) {8}, счетчик 1
3)-... {}, счетчики 0
Считаем f(5):
f(5)=min(f(0)+g(5),...)=10.
Из первой очереди достаем элемент 2, находим его реальное значение, т.е. 2+4*2=10, переносим его во вторую очередь и добавляем туда число 10-3*1=7.
Одновременно с этим достаем элемент 8 из второй очереди, находим его реальное значение, т.е. 8+3*1=11, переносим его в третью очередь и добавляем туда число 11-10*0=11.
Увеличиваем счетчики очередей 1,2,3.
Состояние очередей:
1) {2,2,2}, счетчик 5
2) {7}, счетчик 2
3) {11}, счетчик 1
Считаем f(6):
f(6)=min(f(0)+g(6),...)=12.
...
Теперь состояние очередей:
1) {2,2,2}, счетчик 6
2) {6}, счетчик 3
3) {11,3}, счетчик 2
Это значит, что при подсчете f(7) у нас будет:
h(1)=f(1)+g(6)=11+2*10=31
h(2)=f(2)+g(5)=3+2*10=23
h(3)=f(3)+g(4)=6+3*3=15
h(4)=f(4)+g(3)=2+6*2=14
h(5)=f(5)+g(2)=2+6*2=14
h(6)=f(6)+g(1)=2+6*2=14
Дальше, очевидно, f(x) будет >12, поэтому ответ для данного теста будет равен 6.
На самом деле еще год назад я бы делал как ты говорил
Просто в универе в начале семестра читали векторы и я понял что с ними все намного проще, если расшарить.
Мне кажется, можно немного проще:
Пусть дан вектор AB и точка P. Тогда точка лежит на прямой, содержащей AB тогда и только тогда, когда [AB,AP]=0, т.е. скалярное произведение AB и AP равно нулю. Чтобы теперь определить, лежит ли эта точка на нужном луче, надо чтобы векторы AB и AP были направлены в одну сторону, т.е. скалярное произведение AB на AP должно быть больше или равно 0.
Итого получаем такие условия:
[AB,AP]=0 && (AB,AP)>=0
Ну можно попробовать хранить для каждой клеточки в столбце номер ее компоненты связности. Тогда нужно при переходе еще перебирать все возможные способы объединения компонент в одной компоненте. Главное отсекать разные недопустимые профили и компоненты нумеровать так, чтобы верхняя клетка принадлежала первой и номера шли подряд. Думаю, тогда решение успеет.
Ой, я имел ввиду что k увеличивается - дальше именно это и подразумевалось.
Для всех i<x у нас известно h(i)=f(i)+g(k).
f(i) не меняется, значит нужно обновлять g(k). Для этого заметим, что при сдвиге x на один вправо у нас ко всем h(i) прибавится стоимость k-й минуты разговора.
Отнесем каждое i к одной из N групп в зависимости от номера части к которой относится k-я минута. Очевидно, что группы будут состоять из последовательных i. При сдвиге x вправо из некоторых групп по одному элементу перейдут в следующую группу, а все остальные не изменят номера своих групп.
Если решать при помощи дерева, то нужно хранить указатели на начало и конец каждой из групп. Передвинуть указатели можно за O(N) операций. Теперь к каждому из отрезков (которому соответствует какая-то группа) прибавим стоимость минуты разговора, таким образом обновив h(i). В конце нам останется только найти минимум. Дерево Фенвика использовать нельзя, потому что чтобы в нем можно было искать минимум значения нужно только уменьшать, а мы их увеличиваем.
Сложность выйдет O(NMlogM) и я не уверен что оно уложится в 5 секунд с такими ограничениями.
Поэтому я предлагаю делать немного иначе: хранить каждую группу в своей очереди. Тогда передвижения элемента из группы в группу эквивалентно доставанию его из начала одной очереди и добавлению в конец следующей очереди. Как теперь искать минимум? Очень просто - можно для каждой очереди хранить глобальный счетчик - количество дополнительных минут, которые были прибавлены ко всей группе. В таком случае мы можем из каждой очереди за O(1) извлекать минимум и прибавлять к нему количество минут умноженное на стоимость одной такой минуты. А чтобы передвинуть элемент из группы в группу достаточно прибавить к нему накопившееся количество минут умноженное на стоимость предыдущей группы и отнять эту же величину для следующей группы.
Не уверен что это верно, но возможно пройдет:
Пусть f(x) это минимальное количество денег, требуемое чтобы поговорить x минут, а g(x) это количество денег, требуемое чтобы поговорить x минут за один разговор.
Тогда получаем формулу:
f(x)=min(f(x-k)+g(k)) по всем k<=x.g(x) легко предпосчитать в самом начале программы для всех x.
Пускай мы вычислили f(x) для какого-то x и для всех i<x мы знаем h(i)=f(x-k)+g(k), где x-k=i. Нам нужно придумать структуру данных, которая будет быстро находить этот минимум. Теперь, когда мы приступим к вычислению f(x+1) нам нужно как-то обновить нашу структуру. Заметим, что x-k не поменяется для фиксированного i, потому что x увеличился на 1, а требуемое k уменьшилось на 1. Значит, нам нужно поменять всего лишь g(k) для всех i<x т.к. k увеличится на 1, а так же добавить значение g(x-1)+g(1) для i=x.
Для всех i<x k увеличится ровно на 1. Разобьем все i на N групп, в каждой из которых стоимость одной минуты будет фиксированной. В таком случае, для всех i таких что соответствующие k и k+1 лежат в одной группе, нам надо всего-лишь увеличить h(i) на соответствующую цену минуты. Будет еще O(N) таких i для которых k и k+1 лежат в разных группах и надо "перевести" этот i из одной группы в другую и увеличить h(i) на стоимость одной минуты уже в новой группе.
Эту задачу уже можно решать либо деревом отрезков с поддержанием указателей на начало каждой группы и переходом от f(x) к f(x+1) за O(NlogM), либо заметить что если элемент A вошел в какую-то группу раньше элемента B, то и выйдет он из нее раньше. Значит, можно создать N очередей и поддерживать для каждой минимум, переходя от f(x) к f(x+1) за O(N).
Суммарная сложность выйдет либо O(NMlogM), если делать деревом отрезков, либо O(NM), если делать очередями.
А можно ссылку на задачу?
Вы хотели поделиться с нами задачей?
Только сложность описанной выше динамики выходит O(N^2*2^N), потому что состояний O(N*2^N) и из каждого состояния мы перебираем O(N) переходов.
Мне кажется, проще тогда уже так:
gcd(a,p)=1, где p=2^64.
Тогда
a^(phi(p)) = 1 (mod p)
phi(p)=2^64-2^63=2^63=b
a^b = 1 (mod p)
a^(b-1) = a^(-1) (mod p)
Ну раз так, тогда gcd(a,2^64)=gcd(a,2^64-a). Ну а 2^64-a=~0ull-a+1.
Даже если можно было представить, то все равно этот метод работал бы только для нечетных чисел. Я не знаю, действительно ли вам нужно деление, думаю там можно обойтись умножением и отниманием, но если оно все же необходимо, возьмите какой-нибудь простой модуль, правда тогда вместо естественного переполнения надо будет часто брать остаток по модулю и следить, чтобы небыло переполнения.
Может дадите ссылку на задачу?
А на вторую перебор+массив констант (либо даже без него) не пройдет? Можно делать либо совсем тупой перебор (просто перебирать все числа, начиная от 1 и находить количество делителей, не превышающих корень), а можно заметить что максимальное простое там будет небольшим, а так же тот факт, что если простое число присутствует в разложении, то все простые, меньшие его тоже присутствуют в нем.
Думаю, если делать перебор вторым способом, то даже массив констант не понадобится.
Выделим какую-то вершину root как корень. Посчитаем расстояние от корня до всех остальных вершин.
Тогда, если поступает запрос нахождения кратчайшего пути между A и B, то пусть C - их наименьший общий предок. Легко показать, что dist(A,B)=dist(root,A)+dist(root,B)-2*dist(root,C). На этом сайте описано, как быстро находить LCA. Если использовать эффективный алгоритм, то тут можно получить сложность даже O(N+M), где N - кол-во вершин, а M - кол-во запросов.
Edit: пока писал, уже ответили.
Тут можно использовать дерево отрезков. Для начала, построим дерево отрезков на массиве, которое для каждой вершины хранит минимальное число из отрезка, соответствующего ей.
Если мы хотим удалить число - просто поставим на его место +бесконечность.
Чтобы обработать запрос второго типа, нужно посмотреть, если у правого сына текущей вершины минимум не превышает заданного числа, значит рекурсивно переходим к нему, иначе переходим к левому сыну.
Все запросы работают за O(logN).
А чему равна медиана, когда количество чисел четное? Среднему арифметическому двух центральных?
MAXimal :: φορυμ » Сообщения от KADR