Programming Basics Exam - 18 December 2016 Letters Combinations
Здравейте,
Имате ли представа защо на два от тестовете в Judge ми дава Time limit и при двете ми решения на задачата?
http://pastebin.com/NY26Z6fb
http://pastebin.com/jU41h1H1
Best Answer
За тази задача в Judge има доста стегнат лимит по време, който е много лесно да бъде превишен с Java решение.
На мен ми се наложи да направя три версии с оптимизации, докато стигна от 80 до 100%, все заради забявяне с тестове 3 и 10.
Ето финалното ми решение: http://pastebin.com/FEpBP0wP
То е с около 4 пъти по-бързо от стандартното (0.077s срещу 0.305s), като основното ускорение идва от (пре)използването на char array за стринговете, в който променям само по една буква на итерация. По-малко ускорение има от изнасянето на проверката за валидност на текущия символ преди следващия вложен цикъл, което спестява малко време (не се въртят долните цикли, ако ще получим невалиден стринг на края).
С тези оптимизации кодът е с една идея по-трудно четим, но и Judge-a иска жертви :)
С първото решение си на прав път използвай continue за да пропуснеш когато "b" е в играта :)
Вместо:
Scanner scan = new Scanner(System.in);
може да използвате:
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
BufferedReader е доста по бърз от Scanner
става въпрос за Java
Ето моето решение
http://pastebin.com/aaNN3ZjH
И аз достигнах до тази задача, със същите проблеми на 3-ти и 10-ти тест. Бързото решениетo при мен беше да се махне print от цикъла и да се постави след края на всички цикли. За целта използвах StringBulider.
При стандартно решение с printf в последният цикъл, времената на 3-ти и 10-ти тест са: 0.314s и 0.178s, докато със StringBuilder времената са: 0.028s и 0.023s
Колеги, аз с помощ от приятел,стигнах до следното решение, за 100/100:
https://pastebin.com/euiX2JKd