[Lab] Алгоритми - Problem Solving - Part I - Elections
Здравейте!
Попринцип, Ивайло, предлага задачата да се реши с "subset sum" подхода, честно казано, и на мен първо това ми дойде на ум, обаче на практика тестовете ми се бавят много (над 6 секунди). Ето решението ми: https://github.com/Vallerious/Algorithms-Course-Java/blob/e53e72e971b85971b85abc616bb4bfb7294d516b/exam_prep/Elections.java.
Мислих си дали не се решава с матрица, както би се решил Knapsack проблема, но K е прекалено голямо число, пък и плюс това нямаме някакъв "капацитет" до който да се лимитираме.
П.С. условието е тук: https://softuni.bg/trainings/resources/officedocument/30703/lab-problem-descriptions-algorithms-march-2018/open
Всичко хубаво, но поне ако може да вдигнете малко времената, защото решението на лектора от миналото издание 1:1 не минава по време на 3-4 теста (а на видеото, решението му минава със 100/100)
Не са добре времената нещо, да... Същото решение с няколкото часовника като го преписах от C# на Java и мина без никакви проблеми.
Това е една от малкото задачи, при които решението на Java е по-бързо от C# такова. *
Едно възможно обяснение, е може би по-бърза работа на Java с BigInteger, защото това е единственото по-специфично нещо в решението на тази задача.
* Когато съм правил сравнения, най-често решенията са сходни като време, а в останалите случаи C# е по-бърз.
Наскоро загубих няколко часа в оптимизации на алгоритъма и микрооптимизации на кода на една задача, докато открия, че забавянето (0.16с при 0.1 разрешени) идва от използването на стрийм за парсването от конзолата на 2 числа до int[]. Премахването на стрийма смъкна времето с 50% (под 0.08с) и задачата мина. Знаех, че стриймовете са бавни, но за първи път се сблъсквам с толкова ясно изразен проблем. :)