Софтуерно Инженерство
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 SoftUni Team 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