Loading...
kaloyannikov avatar kaloyannikov 531 Точки

Sticks oт Algorithms Exam - 15 May 2016

Линк към Judge и условието,

Ударих на камък с тая задача , има ли шанс с тоя подход да се реши или съм тръгнал в тотално грешна посока ?

http://pastebin.com/uyxEvM9b - 20 / 100.   

edit :  с топологично сортиране http://pastebin.com/Rh8tv56Y 60/100

Тагове:
0
Структури от данни и алгоритми 27/08/2016 23:39:54
AntyfrizZz avatar AntyfrizZz 238 Точки

Здравей,

 

Задачата се решава с топологично сортиране. Ако не се лъжа, на изпита взех примера за топологично и промених съвсем малко нещо (в момента не мога да се сетя какво), и минава.

http://pastebin.com/SLRHNM7k

EDIT: Сега сравних авторското с това и единственото, което съм променил (като не взимаме предвид пълненето на графа) е цикъла, който започва да маха нодове. Върти отзад напред.

for (int node = 0; node < graph.Length; node++)
for (int node = graph.Count - 1; node >= 0; node--)

 

Поздрави!

1
29/08/2016 17:48:49
kaloyannikov avatar kaloyannikov 531 Точки

Ами и аз така пробвах в другия пост , където е писал Innos решението ми е 1 към 1 с твоето и това от демата за source removal топологично понеже с dfs няма да се получи и  минава си 100/100 на C#, но на Java дава 90/100.

Поздрави!

0
Innos avatar Innos 419 Точки

Разгледах го, наблюдението ми е че n^2 решението на C#-а е по-бързо от колкото трябва да е, предполагам компилатора прави някакви оптимизации отдолу. Спрямо времето на Java, на изпита хората които писаха на Java да са били 1-2 и може би да не е изникнало като проблем. Въпреки че мисля че го тествахме на Java, оптималното решение се върти покрай 100~110ms, така че има възможност да е минало и да сме го оставили без екстра тестване. С оглед тестовете които направих, се вижда че Java-та найстина прави проблеми, така че ще вдигна времето, но в предвид факта че това са задачи за алгоритми, ще го вдигна само до толкова че гарантирано да минава оптималното решение. Факта че неоптимални решения на C# ще минават е тъжен, но неизбежен очевидно. Защо е сложено това решение като авторско е добър въпрос, двете решения на C# вадят еднакво време така че може да е от недоглеждане. Ще добавя отпималното решение и java версията му, но ще е утре. 

@kaloyannikov На въпроса за итерирането, да за външният цикъл имах предвид - ето един Rule of Thumb при алгоритмите, оптималното решение винаги ще итерира единствено и само върху правилните отговори. Това означава че if от този род няма и да ти трябва при оптимално решение, защото елементите по които ще минаваш винаги ще изпълняват условието на if-a така или иначе. На истинският отговор сега - сложността може да се свали до O(n log n), истинският жокер е Rule of Thumb-a, ако искаш направо код, утре ще кача авторските решения и може да погледнеш от там.

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