Nechť b je rok, v němž Kocourkov dosáhl úplně největší populace. Jestliže v nějakém roce a předcházejícím roku b dosáhl vyšší populace než v nějakém roce c následujícím po roce b, pak trojice a, b a c splňuje požadavky zadání; abychom rozhodli, zda takové roky a a c existují, stačí nám znát maximální populaci v letech 1 až b-1 a minimální populaci v letech b+1 až N.
Jestliže takto rovnou nenalezneme řešení, pak byla populace před rokem b vždy nižší než populace po roce b, hledaná trojice roků tedy musela buď celá nastat před rokem b, nebo celá po roce b. To nám dává přirozený rekurzivní algoritmus:
/* Nalezne trojici a<b<c s vlastnostmi ze zadání tž. od <= a, b, c <= do.
Vrací true existuje-li taková trojice, false jinak. */
bool vzestup_a_pad (int od, ind do)
{
if (do <= od + 1)
return false;
b = pozice maxima populace z intervalu od, do;
a = pozice maxima populace z intervalu od, b - 1;
c = pozice minima populace z intervalu b + 1, do;
if (populace[c] < populace[a])
{
vypiš a, b, c;
return true;
}
return vzestup_a_pad (od, b - 1) || vzestup_a_pad (b + 1, do);
}
Počet rekurzivních volání funkce vzestup_a_pad je nejvýše N – stačí nahlédnout, že každé číslo ze vstupu je maximem v nejvýše jednom z intervalů, na které je tato funkce volaná. Potřebujeme ale umět efektivně hledat pozice maxim a minim v intervalech.
Jednoduché řešení je si předpočítat pozici minima a maxima pro každý interval, jehož délka je mocnina 2. Takových intervalů je O(N log N) a jejich minima a maxima snadno spočítáme se stejnou časovou složitostí (minimum z intervalu od a do a+2k-1 je rovno minimu z intervalů od a do a+2k-1-1 a od a+2k-1 do a+2k-1=(a+2k-1)+2k-1-1, máme-li tedy minima již předpočítaná pro intervaly délky 2k-1, můžeme ho určit v konstantním čase). Chceme-li nyní zjistit minimum z intervalu od a do b, stačí najít největší mocninu dvojky x menší nebo rovnu b-a+1 (kterou můžeme mít také předpočítanou) a vrátit menší z minim intervalů od a do a+x-1 a od b-x+1 do b. Pozici minima a analogicky maxima z intervalu tedy dokážeme určit v konstantním čase.
Celková časová a paměťová složitost tohoto řešení tedy bude O(N log N), dominuje ji složitost předzpracování pro vytvoření datové struktury popsané v předchozím odstavci. Poznamenejme, že existuje obdobná datová struktura, kterou lze vytvořit v lineárním čase, čímž lze časovou složitost vylepšit na O(N); nicméně tato datová struktura je podstatně složitější.
Existuje ale i jednodušší řešení. Budeme postupně procházet posloupnost p1, …, pN populací v jednotlivých rocích. Nechť nyní zpracováváme rok x a zajímá nás, zda tento rok může hrát roli roku c v nějakém řešení. To se stane právě tehdy, když existují nějaké roky a<b před x takové, že pa<pb a zároveň px<pa. Pro ověření této podmínky zjevně stačí znát roky a a b takové, že a<b<x a pa<pb a populace pa je největší možná mezi dvojicemi a a b splňujícími tyto podmínky.
Budeme si tedy průběžně udržovat informaci o takových rocích a a b a jejich populacích pa a pb. Jak se tato informace může změnit při zpracování roku x? Je možné, že existuje nějaký rok y přecházející roku x takový, že py>pa, ale mezi x a y není nikdy populace vyšší než py, takže y zatím nesplňuje podmínky pro možnou volbu roku a. Jestliže ale px>py, pak bychom si chtěli místo roků a a b od nynějška pamatovat roky y a x.
Abychom toto mohli dělat efektivně, budeme si kromě roku b také pamatovat ostatní zatím zpracované roky y, v nichž byla populace vyšší než v roce a. Povšimněme si, že takové roky se nutně v posloupnosti vyskytují v klesajícím pořadí populací, jinak by některý z nich musel hrát roli a. Bez újmy na obecnosti proto můžeme předpokládat, že b je poslední z takových roků (a má tedy mezi nimi nejmenší populaci). Místo jednoho roku b si proto budeme pamatovat zásobník B roků, v nichž je populace vyšší než v roce a, setřízený tak, že populace roku na vrcholu zásobníku B je nejmenší.
Když zpracováváme rok x, nejprve zkontrolujeme, zda px<pa; je-li tomu tak, pak a, rok na vrcholu zásobníku B a rok x tvoří hledané řešení. Jestliže px>pa, pak zkontrolujeme, zda nějaké roky na zásobníku B mají populaci menší než px. Jestliže ano, pak si ten z nich s největší populací zapamatujeme jako rok a a roky s menší populací vyhodíme z B; povšimněme si, že vzhledem k uspořádání roků v zásobníku projdeme v B nejvýše o dva prvky víc, než kolik jich vyhodíme, časová složitost tohoto kroku je tedy úměrná počtu smazaných prvků. Každopádně pak vložíme x na zásobník B, jelikož jeho populace je vyšší než populace v roce pa (ať už jsme a měnili nebo ne).
Jelikož popsaný algoritmus pouze jednou projde vstup a každé číslo nejvýše jednou přidá a odebere ze zásobníku B, časová i paměťová složitost je O(N).
Z učebního textu o stromochodech pravděpodobně znáte základní grafovou terminologii (vrcholy, hrany, cesty), kterou budeme používat i v tomto řešení (křižovatky jsou vrcholy, ulice jsou hrany).
Ukážeme si, jak vyřešit úlohu v čase O(m·log(n)) za předpokladu, že je optimální pouze jednou změnit dopravní prostředek. Budeme předpokládat, že Norbert vyjde z domova pěšky a někde cestou přesedne na koně (opačná situace je symetrická a náš algoritmus může vyzkoušet obě a vrátit lepší z nich).
Jako přímočaré řešení by se nabízelo zjistit si délku nejkratší pěší cesty z Norbertova domova do každého vrcholu s koňostavem a potom délku nejkratší cesty na koni z každého vrcholu s koňostavem na radnici, a potom vybrat takový koňostav, že součet délek jeho příslušných dvou cest je co nejmenší. Na hledání nejkratších cest použijeme Dijkstrův algoritmus (viz kapitola v Kuchařce KSP: https://ksp.mff.cuni.cz/kucharky/halda-a-cesty/), který nám dokáže zjistit délky nejkratších cest z jednoho vrcholu do všech ostatních v čase O(m·log(n)).
Takové řešení by však rozhodně neseběhlo dostatečně rychle, jelikož musíme spustit Dijkstrův algoritmus z každého vrcholu z koňostavem, kterých může být až n. Všimněme si ale, že pro každý koňostav nás zajímá pouze nejkratší cesta na radnici. A tedy místo toho, abychom spouštěli Dijsktrův algoritmus z každého vrcholu s koňostavem, ho můžeme spustit z vrcholu s radnicí a zaznamenat si všechny nejkratší cesty do vrcholů s koňostavy. Tím již dostaneme časovou složitost O(m·log(n)) a kýžených pět bodů.
Nyní už je možné, že v optimálním řešení bude potřeba několikrát změnit dopravní prostředek. Máme ovšem slíbeno, že míst, kde bude možné dopravní prostředek měnit, bude málo.
Představme si nyní, že máme optimální řešení O. Nejprve si uvědomme, že se v O neopakuje žádný vrchol s koňostavem – délky hran jsou kladná celá čísla, a kdyby se tedy v O dvakrát vyskytl vrchol xi, v němž je koňostav, mohli bychom odebrat celou část cesty mezi těmito dvěma výskyty xi, čímž bychom cestu zkrátili, což je spor s tím, že O je optimální.
Označme Ô posloupnost vrcholů s koňostavy v pořadí, v jakém se vyskytují v O (tedy speciálně Ô začíná vrcholem, kde Norbert bydlí, a končí vrcholem, kde se nachází radnice). Z předchozího odstavce víme, že se v Ô neopakují vrcholy. Navíc v každém vrcholu Ô můžeme libovolně změnit dopravní prostředek. To znamená, že jsou-li vrcholy x1, x2 sousední v Ô, tak mezi nimi jdeme nejkratší možnou cestou při použití pouze jednoho dopravního prostředku.
To vede k řešení se složitostí O(smlog n + s2log s). Označme si jako G graf, který jsme dostali na vstupu. Nejprve si z každého vrcholu x s koňostavem spustíme dvakrát Dijkstrův algoritmus – jednou chodíme pouze pěšky a jednou jezdíme pouze na koni – a pro každý vrchol y s koňostavem si zaznamenáme délku nejkratší cesty mezi x a y (tj. tu kratší z cest pěšky resp. na koni). Nyní si můžeme vytvořit nový pomocný graf Ĝ, jehož vrcholy budou pouze vrcholy s koňostavy, a mezi každé dva vrcholy natáhneme hranu délky odpovídající délce nejkratší cesty v kocourkovském grafu G (nebo žádnou, pokud mezi těmito dvěma vrcholy nevede cesta). To stihneme v čase O(s·m·log(n)) – 2s-krát spustíme Dijkstrův algoritmus, dvakrát pro každý vrchol s koňostavem, konstrukce grafu Ĝ je pak již lineární.
A nyní již jen stačí najít nejkratší cestu mezi Norbertovým domovem a radnicí v grafu Ĝ (což nám opět pomocí Dijkstrova algoritmu zabere O(s2·log(s)) času, jelikož hran v Ĝ může být až s2). Tato nalezená cesta jistě odpovídá nějaké cestě s přesedáním v kocourkovském grafu. Naopak, jak jsme si již rozmysleli, optimální řešení O odpovídá nějaké posloupnosti vrcholů s koňostavy, kde se mezi sousedními vrcholy přesunujeme bez změny dopravního prostředku, tedy přesně cestě v grafu Ĝ.
Rádi bychom pustili Dijkstrův algoritmus jen jednou. Ale to jistě nepůjde přímo na graf G, jelikož algoritmus neví, kterou délku hran má používat. Potřeboval by v každém kroku vědět, zda z aktuálního vrcholu má odejít po hranách pěšky, anebo odjet na koni.
A to přesně uděláme. Vytvoříme graf G' tak, že za každý vrchol v ∈ G přidáme do G' jeho dvě kopie, vp a vk, kde vp znamená, že jsme ve vrcholu v pěšky a vk znamená, že tam jsme na koni. Pokud je v G hrana uv, tak do G' umístíme hrany upvp a ukvk, přičemž délka upvp bude rovna délce uv, když se po ní jde pěšky, a délka ukvk bude rovna délce uv na koni.
Navíc ještě musíme nějak v G' zachytit přesedání a to uděláme tak, že pro každý vrchol v ∈ G, v němž je koňostav, přidáme do G' hranu vpvk a dáme jí délku nula.
Každá cesta v G' jednoznačně odpovídá cestě v G s přesedáním a naopak. Ale na G' nyní už můžeme spustit Dijkstrův algoritmus (z libovolné kopie Norbertova domu) a vzdálenost libovolné kopie radnice, kterou nám algoritmus spočítá, bude naše hledaná odpověď.
Zjevně stačí umět určit nejvzdálenější viditelnou věž ve směru k radnici; pro nalezení nejvzdálenější věže v obou směrech níže popsaný algoritmus aplikujeme dvakrát, jednou ve směru k radnici a jednou ve směru od radnice, a z nalezených vzdáleností vezmeme maxima.
Nechť zadané věže mají vzdálenosti od radnice x1, …, xN a výšky v1, …, vN. Nechť Pa je konvexní obal bodů (x1,v1), …, (xa,va) pro nějaké a, a (xb,yb) je soused (xa,va) na horní části hranice Pa. Povšimněme si, že vrcholy všech věží s číslem menším nebo rovným a jsou pod přímkou spojující (xa,va) a (xb,yb), neblokují tedy výhled z věže a na věž b. Ze stejného argumentu také plyne, že věže s číslem menším než b nejsou vidět z věže a, jelikož je blokuje věž b. Proto b je nejvzdálenější věž viditelná z věže a směrem k radnici.
Stačí tedy spočítat konvexní obaly P1, …, PN. Bylo by ovšem zbytečně pomalé počítat každý z těchto obalů zvlášť. Podíváme-li se na známý algoritmus pro určení konvexního obalu (viz například https://ksp.mff.cuni.cz/kucharky/geometrie/), povšimneme si, že ten přidává do konstruovaného konvexního obalu body postupně dle jejich x-ové souřadnice a počítá průběžně konvexní obaly již přidaných bodů, tedy přesně to, co my potřebujeme. Stačí si tedy po každém přidaném bodu zapamatovat, do kterého bodu z něj vede hrana v horní části konvexního obalu (dolní část konvexního obalu samozřejmě vůbec nemusíme počítat). Jelikož algoritmus na nalezení konvexního obalu má (při bodech zadaných v rostoucím pořadí dle x-ové souřadnice) lineární časovou složitost, časová i paměťová složitost výsledného algoritmu je O(N).
a) K ověření, zda je určená množina vrcholů nezávislá, postačí obyčejné prohledání stromu do hloubky. Pokud je vrchol stromu označen, při vstupu do každého jeho syna zkontrolujeme, zda syn není také označen. To jistě zvládneme v lineárním čase s velikostí stromu.
type vrchol = record
stav: 0..3; { Kolikrát jsme ve vrcholu byli }
vybraný: boolean; { Patří do zadané množiny }
ok: boolean; { V kořeni výstup, jinde nevyužito }
end;
var otec_vybraný: boolean;
zatím_ok: boolean;
begin
zatím_ok := true;
repeat
V.stav := V.stav + 1;
case V.stav of
1: if ex_l then begin
otec_vybraný := V.vybraný;
jdi_l;
if V.vybraný and otec_vybraný then zatím_ok := false;
end;
2: if ex_p then begin
otec_vybraný := V.vybraný;
jdi_p;
if V.vybraný and otec_vybraný then zatím_ok := false;
end;
3: if ex_o then jdi_o
else begin
V.ok := zatím_ok;
halt;
end;
end;
until false;
end.
b) Nejprve „vytáhneme králíka z klobouku“ a předvedeme jednoduchý
algoritmus, který najde nezávislou množinu. Později dokážeme, že tato
množina je největší možná.
Strom budeme (jak jinak) prohledávat do hloubky. Kdykoliv budeme opuštět nějaký vrchol, rozhodneme se, zda ho označíme, a tím vložíme do nezávislé množiny. Opouštíme-li list, označíme ho vždy. Opouštíme-li vnitřní vrchol, označíme ho právě tehdy, není-li označený žádný ze synů. Práci si trochu zjednodušíme tím, že při prvním vstupu do vrcholu tento hned označíme, a pokud se do něj vrátíme z označeného syna, značku smažeme. Program vypadá následovně.
type vrchol = record
stav: 0..3; { Kolikrát jsme ve vrcholu byli }
vybraný: boolean; { Patří do vybrané množiny }
end;
var syn_vybraný: boolean;
begin
repeat
V.stav := V.stav + 1;
case V.stav of
1: V.vybraný := true;
if ex_l then jdi_l;
2: if ex_p then jdi_p;
3: if ex_o then begin
syn_vybraný := V.vybraný;
jdi_o;
if syn_vybraný then V.vybraný := false;
end
else halt;
end;
until false;
end.
Algoritmus evidentně doběhne v lineárním čase a vydá nějakou nezávislou množinu. Je to ovšem typický zástupce takzvaných hladových algoritmů – vybírá si vždy lokálně nejvýhodnější volbu a neohlíží se na budoucnost. Takové algoritmy obvykle nenajdou globálně nejlepší řešení. Dokážeme, že zrovna ten náš ho najde.
Nejprve nahlédneme, že bez újmy na obecnosti můžeme do naší nezávislé množiny umístit všechny listy. Platí totiž, že libovolnou největší nezávislou množinu M můžeme předělat na jinou, stejně velkou M', která obsahuje všechny listy. Vskutku: Kdykoli v M chybí nějaký list ℓ, najdeme jeho otce p a podíváme se, zda leží v M. Kdyby neležel, mohli bychom do M přidat ℓ – tím by také vznikla nezávislá množina, takže M nebyla největší. Ve skutečné největší M tedy musí otec p ležet. Tak ho odtud odebereme a místo něj přidáme ℓ. Jak nezávislost, tak velikost množiny jsme zachovali.
Naopak vrcholy, které leží těsně nad listy, do hledané množíny jistě nepatří (jinak by nebyla nezávislá). Pokud nyní jak listy, tak tyto vrcholy odebereme, můžeme ve zbylém grafu (ten se mohl rozpadnout na více stromů) opět hledat největší nezávislou množinu. Nikdy se nám totiž nestane, že bychom vybrali nějakého souseda vrcholu vybraného v prvním kole: všichni takoví sousedé už jsou z grafu odebraní.
Nyní stačí uvědomit, že naše prohledávání do hloubky je s tímto postupem ekvivalentní. Každý list vybere, otce listu jistě nevybere (což je totéž, jako by byl odebraný), vrcholy, pod nimiž jsou jen otcové listů, opět vybere (ty se po prvním odebírání stanou listy) a tak dále.