Здравейте колеги,
имам проблем с решението на тази задачата. Три теста не ми минават за необходимимото време от 200 ms. Някой може ли да хвърли едно решение, да видя къде бъркам, че очевидно програмата ми работи по-бавно отколкото трябва.
Линк към задачата. https://judge.softuni.bg/Contests/Practice/Index/812#1
Кодът ми - https://pastebin.com/57jezfKn
Благодаря!
Judge има доста стегнати тайминги за тази задача и дори оптимизирани откъм алгоритъм и използвани структури решения може да не минат от първия опит.
На пръв поглед, не си избрал най-добрата структура (LinkedList) за тази задача.
Това е моето решение отпреди половин година. Тогава е минало за 0.181 сек от първия път, а сега ми отне 10-ина опита (0.205-0.280 сек.), докато мине с 0.199. Явно и сървъра е доста натоварен.
Опитах разни микрооптимизации, но така и не стигнах до осезаемо по-бързо решение, което да минава гарантирано в Judge.
Благодаря ти много за отделеното време и решението, което ми показа! Аз от скоро започнах да пиша на Java и още не съм се запознал обстойно със структурите и бързината им.Използвах LinkedList, защото видях, че е по-бързо от List. Интересното, обаче, в този случай е, че структурата беше половината проблем. С първоначалния си код постигах стойности около 400 ms, като промених на ArrayDeque падна на около 300 ms и пак не минаваше. После започнах да тествам разликите с твоя код една по една и всъщност, се оказа, че другият проблем е Scanner, който аз използвах да чета входа. Когато го промених на BufferedReader взех 100% от първия опит и мина на 198 ms. Не очаквах, че начина на четене от конзолата да има такова значение.
Радвам се, че решението ми ти е било от полза!
Да, Scanner е по-бавен от BufferedReader, но за повечето задачи от това ниво на курса не би трябвало да оказва влияние върху резултатите. Явно в тази задача за някои от тестовете има доста на брой входни данни.
При задачи с много на брой изходни данни (много като заявки, а не като брой символи), може да се наложи да ползваш StringBuilder, с чиято помощ - освен всичко друго, ще може да отпечаташ крайният резултат само с едно извикване на print/println.
Мерси! Ще го имам пред вид.