Loading...
kaloyannikov avatar kaloyannikov 531 Точки

Cable Merchant oт Algorithms Exam - 15 May 2016

Това е условието  =>

You're a merchant of the "Jicata" cable. You are given different lengths of "Jicata" {1, 2, 3, …, n} each with a different price. For example, we are given the sequence K = { 3, 8, 13, 15, 18, 20, 22 }:
Length    1    2     3     4      5      6      7
Price       3    8    13    15    18    20    22
Instead of selling a 5m cable for 18$, you noticed you can cut that cable into parts of lengths 2m (8$) and 3m (13$). Then you could use 2 connectors (to connect the cables) for a price of 2 * 1$ = 2$ and make a profit of 8 + 13 – 2 * 1 = 19$. Sneaky little bastard, aren't you?

Успях да скалъпя някакво решение , обаче въпроса ми е може ли да се оптимизира по някакъв начин http://pastebin.com/aiY9J34Q

Тагове:
1
Структури от данни и алгоритми 26/08/2016 18:45:34
Innos avatar Innos 419 Точки

Изглежда добре, гледам си го оптимизирал 2рият цикъл да се върти до i/2, така че не виждам на къде повече от алгоритмична гледна точка. Голяма част от времето ти в Judge-a идва от Scanner-а и stream-овете, понеже са супер тромави, защо най-вероятно само Oracle знаят. Промених ти леко кода, пробвай го в Judge ако искаш да видиш разликата.

1
26/08/2016 20:20:04
kaloyannikov avatar kaloyannikov 531 Точки

Да , явно от стриймовете и скенера почти всеки commit беше на кантар ,а сега около 0.05s,  което е доста голяма разлика. 

Има ли алтернативно решение с Map или подобно , но май всъщност винаги трябва да се провери дали при ситуация да речем дължина 5 дали 4+1 или 2+3 дава по-доброто решение за момента тъй като се променят стойностите динамично. 

1
26/08/2016 21:26:54
Innos avatar Innos 419 Точки

Няма нужда от екстра колекции, понеже пътя на алгоритъма позволява да модифицираш текущата. Да - трябва да обходиш всички възможни разрязвания до i/2, както един колега на изпита разбра че дори и да пресметнеш най-добрата цена на метър за всяка вече премината дължина, понякога най-доброто решение е да не я вземеш.

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