Софтуерно Инженерство
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
Innos avatar Innos SoftUni Team 419 Точки

С този вход:
4
2
0 2
0 1
програмата ти изважда това като изход:
3 0 1 2
помисли защо. Задачата е за топологично сортиране и нещо екстра.

2
kaloyannikov avatar kaloyannikov 531 Точки

Аз го бях почнал с топологично и изкарах 60точки с dfs() обаче с него не става тъй като не мога да аддвам тея които могат да се вдигнат веднага,  ако имат деца. 

 

Със source removal на Java обаче не мога да изкарам повече от 90 и не ми е ясно защо , преди принтирах със String,Join сега го направих да е опашка и poll();

То дори си е 1 към 1 кода с тоя от демата само , че с почване от най-големия stick.

Четенето също не го правя с ламбда = > http://pastebin.com/GFd7ucRS

1 към 1 кода на C# си минава без проблем =>http://pastebin.com/FZKfNVg7

0
29/08/2016 13:40:11
Innos avatar Innos SoftUni Team 419 Точки

Прегледах го, това решение да минава на C# е oversight ако нещо, за жалост няма все още възможност за различни времеви лимити на C# и на Java за да може да се избегнат всички такива слабости. Пробвах с Java-ta и на мене ми удря лимит на последния тест с между 10-20ms. Ще направя по подробни тестове по-късно, за да съм сигурен че не е натоварване на Judge-a преди да го променям, но за сега мога да ти кажа, че решението ти може да се подобри. Усреднено сложността ти е O(n^2) с 2ният цикъл с който си търсиш следващият елемент и намаляваш predecessor-ите, виж дали можеш да го подобриш. Итерирането върху елементи които вече са взети или имат predecessor-и е излишно, ако паднеш до < 120 ms трябва да си го намерил.

0
29/08/2016 16:20:28
kaloyannikov avatar kaloyannikov 531 Точки

if (predecessorsCount[stick] == 0 && !isRemoved[stick])

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

0
29/08/2016 17:21:16
villyjord avatar villyjord 174 Точки

Алгоритмите не са ли чак на пролет 2017?

1
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