Loading...
thekoceto avatar thekoceto 31 Точки

Softuniada 2020 - Задача 08. Sticks

Здравейте колеги,

Задачата е  08. Sticks от  Softuniada 2020.

Мъчи ме от поне ден и блокирах.

Започнах с Java. Ето и решението. Проблем се оказа времето и на 8 от 15 теста гръмна. Сигурен съм във вреността на изхода и остава времето. Неможах да намеря по бърз вариант и реших да пробвам с друг език.

Последва С++. Ето и това решение. Тук не генерира всички възможни вариации и немога да намеря проблема.

Ще съм благодарен ако се появи някоя насока.

 

 

Тагове:
0
SoftUni Tech Fest
MartinBG avatar MartinBG 4803 Точки
Best Answer

Това е решението ти на Java с няколко микрооптимизации - минава за около 0.2 секунди.

Като съвет:

- входно-изходните операции са много бавни. Стреми се да получаваш/изпращаш максимано количество данни наведнъж

- String.format() е много бавен метод; В Java 9.0+ конкатенацията на стрингове (с "+") е оптимизирана и достатъчно бърза

- подбирай си правилно структурите и използвай предимствата им - използвал си TreeSet, но накрая пускаш stream + sort за да го отпечаташ, а е достатъчно само да го отпечаташ

- Scanner е бавен - използвай BufferedReader винаги, когато можеш

 

_________________________

 

Грешката в C++ решението е в тази част:

         for (int i = index; i < sticksSize; i++){
             std::swap(sticks[index],sticks[i]);
             generate(set, sticks, sticksSize, i + 1); // трябва да е index + 1
             
             std::swap(sticks[index].first,sticks[index].second);
             generate(set, sticks, sticksSize, i + 1); // трябва да е index + 1
             
             // std::swap(sticks[index].first,sticks[index].second); - излишно
             // std::swap(sticks[index],sticks[i]);  - излишно
         }

 

1
22/04/2020 02:34:04
thekoceto avatar thekoceto 31 Точки

Всъщност замяната само на:

String.format("|%d-%d|", this.first, this.second);

с:

"|" + this.first + "-" + this.second + "|"

разреши проблема. Не знаех, че има толкова голяма разлика (макс 0.401 s срещу 1.354 s). Дори мислех че е обратно. Знам че тези времена не са меродавни, но все пак е показател.

Молбата ми е ако имаш свободно време да погледнеш и другото решение. Там ми е голяма загадка. Алгоритъма е същия, а резултатите не.

Благодаря за отделеното време.

П.С. Относно TreeSet и stream + sort  -> остатък е от опит да използвам HashSet като по-бърз контейнер и след това сортиране. Нямаше голяма разлика.

1
22/04/2020 01:47:26
MartinBG avatar MartinBG 4803 Точки

@thekoceto

smiley

Ъпдейтнах си отговора и за C++ решението.

1
22/04/2020 02:35:12
thekoceto avatar thekoceto 31 Точки

Време е за минутка срам. blush

Извинявай за изгубеното време.

1
22/04/2020 11:24:55
MartinBG avatar MartinBG 4803 Точки

Всички допускаме подобни грешки от недоглеждане - не е истина аз колко часове съм изгубил за подобни неща! smiley

За избягването им много помагат по-дългите и смислени за контекста имена на променливите дори и когато са с много кратък скоуп. Аз избягвам да ползвам for цикили, а когато го правя използвам "i" като име на индекса само в случаите, когато няма други променливи, използвани като индекс в скоупа.

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