Letisko

Zadanie príkladu Letisko od riešiteľa po prelúskaní sa príbehom vyžadovalo nasledovné. Majme postupnosť N celých čísel A0 až AN - 1. Nájdite súvislú podpostupnosť indexov [i, j) dĺžky M tak, aby f(i) bola minimálna pre i z [0, N - M), kde f(i) je pre známe M definovaná nasledovne:

f(i) = sum(Ai … Ai + M - 1) - min(Ai … Ai + M - 1) * M

Pozorný čitateľ si všimne, že zadanie dovoľuje z rezu odstrániť ľubovoľne rozložený 1 m2 v jednom ťahu, nie len práve štvorcovú suvislú plochu na indexe postupnosti, tak ako naznačuje zjednodušenie popísané vyššie.

Pre potrebu dôkazu zadefinujeme f'(j), ktorá vyjadruje cenu potrebnú na postavenie letiska, ak začneme stavať od j-teho metra pohoria, pričom j je v tomto prípade ľubovoľné desatinné číslo z [0, N - M).

Dôkazom, že vyššie spomenutá redukcia naozaj stačí, je argument, že f'(j) dosahuje extrémy funkčnej hodnoty len na celočíselných hodnotách j. To vidíme vďaka faktu, že f'(j) je lineárna na ľubovoľnom intervale [i, i+1) pre celočíselné i z [0, N-1). Náčrt dôkazu lineárnosti na daných intervaloch spočíva v tom, že f'(i) je vlastne kombinácia:

Po tomto dôkaze je zrejmé, že stačí f() vyhodnotiť na všetkých možných celočíselných indexoch v postupnosti a jeden z nich bude v globálnom minime. Otázka je teda už len ako vyhodnotiť hodnoty f() na celom jej definičnom obore a stihnúť to v časovom limite.

Na implementáciu riešenia použijeme techniku nazývanú sliding window. Vyčíslime f(0), a potom postupne f(1), f(2), atď. tak, že budeme čo najviac recyklovať informácie z predchádzajúcich výpočtov. Recyklácia hodnoty aktuálnej sumy na intervale je jednoduchá:

sum(Ai + 1 … Ai + M) = sum(Ai … Ai + M - 1) - Ai + Ai + M

Na recykláciu informácie o minime vzorové riešenie používa binárny strom, ktorý podporuje operácie vloženia a výberu ľubovoľných čísel a výpočet minima v postačujúco rýchlom čase.

Vzorové riešenie na vyhodnotenie funkčnej hodnoty f(i) dosahuje v rámci prístupu sliding window časovú zložitosť O(log M). Celková zložitosť je teda O(N log M). Vďaka nie práve najprísnejším vstupom boli pri tomto príklade akceptované aj riešenia s väčšou asymptotickou zložitosťou.

Vypracoval: Daniel Švoňava

Autor príkladu: Daniel Švoňava