Задачи на СНМ(DSU)

12 лет назад, # |

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

→ Ответить

12 лет назад, # ^ |

Господа минусующие, объясните свою логику, будьте любезны :).

→ Ответить

kuzmichev_dima

12 лет назад, # ^ |

По крайней мере, эту задачу можно и без снм решить. Пример не совсем удачный

→ Ответить

задача на персистентный СНМ

12 лет назад, # ^ |

Возможно. Вообще-то да, задача больше интересна с точки зрения "увидеть СНМ и правильно его закодить".

→ Ответить

nurzhands

12 лет назад, # |

→ Ответить

CleRIC

12 лет назад, # ^ |

Сложилось такое впечатление, что задачи с персистентными структурами делает только Сергей Копелиович :) А не подскажете, может вы еще знаете какие-нибудь задачи на online-judge на персистентные структуры? Хотелось бы порешать такие задачи.

→ Ответить

HAPKOMAH

12 лет назад, # ^ |

-13

Ммм… На ПТЗ последних ещё была интересная задача на персистентный СНМ. Там добавляли/удаляли ребра из графа и нужно было отвечать на запросы о связности. В основном все делали sqrt декомпозицию, но ИТМО#1 сделали честное решение)

→ Ответить

Hohol

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

Там надо правильно применять. Каждое ребро появляется на каком-то отрезке. Деревом отрезков его можно разбить на лог кусков. И тогда обходя дерево отрезков ничего более страшного чем соеденить/разъеденить как было множества делать не надо.

→ Ответить

12 лет назад, # ^ |

Обращу внимание, что хотя в этот раз задача была не он Burunduk1 за год до этого она была от него.

→ Ответить

12 лет назад, # ^ |

От себя добавлю, что hos.lyric уже улучшил мою идею (Klog^2K) до KlogK. Там вообще нет СНМ :-)

А еще, если интересны подобные фичи, советую почитать похожую идею в статье Eppstein-а Dynamic MST, Offline Solution

→ Ответить

nk.karpov

12 лет назад, # ^ |

там было не персистентное снм, а просто стэк порядка логарифма снм-ов... это в разы проще

→ Ответить

12 лет назад, # ^ |

Чем в разы проще? И то и то адекватно делается только dfs'ом по версиям в оффлайне.

→ Ответить

nk.karpov

12 лет назад, # ^ |

эм... нет... я делал в этой задачке поддержку снм онлайн именно за счёт того, что их мало

→ Ответить

12 лет назад, # ^ |

Например:

Persistent-Stack — олимпиада ЛКШ :-)

Persistent-Queue — один из контестов Андрея Станкевича в Петрозаводске.

Persistent-Treap — на это были задачи в последнем Петрозаводске (контест не помню)

Persistent-Lists-With-Merge — мой последний контест в Харькове.

Правда вот на Online Judge почти все они отсутствуют. Но чтобы порешать, обычно достаточно достать тесты и протестить у себя локально :-) Если нужны тесты, пишите в личку.

→ Ответить

NuM

12 лет назад, # ^ |

http://www.codechef.com/problems/GENETICS Тут можно сдать персистентное декартово дерево

→ Ответить

imslavko

12 лет назад, # ^ |

Возможно нубский вопрос. А как писать персистентный СНМ?

→ Ответить

12 лет назад, # ^ |

Хранишь rank и parent в персистентных массивах (читай: в персистентных деревьях отрезков). Сжатие путей выполнять не стоит — асимптотику оно не улучшит. Реализовывать объединение через рандом — тоже, см. тест ниже.

→ Ответить

imslavko

12 лет назад, # ^ |

← Rev. 2 →

другой нубский вопрос: как сделать массив персистентным используя персистентное дерево отрезков? что хранить в промежуточных вершинах между корнем и листьями?

→ Ответить

http://acm.sgu.ru/problem.php?contest=0&problem=323

12 лет назад, # ^ |

Что хочешь: сумму/минимум/вообще ничего.

→ Ответить

CleRIC

12 лет назад, # ^ |

забавно)) я пишу персистентный массив так, что промежуточных вершин нет вообще :) можете показать как вы реализовываете персистентный массив?

→ Ответить

imslavko

12 лет назад, # ^ |

вы тоже объясните, как? Пожалуйста

→ Ответить

CleRIC

12 лет назад, # ^ |

+13

у i-ой вершины сыновьями являются вершины с номерами 2*i и 2*i+1.
массив — 1 2 3 4 5
у 1 сыновья 2,3
у 2 сыновья 4,5
у остальных вершин нет сыновей.
получается, что промежуточных вершин нет :)

→ Ответить

Zhukov_Dmitry

12 лет назад, # |

→ Ответить

abdukodir

12 лет назад, # |

задача.

→ Ответить

I_love_Tanya_Romanova

12 лет назад, # |

Пример задачи, у меня там ТЛ был с плохой реализацией СНМ. Миллион вершин, как не крути.

→ Ответить

12 лет назад, # ^ |

Спасибо, это видимо как раз, что нужно, мое правда там не тормозило, зашло за 1.8/5c

→ Ответить

I_love_Tanya_Romanova

12 лет назад, # ^ |

У меня там падали реализации без одной из двух стандартных эвристик (т.е. как решение без подвешивания менее высокой к более высокой, так и решение без сжатия путей). С ними меньше секунды.

→ Ответить

12 лет назад, # ^ |

Ну вообще без эвристик не интересно все же))

→ Ответить

goo.gl_SsAhv

12 лет назад, # |

СНМ — Система Непересекающихся Множеств. DSU — Disjoint Set Union. Мне одному пришлось пройти к задачам, чтобы понять о чем вопрос? Сокращение DSU я бы понял, а СНМ вообще не понял, и не понял что по русски написано.

→ Ответить

nikitosoleil

8 лет назад, # ^ |

-37

Аналогично. Огромное спасибо, что написали, я бы так и не понял. Зашел сюда как раз что бы ответить на вопрос, что такое СНМ

→ Ответить

http://informatics.mccme.ru/moodle/mod/resource/view.php?id=671

12 лет назад, # |

Далее: Структуры данных --> Cистема не пересекающихся множеств

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

О!

Говорят, ты валил СНМ, в котором подвешивание с rand()'ом. Правда ли это? Не подскажешь чем?) Ну и про прямое подвешивание, которое я обычно пишу тоже интересно (i.e dsu[get(a)]=get(b);)

→ Ответить

12 лет назад, # ^ |

for i=1..n-1 : Join(i,i+1)

Кстати, ты мне напомнил еще одну хорошую задачу, где принципиально, чтобы СНМ работало быстро:

Зимние всероссийские сборы 2010, 5 декабря 2010, bridges.

Краткое условие: нужно добавлять ребра в граф и после каждого запроса говорить "сколько сейчас мостов". Собственно, тогда первый раз и завалил :-)

→ Ответить

12 лет назад, # ^ |

Я имел ввиду, что сжатие путей есть, а подвешивание такое, как раз. На таком тесте будет летать:)

→ Ответить

12 лет назад, # ^ |

Я предположил, что у меня задача о персистентном СНМ ТЛится именно из-за рандома. Теперь все окончательно понятно.

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

Кстати, если автор тестов не изверг, я бы сам писал реально быстрый СНМ так:

Get(a) : return a == p[a] ? p[a] : (p[a] = Get(p[a]))
Join(a, b) : p[Get(a)] = Get(b)

Это уже в худшем случае работает аморатизированно за O(logN)

Чтобы работало принципиально дольше чем за O(1), нужно строить специфические тесты.

→ Ответить

12 лет назад, # ^ |

Ты же нам где-то давал задачу такие тесты строить.

→ Ответить

12 лет назад, # ^ |

Да =) Построить такой тест тянуло на целую задачу сборов к межнару... вроде же, это где-то там было?)

→ Ответить

12 лет назад, # ^ |

По моему A0-ЛКШ. Что в том году вобщем-то эквивалентно.

→ Ответить

12 лет назад, # ^ |

Если автор тестов не ты ?:)

Не подкинешь идею таких тестов?)

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

Про авторов тестов: в общем, просто опробуй мой вариант на существующих задачах :-)

Идея теста: нужно много раз делать p[Get(v)] = new Vertex, где v — текущая самая глубокая вершина. Утверждается, что если изначально ничего нет, то N Get-ов сработают за Theta(NlogN) операций.

→ Ответить

12 лет назад, # ^ |

Ага, спасибо помедитирую)

→ Ответить

Chunky.Gecko

12 лет назад, # ^ |

-8

А что надо сделать чтобы СНМ реально работал за О(1)? достаточно ли в "Join" добавить эвристику по количеству вершин в множестве?

→ Ответить