Здравейте колеги,
Задачата е 08. Sticks от Softuniada 2020.
Мъчи ме от поне ден и блокирах.
Започнах с Java. Ето и решението. Проблем се оказа времето и на 8 от 15 теста гръмна. Сигурен съм във вреността на изхода и остава времето. Неможах да намеря по бърз вариант и реших да пробвам с друг език.
Последва С++. Ето и това решение. Тук не генерира всички възможни вариации и немога да намеря проблема.
Ще съм благодарен ако се появи някоя насока.
Това е решението ти на 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]); - излишно
}
Всъщност замяната само на:
с:
разреши проблема. Не знаех, че има толкова голяма разлика (макс 0.401 s срещу 1.354 s). Дори мислех че е обратно. Знам че тези времена не са меродавни, но все пак е показател.
Молбата ми е ако имаш свободно време да погледнеш и другото решение. Там ми е голяма загадка. Алгоритъма е същия, а резултатите не.
Благодаря за отделеното време.
П.С. Относно TreeSet и stream + sort -> остатък е от опит да използвам HashSet като по-бърз контейнер и след това сортиране. Нямаше голяма разлика.
@thekoceto
Ъпдейтнах си отговора и за C++ решението.
Време е за минутка срам.
Извинявай за изгубеното време.
Всички допускаме подобни грешки от недоглеждане - не е истина аз колко часове съм изгубил за подобни неща!
За избягването им много помагат по-дългите и смислени за контекста имена на променливите дори и когато са с много кратък скоуп. Аз избягвам да ползвам for цикили, а когато го правя използвам "i" като име на индекса само в случаите, когато няма други променливи, използвани като индекс в скоупа.