A greedy approach to Turtle Tower problem.

Wieża Żółwi to akademicki problem algorytmiczny. Ciekawa obserwacja, prosty dowód i elementarna wiedza w zakresie technik programowania dynamicznego pozwala uzyskać eleganckie rozwiązanie o kwadratowej złożoności czasowej i liniowej złożoności pamięciowej.W poniższej pracy przedstawiono nowe podejście do problemu. Dodatkowa obserwacja pozwala zastosować metodę zachłanną i zredukować złożoność czasową do logarytmiczno-liniowej z niezmienioną złożonością pamięciową.

The Turtle Tower is a computer science academic problem. It requires an insightful observation,a slight prove and elemental knowledge in dynamic programming techniques to arrive with elegantsolution with quadratic time and linear space complexity.This paper demonstrates another approach to the problem. An additional observation allows to apply a greedy method and reduce the time complexity to log-linear with the space complexity untouched.