Професионална програма
Loading...
thekoceto avatar thekoceto 31 Точки

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

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

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

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

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

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

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

 

 

Тагове:
0
SoftUni Tech Fest
MartinBG avatar MartinBG 2789 Точки
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 2789 Точки

@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 2789 Точки

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

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

1