1

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

http://www.belsut.gomel.by/Ellibrary/2/119.pdf

2

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

Так а можно точные размеры кол-ва рёбер и вершин? Не понимаю как можно решать задачу, вам нужно оптимальнео решение? о_о Или которое только даёт Accepted!!! ~_~

3

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

Ааа smile Я просто прочитал типо что бы было N^3, а надо быстрее ^_^

4

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

Наверно я не понял условие как всегда, но что мешает брать вершину, запускать поиск в глубину, суммировать все вершины достижимые из неё?
Сложность получается O(V*E) ~= O(V^3).

5

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

Отсортировать все точки многоугольника по углу, далее дихотомией по углу..

6

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

Спасибо wink

7

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

Ясно, спасибо!
Да, дерево понятно, оно именно дерево smile
Просто я увидел что задачи которые решает автомат схожи с задачами которые решает дерево, но не заметил такой сложности, тем более в конце строки не увидел символа "$" :-D Да и рёбра не сжимаются wink Нужно разобраться, интересно стало.
А не подскажешь где можно хорошо прочитать про суффиксное дерево, нам на сборах рассказывали бегло, так показалось так легко sad Но не успел я там понять, и вообщем теперь нужно будет читать самому.
Если подкинешь статейку с кодами если ещё и будет, то буду благодарен! wink

8

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

Такой вопрос, эта структура очень уж похожа на суффиксное дерево, даже я бы сказал это оно и есть для суффиксов. И я так понимаю это не алгоритм Укконена? Объясните пожалуйста, не понимаю.

9

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

Oleg пишет:

Спасибо, Егор, за интересные задачи. smile

все-таки  интересно - Максиму повезло (слабость тестов) что его a^(b%phi(с))%c  для a и c не взаимно простых прокатило или все-таки можно и для них ?

На самом деле это естественно не верно для не взаимно простых, но если сделать степень минимальной больше где-то log2(n),то это работает! smile Обоснование читать в разборе ^_^ Не знаю, вроде тесты делались для похожих решений smile

10

(7 ответов, оставленных в News)

Я просто не втыкаю в это=) Но может просто сайт слишком популярен ^_^ Особенно во время соревнований smile

11

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

alexander пишет:

А в http://e-maxx.ru/algo/lca_linear   -   vector<int> g[MAXN];   -    это что? - массив из MAXN векторов типа инт?
т.е. тоже самое, что  vector < vector<int> > graph, но с меньшей функциональностью?

Это массив векторов ^^
То есть мы с самого начала задаём сколько у нас будет строк, а в каждой строке уже хранится динамический свой вектор smile Я в си++ не разбераюся, но надеюсь ответил верно >__<

Можно проще ...
Будем использовать только дихотомию, и для удобства вектора из с++ smile
Теперь рассмотрим на примере
{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.
big_smile

Так погодите, задача такая?
Есть некторый массив чисел, в данном случае это перестановка.
Например {1, 7, 4, 6, 9, 3, 2, 8, 5, 10} и требуется покрыть этот массив минимальным кол-вом возрастающих подпоследовательностей?
В данном случае это 4 возрастающих подпоследовательности, например такие: {1, 7, 9, 10}, {4, 6, 8}, {3, 5}, {2}.
Если я понял условие правильно, то эту задачу можно решить за NlogN. (Если надо, могу рассказать)

14

(7 ответов, оставленных в Feedback)

А вот и спам пришёл!! =0 ааааа yikes wink

15

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

1e+100 = 10^100

16

(12 ответов, оставленных в Feedback)

Оооо smile Их тысячи ^_^

17

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

tongue Куча рулез ^^

18

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

KADR пишет:
brainail пишет:

Ну тогда если так, то не БФС, а Дейкстра с кучей smile

Почему именно с кучей? Она ведь не всегда работает быстрее smile Если ребер много, то проще уже писать Флойда - будет работать быстрее чем N Дейкстр с кучей и писать намного быстрее.

Конечно согласен! Просто условия не вижу вот и говорю что по ассимптотике лучше smile Но не всегда! tongue
Интересно, а вот фибоначива куча, она ведь за O(1) большинство операций делает, и ведь тогда дейкстра будет работать за O(V + E) :-D Я никогда её не писал, но если кто писал, как она себя ведёт при работе на больших тестах? smile

19

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

Ну тогда если так, то не БФС, а Дейкстра с кучей smile

20

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

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

21

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

chum пишет:

а какая разница взвешенный или нет?
ну самое тупое -- V BFS'ов

Есть разница ... Если у нас граф с рёбрами стоимостью 1, то тут да очередь обычная, а если взвешенный то тут не выгодно писать очередь, она может много раз ложить одну вершину .. Придётся писать V дейкстр с кучей ^^

22

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

Так как нету циклов, то граф ациклический.
1. Делаем топологическую сортировку
2. Пускаем ДП по этому графу, так как рёбра направленны в одну сторону, то ДП будет работать правильно :
  F( U ) = MAX( F( V ) + C( U, V ) ), U -> V - некоторое ребро заканчивающееся в U.

23

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

Но ассимптотика будет хуже!) Всё закрыли тему):D

24

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

Ну сжатие путей это понятно! Но и правильно присоединять множество тоже нужно.

25

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

Дело в том, что вся эвристика заключается в том, что бы меньшее множество присоединять к большему, так как если к большему прибавлять меньшее то размер множества не увеличится больше чем в два раза, но если присоединить наооброт, то меньшее множество возрастёт во много раз, и теперь проход по нему составит большее кол-во операций. И того получаем эвристику присоединять меньшее множество к большему! Тогда сложность не превзойдёт NlogN.
Так же если не учитывать размеры,а просто присоединять рандомно "random(2)=1 .." то тоже будет достигаться такая же сложность, за счёт балансирования множества рандомом (это общеожидаемый факт). А вот твой первый метод просто берёт всегда первое и конектит ко второму, из-за чего сложность резко возрастает, и приближается к N^2.
Поэтому всегда советуют писать либо рандомную балансировку, или эвристику по рангам (по размерам множества).