Меня недавно спрашивали про задачу о наименьшем общем предке. А именно, о поиске LCA без какого бы то ни было препроцессинга дерева, чтобы один запрос отвечался за время O(r), где r — расстояние между вершинами запроса.
Если ограничений по памяти нет, то решение придумывается почти мгновенно: будем параллельно поднимать вверх обе вершины, и помечать в двух массивах, какие вершины мы посетили по первому пути, и какие — по второму пути. Как только мы шагнём в вершину, которая есть в обоих путях — это и есть LCA.
Но такое решение требует O(n) памяти или, если использовать hash-set, то O(r) памяти.
Мне же засел в голову такой вопрос: а есть ли решение практически без дополнительной памяти, т.е. с потреблением памяти O(1)? (Разумеется, нужно сохранить ту же временную асимптотику O(r).)
Оказалось, да. Предлагаю и вам поломать голову над этой симпатичной задачкой. (Возможно, боян? Я не встречал).
Как всегда, свои варианты решения в комментариях прячьте под правками, чтобы никто случайно не прочитал решение раньше времени.
Solution in edit.
How to find a vertex with a bigger depth?
We lift up each vertex until we reach the root and we count how many vertices we passed.
Consider an extreme situation: the tree is a chain with root 1. When asking LCA for vetrex n and vetrex n (certainly their LCA is N...they are the same vetrex), lifting up each vetrex leads to O(n) time complexity because you have to go over the whole chain.
Некоторое кривое решение в правке
Это похоже на правильное решение.
Решение немного проще в правке.
Да, у меня примерно то же самое.
Осталось только научиться подниматься на 2^i узлов вверх по дереву без препроцессинга
Здесь подразумевается тупой подъем по одному предку за раз за O(2^i) (то есть мы заранее знаем предка у каждой вершины). И в таких предположениях описанное решение работает за O(r).
"то есть мы заранее знаем предка у каждой вершины"
А это не O(N) доп. памяти выходит?
Это не доп память, это дано изначально. Дерево у нас таким образом представлено по условию задачи. Мы отвечаем на запрос за O(r) времени и используя O(1) памяти.
Ну если это доп память, то у нас не дерево какое-то ибо вообще ничего нет)
Ну почему, дерево ведь можно задать списками детей. И постановка задачи вообще не очень очевидна.
Да следует внимательней читать посты
ответ в правке
моя версия в правке (неверное, расстояние больше проходится)
правка
решение в правке
решение (примерно тоже, что у vitar, оказывается)
in edit
Yes. It is correct solution.
В задаче подразумевается, что для каждой вершины мы знаем предка, хотя явно это нигде не сказано.
да человек хотел просто поделиться красивой задачкой, а вы накидываетесь на него...
не срать ли как граф задается? хоть списком сыновей, хоть предками? очевидно, что как-то задается, на усмотрении автора решения — как хочет, так пусть и задает
Так никто же не спорит. Задача хорошая и решение тоже интересно. Просто если не указать заранее, что дерево задается списком предков, то можно подумать, что подсчет для каждой вершины предка — дополнительные O(N) памяти.
От того, как задаётся граф, задача зависит достаточно сильно. Если не указывать родителя, то задача вообще не будет иметь решения, а если, например, дополнительно указывать для каждой вершины глубину, то задача станет намного проще. Бывает, что в задаче нельзя использовать дополнительную память, но можно перезаписывать существующую (ту, в которой передаются входные данные). С таким дополнением, например, можно обойти дерево, заданное списками смежности, используя O(1) дополнительной памяти. Подобные тонкости надо обязательно указывать в условии задачи, так как они существенны для её решения.
мне почему то показалось очевидным 2 факта:
что никакую глубину и прочую информацию не связанную напрямую с заданием графа хранить нельзя
граф задается на усмотрение автора решения — как хочет, так пусть и задает, но только чтобы это было именно задание графа, а не еще что-либо дополнительное
К сожалению, понятие "не связанную напрямую с заданием графа" трудно формализуется.
просто, насколько я понял, в этой задаче больше интересно решение, нежели применение...
и если уж человек решает эту задачу, он конечно может схитрить и решить ее как-то с предподсчетом или чем-нибудь, и внушив себе, что это задание графа, но кого он обманет? себя? и вы прекрасно понимаете, что в этой фразе: “не связанную напрямую с заданием графа” я имею ввиду
Ты несколько раз повторил "граф задается на усмотрение автора решения — как хочет, так пусть и задает" и тебе несколько раз ответили, в чем ты не прав. Еще раз повторяю, если мы не знаем для каждой вершины предка задача не имеет решения за O(r). Для предложеных решений необходимо знать предка каждой вершины. Если граф задан списками смежности, то нам понадобится препроцессинг за O(n) и O(n) дополнительной памяти, чтобы применить предложенные алгоритмы. Я не могу строго доказать отсутствие решения в случае если мы не знаем предков, но это очень правдоподобно. В любом случае эта задача предполагает что мы обладаем информацией о предках, потому как авторское решение использует эту информацию.
Ну память по факту не дополнительная. Ей можно просто затереть старую память, но О(н) времени препроцессинга никуда не девается, согласен.
С какого перепугу ты решил перезаписывать память? Где сказано что это можно делать? Задача поставлена не формально, но додумывать то зачем. Прочитай коммент и проникнись.