Loading...
Valleri avatar Valleri 304 Точки

[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 1077 Точки

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

2
viraco4a avatar viraco4a 28 Точки

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

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

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

1
MartinBG avatar MartinBG 4803 Точки

Това е една от малкото задачи, при които решението на 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 1077 Точки

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

2
MartinBG avatar MartinBG 4803 Точки

@viraco4a

Разбира се!

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

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

 

@k.sevov

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

2
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.