Loading...
krisdx avatar krisdx 68 Точки

Аз имам два въпроса относно последната (5-та) задача. 

1. Каква е сложността? За всяка поредица излизат n-k на брой други поредици. И за всяка една от тези n-k поредици излизат други n-k на брой поредици, и т.н. Тоест би трябвало да е нещо от сорта на О(n^n-k) или O(n* n^n-k)?

2. Аз на последния пример изкарвам -1. Видях, че и твоито решение дава -1, а отговорът пише, че е 7. Погледнах също и едно друго решение и то дава -1. Ние ли грешиме или просто примера е сгрешен?

0
03/03/2016 15:27:29
djc_bg2015 avatar djc_bg2015 923 Точки

За жалост и на двата въпроса не мога да ти дам конкретен отговор.

Виждях и аз че получавам -1, но пък съм спазил стъпките описани в условието.. така, че само човека който е писал домашното, може да каже къде е грешката.

Поздрави!

1
a_rusenov avatar a_rusenov 1103 Точки

Изглежда сте прави, аз също получавам -1 на последния тест. Преди да го променим обаче, нека още някой сподели решение и да каже, ако получава 7.

1
aslv1 avatar aslv1 304 Точки

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

0
07/03/2016 18:01:51
moholovka avatar moholovka 169 Точки

Не съм почнал още домашното, но на четвърта не би ли трябвало сложността да е O(n), според мен едно обхождане на дървото е достатъчно, а в хинта са дали че при правилен алгоритъм имаме квадратична сложност?

1
krisdx avatar krisdx 68 Точки

И според мен трябва да е така. Като пуснеш един DFS отляво и отдясно си се получава точно O(n). Не знам даже какво трябва да се направи за да е O(n*n) :D

0
djc_bg2015 avatar djc_bg2015 923 Точки

Ами да, обхождането с DFS си е O(n), но след това като започнем да търсим най - голямата сума м/у два нода, имаме два вложени форийча: за всяка сума пробваме да я съберем с всички останали... не е ли така, или греша?

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

0
04/03/2016 07:59:21
moholovka avatar moholovka 169 Точки

Еми аз мисля, като стартираме от корена слизаме до всяко едно листо и помним best sum и second best, както и като открием best запомняме нода. Това е едно обхождане и накрая просто възтановяваме пътищата до корена от двата нода.

2
aababy avatar aababy 14 Точки

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 леко издиша в този случай.

0
05/03/2016 02:09:11
djc_bg2015 avatar djc_bg2015 923 Точки

След като прочетох коментара ти, разгледах пак решението си и условието, и съм напълно съгласен че в решението което съм написал, не се гарантира, че намерения път ще бъде от листо до листо. Също така, най - дългия път определно не трябва задаължително да минава през корена... за разлика от решението ми.

Надявам се да имам млако свободно време идните дни, за да седна и да реша на ново задачата.

Благодаря ти за коментара! :)

1
Innos avatar Innos 419 Точки

Вчера си поиграх със задачата, може би най-интересната от това домашно, защото има възможности за оптимизация. Стъпките коитоследвах са да намерим разстоянието от 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 по хинта в задачата.

2
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.