Софтуерно Инженерство
Loading...
+ Нов въпрос
Valleri avatar Valleri 292 Точки

[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

Тагове:
k.sevov avatar k.sevov 1050 Точки

Можеш да разгледаш как я е решил лекторът в миналото издание на курса тук

2
viraco4a avatar viraco4a 28 Точки

Всичко хубаво, но поне ако може да вдигнете малко времената, защото решението на лектора от миналото издание 1:1 не минава по време на 3-4 теста (а на видеото, решението му минава със 100/100)

0
k.sevov avatar k.sevov 1050 Точки

Не са добре времената нещо, да... Същото решение с няколкото часовника като го преписах от C# на Java и мина без никакви проблеми. 

1
MartinBG avatar MartinBG 1139 Точки

Това е една от малкото задачи, при които решението на Java е по-бързо от C# такова. *

 

Едно възможно обяснение, е може би по-бърза работа на Java с BigInteger, защото това е единственото по-специфично нещо в решението на тази задача.

 

* Когато съм правил сравнения, най-често решенията са сходни като време, а в останалите случаи C# е по-бърз.

Наскоро загубих няколко часа в оптимизации на алгоритъма и микрооптимизации на кода на една задача, докато открия, че забавянето (0.16с при 0.1 разрешени) идва от използването на стрийм за парсването от конзолата на 2 числа до int[]. Премахването на стрийма смъкна времето с 50% (под 0.08с) и задачата мина. Знаех, че стриймовете са бавни, но за първи път се сблъсквам с толкова ясно изразен проблем. :)

3