76 Ответ от brainail

(30 ответов, оставленных в Problems)

KADR пишет:
chum пишет:

сколько раз берем рандомную вершину?)

Один. Если веса ребер положительные, то помоему, это даже правильно. Объяснить можно так: каждое ребро веса А представим в виде цепочки из А ребер веса 1. Тогда получим дерево, где все ребра веса 1, а на нем этот алгоритм правильный.

Edit: Beaten smile

ТЫ процетировал меня ! Я был раньше тебя smile

Перейти к разделу: Problems

77 Ответ от brainail

(30 ответов, оставленных в Problems)

Я только развеял свои сомнения smile Вообщем так,Roman Rubanenko -> тебе привели массу решений,выбирай,если что не понятно спрашивай.
2rf - ты прав,этот алгоритм тоже будет работать и на взвешенном графе,извините что сдуру ляпнул. Действительно взвешенное дерево это тоже не взвешенное просто каждое ребро с весом E,размножается на E подряд идущих рёбер,тем самым мы получим не взвешенное дерево,на котором будет работать данный алгоритм,значит он будет работать и на взвешенном дереве smile
Всё закрыли топик smile

Перейти к разделу: Problems

78 Ответ от brainail

(30 ответов, оставленных в Problems)

Слушайте вы что сума сходите программисты, уже привели три решения, два из них очень простые, а одно из них оптимальное по скорости. Закрывайте топик! Хватит писать тут. А сам автор вопроса походу забил big_smile

Перейти к разделу: Problems

79 Ответ от brainail

(30 ответов, оставленных в Problems)

Roman Rubanenko пишет:

1.Дфс только с одной вершины ничего не даст.
2.При N=1000 юзать дфс с каждой вершины ещё хуже чем Дейкстру.

А теперь посмотрим по чему Дейкстра в твоём решении хуже других алгоритмов!
1. Дейкстра обычно используется для разнообразных графов,а не отдельных видов,как в данном случае Дерево.
2. Так как у нас дерево то у нас все пути между двумя парами вершин однозначны,то есть не существует только один путь между всеми парами вершин,это кстати можно сказать и есть определение дерева.
3.Из пункта два следует,что нам не нужно между парами вершин выбирать какой-то наилучший путь,значит мы просто должны пройти по всем рёбрам лежащими между двумя парами вершин,это и будет длина пути между этими вершинами.
4.Твоя Дейкстра пускается с каждой вершины O(N),и работает она за O(N^2),и того общая сложность O(N^3).При N = 1000 это не успеет ~10^9.
5.Из пункта 2,3 следует что можно заменить Дейкстру любым алгоритмом поиска пути между двумя парами вершин,мы возьмём Очередь(BFS) или Поиск_в_Глубину(DFS). Оценим сложность: пробегаем по всем вершинам O(N),пускаем с каждой вершины (BFS or DFS) - O(N) (так как по каждому ребру мы пройдём один раз,больше нам не надо). И того O(N^2). При N = 1000 это спокойно успевает ~10^6.
6.В итоге получаем то же самое что и у тебя,только Дейкстру работающую за O(N^2) заменили на (BFS or DFS) работающих за O(N).
7.Пиши Дейкстру только на общих графах,которые не обладаю никакими свойствами.
8.Если ты понял что я написал выше,то можешь понять что написал "KADR" -> он привёл решение за O(N),которое оптимальное по времени,но немного сложнее для понимания.

Перейти к разделу: Problems

80 Ответ от brainail

(30 ответов, оставленных в Problems)

KADR пишет:

Можно довольно простой динамикой по дереву сделать за О(Н).
Выделим какую-то вершину как корень и топологически отсортируем дерево. Теперь пусть f(v) это максимальный путь в поддереве с корнем в вершине v, такой что оба его конца лежат в этом поддереве, а g(v) это максимальный путь в поддереве с корнем в v, такой что один его конец это лист этого поддерева, а второй - вершина v.
Тогда f(v)=max(f(v')) для всех потомков. Но считая его так мы не учтем, что может быть путь как бы "соединяется" в вершине v, поэтому в этот max следует еще включить 2 потомка v1 и v2, для которых g(v1)+edge(v,v1)+g(v2)+edge(v,v2) - максимально. Это легко сделать за О(количество потомков).
g(v)=max(g(v')+edge(v,v')) для всех потомков.
Тогда f(корень) и будет ответом.

Я не спорю с тобой smile
Но ведь они не понимает ДВС или БФС со всех вершин,то и динамику не поймут я думаю.

Перейти к разделу: Problems

81 Ответ от brainail

(30 ответов, оставленных в Problems)

Zayakin_Andrey пишет:

Уже была задача, сначала делаем обход из любой вершины, ищем самою дальнюю вершbну от начальной, из неё снова обход, который определит две самые удаленные вершины. сложность O(N)

Данное решение не будет работать на взвешенном дереве!
Оно будет работать если все рёбра по 1!
А что бы написать правильно то нужно писать как я сказал,
можно написать ещё быстрее чем я сказал,но думаю не нужно углубляться,
если и это вам не понятно,что достаточно при таком N,пустить с каждой вершины очередь или рекурсию и всё.

Перейти к разделу: Problems

82 Ответ от brainail

(30 ответов, оставленных в Problems)

При чём тут эта задача тут?

Перейти к разделу: Problems

83 Ответ от brainail

(30 ответов, оставленных в Problems)

Ну если вам не понятно тогда вот так:
Создадим матрицу Dij = расстояние между i-ой вершиной и j-ой.
Как её просчитать,для этого перебираем вершину i,теперь запускам очередь,или рекурсию что бы просчитать расстояния до всех остальных вершин с i-ой. Занесём все показатели в матрицу D.
Теперь когда у нас есть расстояния между всеми парами вершин,мы просто выбираем максимальное из всех таких расстояний,запоминая сами вершины.
Надеюсь так понятней.

Перейти к разделу: Problems

84 Ответ от brainail

(30 ответов, оставленных в Problems)

Как я понял из вашего решения N = 1000 максимум.
Дальше вы написали Дейкстру за O(N^2). Максимальная сложность работы может составить O(N^3)! Что не уложится естественно по времени в 2 секунды.
Вам нужно либо написать Дейкстру с кучей за O(NlogN),тогда сложность программы составит O(N^2*logN),что улаживается  по врмени.
Но в данном случае у вас дано ДЕРЕВО,а это значит все пути в нём из одной вершины в другую однозначны,следовательно вам достаточно перебирать вершину с которой будут искаться расстояния,а потмо пускать либо Рекурсию,либо Очередь (DFS || BFS),так как пути однозначны,то в каждой вершине мы побываем 1 раз,и сложность программы составит O(N^2).

Перейти к разделу: Problems

85 Ответ от brainail

(4 ответов, оставленных в Problems)

Зачем себе голову забивать,пиши дихотомия+сумматор самое распространённое.

Перейти к разделу: Problems

86 Ответ от brainail

(4 ответов, оставленных в Problems)

Я так понял тебе нужно искать на каждом отрезке 1..k, 2..k+1, 3..k+2 => средний элемент или медиану (если отсортировать отрезок и взять в нём элемент стоящий по середине, то это и будет медианой).
Если это так, то можно написать такое решение:
Сожмём числа если они большие (и того получим числа от 1..n), теперь создадим как ты и сказал дерево Фенвика(или сумматор по другому), занесём первые k-1 элементов в сумматор,то есть на их позиции по прибавляем +1 (если одинаковые элементы имеются то на них будет стоять больше 1). Теперь что,начинаем бежать с i = с k .. n элемент, добавляем на позицию i - го числа в сумматоре(дерево Фенвика) +1,теперь что все наши числа в отрезке длиной k в сумматоре,начнём перебирать дихотомией какой элемент будет ответом на данном отрезке,и смотрим если сумма от 1..Middle(текущая позиция дихотомии) >= k / 2, то меняем правый край дихотомии,иначе левый.
И того Middle и будет нашим ответом,так как сумма до него равна k/2. И следовательно в данном отрезке он будет медианой.

Memory: O(N)
Time: O(N*log(N)*log(N)).

Перейти к разделу: Problems

87 Ответ от brainail

(23 ответов, оставленных в Problems)

wink

Перейти к разделу: Problems

88 Ответ от brainail

(23 ответов, оставленных в Problems)

Ярослав smile Так а можно решить задачу про поиск диаметра графа быстрее чем в лобовую?*:D

Перейти к разделу: Problems

89 Ответ от brainail

(23 ответов, оставленных в Problems)

Ээээ, ну так ограничения нужны точные, а так можешь просто написать
Пускаем с каждой вершины поиск в ширину за O(V+E) V - кол-во вершин,E - кол-во рёбер.
И вычисляем ответ,сложно O(V) * O(V+E) = O(V^2 + VE)

Перейти к разделу: Problems

90 Ответ от brainail

(23 ответов, оставленных в Problems)

Для начала, не очень точно дано определение диаметра графа
Диаметр графа — это максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число ребер, которые необходимо пройти, чтобы добраться из одной вершины в другую.
Может это у вас диаметр,и можно ссылку на задачу откуда она взята?
Так же,вроде не существует пока что алгоритмов кроме самых быстрых лобовых(перебирая и с каждой вершины пуская алгоритм находа минимальных путей ),для двудольных думаю можно что нибудь откопать.

Перейти к разделу: Problems

91 Ответ от brainail

(23 ответов, оставленных в Problems)

Так он именно двудольный? То есть есть две доли, и рёбра только между ними?

Перейти к разделу: Problems

92 Ответ от brainail

(5 ответов, оставленных в Problems)

Я же говорил что вот в ней smileroll

Перейти к разделу: Problems

93 Ответ от brainail

(5 ответов, оставленных в Problems)

Читай предыдущую тему, там у участника похожие функции, и ошибка была в погрешности.
Вроде вот в этом месте.

if (norm.scal(p1)  < 0 ) norm.x*=-1,norm.y*=-1;

Или чуть выше.

Перейти к разделу: Problems

94 Ответ от brainail

(15 ответов, оставленных в Algo)

Вот полная реализация дерева отрезков smile Поиск суммы, минимум, кол-во минимум, модификация.

{r-,s-,q-,i-,o+}
{$r+,s+,q+,i+,o-}
uses math;
const Size=200000;
type dataTree=record l,r,a,min,s,c:longint; end;
var t:array[0..Size*3]of dataTree;
 nz,n,_,minV,value,doit,l,r:longint;

procedure gen_tree(u,l,r:longint);
 begin
  t[u].l:=l; t[u].r:=r; t[u].min:=0;
  t[u].a:=0; t[u].s:=0; t[u].c:=r-l+1;
  if(l<r)then begin
   gen_tree(u+u,l,(l+r) shr 1);
   gen_tree(u+u+1,((l+r) shr 1)+1,r);
  end;
 end;

procedure modify(u,l,r:longint);
 var x,y:longint;
 begin
  if(t[u].l=l)and(t[u].r=r)then inc(t[u].a,value) else begin
   if(l<=t[u+u].r)then modify(u+u,l,min(t[u+u].r,r));
   if(r>=t[u+u+1].l)then modify(u+u+1,max(l,t[u+u+1].l),r);
   t[u].min:=min(t[u+u].min+t[u+u].a,t[u+u+1].min+t[u+u+1].a);
   t[u].c:=0; x:=t[u+u].r-t[u+u].l+1; y:=t[u+u+1].r-t[u+u+1].l+1;
   if(t[u].min=t[u+u].min+t[u+u].a)then inc(t[u].c,t[u+u].c);
   if(t[u].min=t[u+u+1].min+t[u+u+1].a)then inc(t[u].c,t[u+u+1].c);
   t[u].s:=t[u+u].a*x+t[u+u].s+t[u+u+1].a*y+t[u+u+1].s;
  end;
 end;

function fMin(u,l,r,w:longint):longint;
 var res:longint;
 begin
  if(t[u].l=l)and(t[u].r=r)then begin
   fMin:=w+t[u].min; exit;
  end else begin
   res:=maxlongint;
   if(l<=t[u+u].r)then res:=min(res,fMin(u+u,l,min(t[u+u].r,r),w+t[u+u].a));
   if(r>=t[u+u+1].l)then res:=min(res,fMin(u+u+1,max(l,t[u+u+1].l),r,w+t[u+u+1].a));
   fMin:=res;
  end;
 end;

function fCout(u,l,r,w:longint):longint;
 var res:longint;
 begin
  if(t[u].l=l)and(t[u].r=r)then begin
   if(w+t[u].min=minV)then fCout:=t[u].c else fCout:=0;
   exit;
  end else begin
   res:=0;
   if(l<=t[u+u].r)then res:=res+fCout(u+u,l,min(t[u+u].r,r),w+t[u+u].a);
   if(r>=t[u+u+1].l)then res:=res+fCout(u+u+1,max(l,t[u+u+1].l),r,w+t[u+u+1].a);
   fCout:=res;
  end;
 end;

function fSum(u,l,r,w:longint):longint;
 var res:longint;
 begin
  if(t[u].l=l)and(t[u].r=r)then begin
   fSum:=(r-l+1)*w+t[u].s; exit;
  end else begin
   res:=0;
   if(l<=t[u+u].r)then res:=res+fSum(u+u,l,min(t[u+u].r,r),w+t[u+u].a);
   if(r>=t[u+u+1].l)then res:=res+fSum(u+u+1,max(l,t[u+u+1].l),r,w+t[u+u+1].a);
   fSum:=res;
  end;
 end;

begin
 assign(input,'input.txt');
 reset(input);
 assign(output,'output.txt');
 rewrite(output);
 read(nz,n);
 gen_tree(1,1,n);
 for _:=1 to nz do begin
  read(doit,l,r);
  if(doit=1)then begin // * Find Min (L .. R) * //
   writeln(fMin(1,l,r,t[1].a));
  end else
  if(doit=2)then begin // * Find Sum (L .. R) * //
   writeln(fSum(1,l,r,t[1].a))
  end else
  if(doit=3)then begin // * Find Kol-Min (L .. R) * //
   minV:=fMin(1,l,r,t[1].a);
   writeln(fCout(1,l,r,t[1].a));
  end else
  if(doit=4)then begin // * Add Value (L .. R)* //
   read(value);
   modify(1,l,r);
  end else assert(0<>0);
 end;
 close(input);
 close(output);
end.

Перейти к разделу: Algo

95 Ответ от brainail

(10 ответов, оставленных в OlympNews)

Надо пользоваться Moj.Moj, а то в том не работают нулевые вектора, из-за этого на входных тестах прога не скомпилицца, да и Moj.Moj удобнее, та ми тесты свои можно быстро вставлять.

Перейти к разделу: OlympNews

96 Ответ от brainail

(5 ответов, оставленных в Algo)

Но ведь в статье описан чей то известный алгоритм ?
Разве тот дядька который этот алгоритм придумал не написал доказательство для этой штуки ...?
или это e-maxx твой алгоритм ?:P

Перейти к разделу: Algo

97 Ответ от brainail

(10 ответов, оставленных в Offtopic)

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

Перейти к разделу: Offtopic

98 Ответ от brainail

(10 ответов, оставленных в Offtopic)

tongue e-maxx добрый big_smile

Перейти к разделу: Offtopic

99 Ответ от brainail

(6 ответов, оставленных в Algo)

Нет ну я знаю что и как работает многоразрядная ) но просто коряво написалось . Понятно.;)

Перейти к разделу: Algo

100 Ответ от brainail

(5 ответов, оставленных в Offtopic)

Может стандартные библиотеки столько весят?
в Delphi тоже, изза библиотек часто таски не сдаются,где МЛ в притык (

Перейти к разделу: Offtopic