Loading...
Vesso1980 avatar Vesso1980 486 Точки

Проблем със задачата - Little Alchemy

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

имам проблем с решението на тази задачата. Три теста не ми минават за необходимимото време от 200 ms. Някой може ли да хвърли едно решение, да видя къде бъркам, че очевидно програмата ми работи по-бавно отколкото трябва. 

Линк към задачата. https://judge.softuni.bg/Contests/Practice/Index/812#1

Кодът ми - https://pastebin.com/57jezfKn 

Благодаря!

Тагове:
0
Module: Java Advanced
MartinBG avatar MartinBG 4803 Точки
Best Answer

Judge има доста стегнати тайминги за тази задача и дори оптимизирани откъм алгоритъм и използвани структури решения може да не минат от първия опит.

На пръв поглед, не си избрал най-добрата структура (LinkedList) за тази задача.

Това е моето решение отпреди половин година. Тогава е минало за 0.181 сек от първия път, а сега ми отне 10-ина опита (0.205-0.280 сек.), докато мине с 0.199. Явно и сървъра е доста натоварен.

Опитах разни микрооптимизации, но така и не стигнах до осезаемо по-бързо решение, което да минава гарантирано в Judge.

0
Vesso1980 avatar Vesso1980 486 Точки

Благодаря ти много за отделеното време и решението, което ми показа! Аз от скоро започнах да пиша на Java и още не съм се запознал обстойно със структурите и бързината им.Използвах LinkedList, защото видях, че е по-бързо от List. Интересното, обаче, в този случай е, че структурата беше половината проблем. С първоначалния си код постигах стойности около 400 ms, като промених на ArrayDeque падна на около 300 ms  и пак не минаваше. После започнах да тествам разликите с твоя код една по една и всъщност, се оказа, че другият проблем е Scanner, който аз използвах да чета входа. Когато го промених на BufferedReader взех 100% от първия опит и мина на 198 ms. Не очаквах, че начина на четене от конзолата да има такова значение. 

1
MartinBG avatar MartinBG 4803 Точки

Радвам се, че решението ми ти е било от полза!

Да, Scanner е по-бавен от BufferedReader, но за повечето задачи от това ниво на курса не би трябвало да оказва влияние върху резултатите. Явно в тази задача за някои от тестовете има доста на брой входни данни.

При задачи с много на брой изходни данни (много като заявки, а не като брой символи), може да се наложи да ползваш StringBuilder, с чиято помощ - освен всичко друго, ще може да отпечаташ крайният резултат само с едно извикване на print/println.

1
12/04/2018 13:54:31
Vesso1980 avatar Vesso1980 486 Точки

Мерси! Ще го имам пред вид.

0
XuTkO avatar XuTkO 2 Точки

Я вижте, доста го изчистих: РЕШЕНИЕ

1
Vesso1980 avatar Vesso1980 486 Точки

Оу, 102ms .. това е 2 пъти по-бързо от лимита. Супер! Мерси, че го сподели, сега ще го разгледам обстойно да видя, кое още ме е бавило.

0
AtanasYordanov avatar AtanasYordanov 37 Точки

Ако искаш, виж и това решение: https://github.com/AtanasYordanov/Java-Advanced/blob/master/08.ExamPreparation/Exam_22_10_2017/LittleAlchemy.java

Дори със stream минава за по-малко от 100ms. Ако махнеш stream-а минава за 40-50ms.

Имай предвид, че ArrayDeque, работи доста по-бързо от LinkedList като опашка и също така BufferedReader > Scanner.

1
06/06/2018 22:55:02
Vesso1980 avatar Vesso1980 486 Точки

Е, твоят е още по-бърз :). Ами мисля, че по времето, когато аз опитвах да я решавам, нещо е имало промлем със сървъра, защото и Мартин по горе се оплакваше, че едва минава с 200 и то от няколко опита. В момента с моя алгоритам, който пригодих с помощта на Мартин минава на 100, а преди мина с 198. 

Иначе, това животно много ми хареса, мисля да го изплагиатствам :) ->  for (String input = reader.readLine(); !input.equals("Revision"); input = reader.readLine())

 

0
XuTkO avatar XuTkO 2 Точки

И аз го гепвам :)

0
06/06/2018 23:35:41
Lallushe avatar Lallushe 0 Точки

Само да вмъкна, че в решението ти не е нужно да ползваш ArrayDeque за златото. Можеш да използваш обикновен int.

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