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

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

2
viraco4a avatar viraco4a 28 Точки

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

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

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

1
MartinBG avatar MartinBG 1189 Точки

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

 

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

 

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

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

3
viraco4a avatar viraco4a 28 Точки

Мартине, това което казваш е много интересно. Можеш ли да шернеш конкретни примерни за парсването?

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

Възможно е и Java да се справя по-добре с работата с големи масиви. Примерно на Rectangle Intersection бавното решение с матрицата 2000х2000 въобще не минава на C# и като памет, и като време. С Java същото мина 100/100 и то с разлика под границите. Не съм пробвал на други задачи, така че нямам по-сериозни наблюдения. 

2
MartinBG avatar MartinBG 1189 Точки

@viraco4a

Разбира се!

Това е задачата на Java - разликата в кода е само в парсването на първия ред от входните данни.

Вариантите на решението може да се тестват тук.

 

@k.sevov

На теория поне, не би трябвало който и да е съвременен език да е бавен при работа с големи масиви, защото това е доста базова операция и аз лично съм по-склонен да мисля, че в конкретния случай при Java сработва някоя оптимизация, която липсва или не е толкова добра в C#.

2