2 2010-07-07 20:00:24
Re: Сумма по всем достижимым вершинам (9 ответов, оставленных в Algo)
Так а можно точные размеры кол-ва рёбер и вершин? Не понимаю как можно решать задачу, вам нужно оптимальнео решение? о_о Или которое только даёт Accepted!!! ~_~
3 2010-07-07 19:53:31
Re: Сумма по всем достижимым вершинам (9 ответов, оставленных в Algo)
Ааа Я просто прочитал типо что бы было N^3, а надо быстрее ^_^
4 2010-07-07 11:19:53
Re: Сумма по всем достижимым вершинам (9 ответов, оставленных в Algo)
Наверно я не понял условие как всегда, но что мешает брать вершину, запускать поиск в глубину, суммировать все вершины достижимые из неё?
Сложность получается O(V*E) ~= O(V^3).
5 2010-06-28 20:04:49
Re: triangles (4 ответов, оставленных в Problems)
Отсортировать все точки многоугольника по углу, далее дихотомией по углу..
7 2010-06-19 22:16:13
Re: Суффиксный автомат (5 ответов, оставленных в Algo)
Ясно, спасибо!
Да, дерево понятно, оно именно дерево
Просто я увидел что задачи которые решает автомат схожи с задачами которые решает дерево, но не заметил такой сложности, тем более в конце строки не увидел символа "$" :-D Да и рёбра не сжимаются Нужно разобраться, интересно стало.
А не подскажешь где можно хорошо прочитать про суффиксное дерево, нам на сборах рассказывали бегло, так показалось так легко Но не успел я там понять, и вообщем теперь нужно будет читать самому.
Если подкинешь статейку с кодами если ещё и будет, то буду благодарен!
8 2010-06-19 17:20:04
Тема: Суффиксный автомат (5 ответов, оставленных в Algo)
Такой вопрос, эта структура очень уж похожа на суффиксное дерево, даже я бы сказал это оно и есть для суффиксов. И я так понимаю это не алгоритм Укконена? Объясните пожалуйста, не понимаю.
9 2010-06-12 06:32:07
Re: Codefoces 17 (2 ответов, оставленных в Algo)
Спасибо, Егор, за интересные задачи.
все-таки интересно - Максиму повезло (слабость тестов) что его a^(b%phi(с))%c для a и c не взаимно простых прокатило или все-таки можно и для них ?
На самом деле это естественно не верно для не взаимно простых, но если сделать степень минимальной больше где-то log2(n),то это работает! Обоснование читать в разборе ^_^ Не знаю, вроде тесты делались для похожих решений
10 2010-06-05 09:51:23
Re: Оптимизация сайта (7 ответов, оставленных в News)
Я просто не втыкаю в это=) Но может просто сайт слишком популярен ^_^ Особенно во время соревнований
11 2010-05-08 00:00:19
Re: Наименьший общий предок (как задать граф?) (11 ответов, оставленных в Algo)
А в http://e-maxx.ru/algo/lca_linear - vector<int> g[MAXN]; - это что? - массив из MAXN векторов типа инт?
т.е. тоже самое, что vector < vector<int> > graph, но с меньшей функциональностью?
Это массив векторов ^^
То есть мы с самого начала задаём сколько у нас будет строк, а в каждой строке уже хранится динамический свой вектор Я в си++ не разбераюся, но надеюсь ответил верно >__<
12 2010-05-02 13:46:09
Re: Разбиение перестановки на подпоследовательности (7 ответов, оставленных в Problems)
Можно проще ...
Будем использовать только дихотомию, и для удобства вектора из с++
Теперь рассмотрим на примере
{1, 7, 4, 6, 9, 3, 2, 8, 5, 10}
Пусть нам поступила 1.
Запишем её {1}.
Далее поступает 7, запишем её после 1. Получим {1, 7}
Далее идёт 4, запишем её в новую строку, получим
{1, 7}
{4}
далее 6, запишем после 4, получим.
{1, 7}
{4, 6}
далее 9, запишем после 7, получим
{1, 7, 9}
{4, 6}
И так далее, на каждом ходу ищем из существующих строк, как можно высшию, что бы последнее число не превышало добавляемого числа, если таких строк нет, то добавляем в новую строку. ...
далее буду получатся вот такие ходы:
{1, 7, 9}
{4, 6}
{3}
....
{1, 7, 9}
{4, 6}
{3}
{2}
....
{1, 7, 9}
{4, 6, 8}
{3}
{2}
.....
{1, 7, 9}
{4, 6, 8}
{3, 5}
{2}
....
{1, 7, 9, 10}
{4, 6, 8}
{3, 5}
{2}
В итоге получаем 4 покрывающих последовательности!
Ищем мы строку обычной дихотомией! Теперь почему этот жадный правилен.
Если нам надо поставить число X, и его на текущий момент допустим можно поставить в конец како-то последовательности,или начать с него новую последовательность.
Тогда, нам всегда выгодно поставить в конец, чем создавать новое ... Так же в случае когда нужно выбирать между строками, то нужно выбирать с максимально близким меньшим к нему числом! Это всё несложно увидеть посмотрев на различные последовательности...
И того можно написать так, прямо при чтении для каждого числа ищем дихотомией его местоположение, и пихаем его в конец найденной строки.
NlogN.
13 2010-05-01 12:36:46
Re: Разбиение перестановки на подпоследовательности (7 ответов, оставленных в Problems)
Так погодите, задача такая?
Есть некторый массив чисел, в данном случае это перестановка.
Например {1, 7, 4, 6, 9, 3, 2, 8, 5, 10} и требуется покрыть этот массив минимальным кол-вом возрастающих подпоследовательностей?
В данном случае это 4 возрастающих подпоследовательности, например такие: {1, 7, 9, 10}, {4, 6, 8}, {3, 5}, {2}.
Если я понял условие правильно, то эту задачу можно решить за NlogN. (Если надо, могу рассказать)
14 2010-05-01 09:05:45
Re: IMHO о сайте (7 ответов, оставленных в Feedback)
А вот и спам пришёл!! =0 ааааа
16 2010-04-18 12:41:17
Re: Регулярные контесты. (12 ответов, оставленных в Feedback)
Оооо Их тысячи ^_^
18 2010-04-17 12:12:27
Re: Диаметр графа (13 ответов, оставленных в Algo)
brainail пишет:Ну тогда если так, то не БФС, а Дейкстра с кучей
Почему именно с кучей? Она ведь не всегда работает быстрее Если ребер много, то проще уже писать Флойда - будет работать быстрее чем N Дейкстр с кучей и писать намного быстрее.
Конечно согласен! Просто условия не вижу вот и говорю что по ассимптотике лучше Но не всегда!
Интересно, а вот фибоначива куча, она ведь за O(1) большинство операций делает, и ведь тогда дейкстра будет работать за O(V + E) :-D Я никогда её не писал, но если кто писал, как она себя ведёт при работе на больших тестах?
19 2010-04-16 13:19:29
Re: Диаметр графа (13 ответов, оставленных в Algo)
Ну тогда если так, то не БФС, а Дейкстра с кучей
20 2010-04-15 13:26:23
Re: Диаметр графа (13 ответов, оставленных в Algo)
Аааа, тогда да.
Я же подумал что человек хочет узнать диаметр, если рёбра взвешены, и уже считается не по кол-ву рёбер, а по длине пути! извиняюсь.
21 2010-04-14 18:44:50
Re: Диаметр графа (13 ответов, оставленных в Algo)
а какая разница взвешенный или нет?
ну самое тупое -- V BFS'ов
Есть разница ... Если у нас граф с рёбрами стоимостью 1, то тут да очередь обычная, а если взвешенный то тут не выгодно писать очередь, она может много раз ложить одну вершину .. Придётся писать V дейкстр с кучей ^^
22 2010-04-14 12:59:25
Re: Longest Path (5 ответов, оставленных в Problems)
Так как нету циклов, то граф ациклический.
1. Делаем топологическую сортировку
2. Пускаем ДП по этому графу, так как рёбра направленны в одну сторону, то ДП будет работать правильно :
F( U ) = MAX( F( V ) + C( U, V ) ), U -> V - некоторое ребро заканчивающееся в U.
23 2010-04-06 19:00:43
Re: Union в DSU... (12 ответов, оставленных в Problems)
Но ассимптотика будет хуже!) Всё закрыли тему):D
24 2010-04-06 01:01:12
Re: Union в DSU... (12 ответов, оставленных в Problems)
Ну сжатие путей это понятно! Но и правильно присоединять множество тоже нужно.
25 2010-04-05 17:20:42
Re: Union в DSU... (12 ответов, оставленных в Problems)
Дело в том, что вся эвристика заключается в том, что бы меньшее множество присоединять к большему, так как если к большему прибавлять меньшее то размер множества не увеличится больше чем в два раза, но если присоединить наооброт, то меньшее множество возрастёт во много раз, и теперь проход по нему составит большее кол-во операций. И того получаем эвристику присоединять меньшее множество к большему! Тогда сложность не превзойдёт NlogN.
Так же если не учитывать размеры,а просто присоединять рандомно "random(2)=1 .." то тоже будет достигаться такая же сложность, за счёт балансирования множества рандомом (это общеожидаемый факт). А вот твой первый метод просто берёт всегда первое и конектит ко второму, из-за чего сложность резко возрастает, и приближается к N^2.
Поэтому всегда советуют писать либо рандомную балансировку, или эвристику по рангам (по размерам множества).