Софтуерно Инженерство
Loading...
kaloyannikov avatar kaloyannikov 530 Точки

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 SoftUni Team 419 Точки

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

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

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

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

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

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

1
26/08/2016 22:38:34