[Homework] Tree And Graph Traversal - Март 2016
Здравейте колеги, ето моите решенията на задачките от домашното:
https://github.com/vdonchev/Tree-ndGraphTraversal-Homework
Ще се радвам на коментари и въпроси.
Поздрави!
Аз имам два въпроса относно последната (5-та) задача.
1. Каква е сложността? За всяка поредица излизат n-k на брой други поредици. И за всяка една от тези n-k поредици излизат други n-k на брой поредици, и т.н. Тоест би трябвало да е нещо от сорта на О(n^n-k) или O(n* n^n-k)?
2. Аз на последния пример изкарвам -1. Видях, че и твоито решение дава -1, а отговорът пише, че е 7. Погледнах също и едно друго решение и то дава -1. Ние ли грешиме или просто примера е сгрешен?
Не съм почнал още домашното, но на четвърта не би ли трябвало сложността да е O(n), според мен едно обхождане на дървото е достатъчно, а в хинта са дали че при правилен алгоритъм имаме квадратична сложност?
И според мен трябва да е така. Като пуснеш един DFS отляво и отдясно си се получава точно O(n). Не знам даже какво трябва да се направи за да е O(n*n) :D
Ами да, обхождането с DFS си е O(n), но след това като започнем да търсим най - голямата сума м/у два нода, имаме два вложени форийча: за всяка сума пробваме да я съберем с всички останали... не е ли така, или греша?
..освен ако не се оптимизира някак да помним коя двойка вече сме пробвали, и да не я повтаряме...
Еми аз мисля, като стартираме от корена слизаме до всяко едно листо и помним best sum и second best, както и като открием best запомняме нода. Това е едно обхождане и накрая просто възтановяваме пътищата до корена от двата нода.
Hi,
Имам някои въпроси по условието на 4-та задача. Според мен като че ли не е задължително the longest path by sum of the nodes from leaf to leaf да включва root-а, но е задължително да започва и да свършва с листо. Обаче пътят с най-голяма сума в дървото не е задължително да включва листо/листа, например при листа с отрицателно тегло. Ако това е вярно, как методът private static int FindLongestPath(int longestPath) в представеното решение (_04.LongestPathInATree) гарантира, че намереният път започва и завършва с листо?
При вход:
10
9
5 -11
1 8
-11 -3
8 -7
5 1
-11 2
8 -6
2 -15
8 -4
се получава резултат 20, като нодовете в двата края са -3 и 8.
Може би греша, но ми се струва, че hint № 3 леко издиша в този случай.
След като прочетох коментара ти, разгледах пак решението си и условието, и съм напълно съгласен че в решението което съм написал, не се гарантира, че намерения път ще бъде от листо до листо. Също така, най - дългия път определно не трябва задаължително да минава през корена... за разлика от решението ми.
Надявам се да имам млако свободно време идните дни, за да седна и да реша на ново задачата.
Благодаря ти за коментара! :)
Вчера си поиграх със задачата, може би най-интересната от това домашно, защото има възможности за оптимизация. Стъпките коитоследвах са да намерим разстоянието от root-a до всички node-ове и намирането на всички leaves. От там трябва да намерим за всяка уникална двойка leaves (където 2та leaf-a са различни) разстоянието между тях през най-близкия общ родител. Изборите ни са 2 тук:
Първият: за всеки 2 leaf-a намираме най-малкия общ родител чрез изграждане на лист от родителите за всеки от 2та leaf-a и засичаме 1вият повтарящ се елемент. Операцията за изграждане на лист-a с родители е в най-лошият случай сложност O (h) където h e височината на дървото, ако дървото ни е балансирано сложността е O(log(n)). Този метод може да е тромав при определени ситуации - примерно небалансирано дърво с много leaves.
Вторият: Алтернативата ни е намиране на всички най-малки общи родители за цялото дърво по алгоритъма на Tarjan за намиране на lowest common ancestors, който има сложност О(n), но се извършва 1 път.
След като намерим всички уникални 2ки leaves и техните общи родители, намираме разстоянието между 2тe leaves по хинта в задачата.
За жалост и на двата въпроса не мога да ти дам конкретен отговор.
Виждях и аз че получавам -1, но пък съм спазил стъпките описани в условието.. така, че само човека който е писал домашното, може да каже къде е грешката.
Поздрави!
Изглежда сте прави, аз също получавам -1 на последния тест. Преди да го променим обаче, нека още някой сподели решение и да каже, ако получава 7.
На последния пример би трябвало да е -1, защото 7 2 1 6 8 4 3 не е пермутация на числата от 1 до 7. 5 е изпуснато, затова пък има 8.
Реших да смъкна всяко едно от числата 6, 7 и 8 с едно --> но на 6 2 1 5 7 4 3 моята програма също извежда -1. Така че си мисля, че с обръщания по четворки няма да се получи. С k=2 отговорът е 11.
А ето го и моето решение: http://pastebin.com/fV9A0xv4
Аз леко доразвивам идеята в подсказката - правя граф, чиито върхове са възможните пермутации и свързвам с ребра тези от тях, които могат да се получат с едно обръщане на k елемента. Останалото е ясно - опашка и BFS.
При една или няколко заявки ще работи малко по-бавно от авторското решение, но при повечко заявки за едно и също n - ще пуска BFS върху вече построения граф и ще е доооста по-бързо, отколкото ако на всяка заявка пълним опашката с помощта на пресмятания, а не от графа.