[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. Ние ли грешиме или просто примера е сгрешен?
За жалост и на двата въпроса не мога да ти дам конкретен отговор.
Виждях и аз че получавам -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 върху вече построения граф и ще е доооста по-бързо, отколкото ако на всяка заявка пълним опашката с помощта на пресмятания, а не от графа.