Решението със сложност O(N*N*N) е засегнато в описанието на квадратичното решение, понеже двете си приличат.

O(N*N) решение: Пробваме всяка възможна двойка (i,j) i<j да бъде двата края на въжето. Първо трябва да проверим дали h[i]<=h[j]. Ако това е вярно, пътят от сграда i до j е проста сметка. Пътят от началото до сграда i може да се намери по няколко начина. Първият е, ако всеки път изчерпваме всички двойки (i,j) за всяко i и после увеличаваме i с едно, да пазим сума на всички изминати сгради преди i и след приключване на сграда i да прибавим нейната височина към тази сума. Вторият и по-лесен начин е с префиксен масив. Дефинираме pref[i] като сборът от височините на всички сгради до сграда i включително. Тогава pref[i]=pref[i-1]+abs(h[i]-h[i-1])+1 (+1 заради пътят по покрива на самата сграда), и така pref[i] пази дължината на пътя от началото до сграда i. Аналогично това са и двата метода за намиране на дължината на пътя от j до края, или с изчерпване на двойките по j, или използвайки същият префиксен масив за намиране на pref[N+1]-pref[j-1], което ни дава търсената дължина. За постигане на O(N*N*N) сложност, можем всеки път като търсим дължината на пътя от началото до i и от j до края да итерираме през индексите и да добавяме височините им към някаква сума. По този начин за всяка двойка O(i,j) ще направим N итерации за намиране на тези две дължини, и понеже имаме грубо N*N двойки, то общата сложност е N*N*N.

O(N*logN)/O(N), h[i]<=3
Тук вече старият подход няма да ни върши работа, тъй като сложността му не подлежи на сериозни оптимизации. За тези ограничения е нужно да се направи следното наблюдение: За фиксиран десен край на въжето не ни интересува колко е точната дължина на левия край, а ни интересува колко на далеч се намира от десния край. От всички i, за които h[i]<=h[j], може да се докаже, с неравенство на триъгъника, че оптималният вариант е най-лявото такова i. Ще използваме dp[i], в което ще пазим дължината на най-краткият път от началото до сграда i. За десен край на въжето j, dp[j]=min(dp[j-1]+abs(h[j-1]-h[j])+1,pref[i]+sqrt((j-i)*(j-i)+(h[j]-h[i])*([j]-h[i]))). Левият е вариантът, в който въжето не завършва в j, а десният е вариантът, в който завършва в j. Така накрая отговорът ще се пази в dp[N], зависи от имплементацията дали трябва да се прибави и h[N] към dp[N]. Сега остава да измислим как да намерим най-левият индекс i, за който h[i]<=h[j]. Ако h[j]=1 ние трябва да намерим най-левия индекс i, за който h[i]=1. Аналогично ако h[j]=2, трябва да сравним най-левия индекс, за който h[i]=2, и най-левия индекс, за който h[i]=1, и от тях да изберем по-малкия. Същата логика прилагаме за h[j]=3. Тъй като h[i]<=3, то нас ни интересува единствено най-левите инекси, за които h[i]=1, h[i]=2 или h[i]=3. Това може да стане както със труктура от данни за минимум (безмислено сложно за тази подгрупа), така и с прост масив с 3 клетки, в който firstOccurance[i] пази първото срещане на височина i. Разбира се, ако не съществува сграда i<j, за която h[i]<=h[j], то изпускаме първия вариант за dp[j].

O(N*logN)
Тук идеята за dp-то е същата, но ни трябва бърз начин да намерим най-лявото i, за което h[i]<=h[j]. Ограниченията на тази подгрупа ни позволяват да използваме структура от данни с логаритмична сложност на въпросите. Един вариант за такава структура е дърво на Фенуик. Когато срещнем h[i], ще ъпдейтнем дървото в индекс h[i] (разбира се, ако тази височина е вече срещана, то стойносстите в дървото няма да се променят), а когато питаме за десен край j ще подаваме заявко типа: коя е най-малката стойност между позиции 1 и h[j]. Алтернативен подход е да сортираме височините преди смятане на dp стойностите. Важно е да обърнем внмание, че ни интересуват и самите индекси, затова сортираме двойките (h[i],i). След сортирането можем с едно обхождане на сортирания вектор да намерим оптималното i за всеки десен край j. 

O(N)
За улеснение ще считаме, че фиксираме ляв край на въжето и търсим най-далечния възможен десен край. Първо правим префиксен масив prefmin[i], който пази най-малката стойснот до елемент i вкючително и индекса, на който се среща. Очевидно prefmin[i].val<=prefmin[i-1].val. Интуитивно, нас ни интересуват възможно най-ниски леви краища на въжето, тъй като ако сравнявма две сгради i1 и i2, то ако h[i1]<h[i2], то оптималният десен край за i1 ще е по-далечен или равен на оптималния десен край за i2. Щом prefmin е намаляваща редица, то оптимумите за prefmin[i].idx са растяща редица. Това ни позволява да ползваме показалка за десния край, която ще увеличаваме при промяна на prefmin[i].val, тоест ако prefmin[i].val<prefmin[i-1].val. Тази показалка ще трябва да отива до най-далечния индекс j, за който h[j]>=prefmin[i].val. Това може да се постигне със суфиксен масив за максимуми, който на позиция i пази най-голямата височина измежду индекси i и N и индексът, на който се намира тя. Очевидно suffmax[i].val>=suffmax[i+1].val, така че това е намаляваща редица. Та за фиксирано prefmin[i] можем да увеличаваме показалка j докато е вярно, че suffmin[j].val>=prefmin[i].val. Така си гарантираме, че сме стигнали до най-десния възможен индекс за десен край, и че следващият оптимален индекс ще е или сегашният или някой в дясно от него. Отново използваме старата dp зависимост.

Предвидено беше за 100 точки да минават само линейни решение, но, уви, избраните ограничения за време и размер не бяха достатъчно стриктни. Реално се оказва, че някои решения с логаритмична сложност също изкарват 100 точки.