Jako první si předvedeme řešení, jehož časová složitost je O(N2). Pro každé k=1,...,N-1 budeme hledat dvojice hodnot (ck,dk) takových, že mezi městy s čísly 1 až k+1 lze postavit vodovody v ceně dk a zároveň platí:
Dvojici hodnot (ck,dk), která má výše uvedené vlastnosti, nazveme k-přípustnou.
Povšimněme si, že nemusíme hledat všechny přípustné dvojice hodnot. Pokud (ck,1,dk,1) a (ck,2,dk,2) jsou k-přípustné dvojice a platí ck,1≥ck,2 a dk,1≤dk,2, pak v libovolném řešení, kde vodovodní síť mezi městy 1 až k+1 odpovídá dvojici (ck,2,dk,2), lze tuto síť nahradit vodovodní sítí odpovídající dvojici (ck,1,dk,1), aniž by se zvýšila cena vodovodní sítě. Náš program pro každé k=1,...,N-1 nalezne seznam k-přípustných dvojic (ck,1,dk,1),...,(ck,l,dk,l) takový, že pro každou k-přípustnou dvojici (ck,dk) existuje i∈{1,...,l} takové, že ck≤ck,i a dk≥dk,i. Pokud je toto splněno, můžeme předpokládat, že optimální řešení pro propojení měst s čísly 1 až k+1 používá síť vodovodů odpovídající některé dvojici ze seznamu.
Dále můžeme předpokládat, že ck,1<...<ck,l a dk,1<...<dk,l (jinak lze některou z dvojic vynechat, aniž bychom porušili vlastnost uvedenou v minulém odstavci). Tato skutečnost nás vede k tomu, že k-přípustné dvojice budeme mít setříděné dle první (a tedy i druhé) souřadnice.
Nyní popíšeme samotný algoritmus. K určení seznamu 1-přípustných dvojic, rozlišíme dva případy. Pokud a1<0, pak první město musí být napojeno na druhé město a jediná 1-přípustná dvojice je (a1,b1). Pokud a1≥0, pak první město můžeme, ale nemusíme, s druhým městem propojit. Tedy máme dvě 1-přípustné dvojice: (0,0) a (a1,b1).
Předpokládejme, že jsme již nalezli seznam k-přípustných dvojic s výše uvedenými vlastnostmi a tento seznam je (ck,1,dk,1),...,(ck,l,dk,l). Všechny dvojice (ck,i+ak+1,dk,i+bk+1), i=1,...,l, jsou (k+1)-přípustné, neboť odpovídají rozšíření sítě vodovodů mezi městy s čísly 1 až k+1 o vodovod mezi městy s čísly k+1 a k+2. Navíc, pokud i0 je nejmenší index takový, že -ck,i0≤ak+1, pak i dvojice (0,dk,i0) je (k+1)-přípustná. Pokud takový index i0 neexistuje, pak hledaný seznam (k+1)-přípustných dvojic je (ck,1+ak+1,dk,1+bk+1),...,(ck,l+ak+1,dk,l+bk+1). Pokud takový index i0 existuje, pak hledaný seznam (k+1)-přípustných dvojic je tento seznam vzniklý rozšířením o dvojici (0,dk,i0) a vynecháním dvojic (ck,i+ak+1,dk,i+bk+1) s ck,i+ak+1≤0 a dk,i+bk+1>dk,i0).
Nyní předpokládejme, že jsme nalezli seznam (N-1)-přípustných dvojic. Pokud i0 je nejmenší index takový, že -cN-1,i0<aN, pak nejmenší cena vodovodní sítě, která splňuje podmínky zadání, je dN-1,i0 a program tedy vypíše číslo dN-1,i0 na výstup. Vzhledem k omezením na vstup ze zadání víme, že řešení vždy existuje.
Podívejme se blíže na časovou analýzu našeho algoritmu. V každém kroku do seznamu přípustných kroků přidáme nejvýše jednu dvojici a některé dvojice případně vynecháme. Tedy seznam k-přípustných dvojic vždy obsahuje nejvýše k+1 prvků. Při zpracování seznamu musíme ke každé dvojici ze seznamu přičíst hodnoty ak+1 a bk+1 a případně přidat do seznamu jednu dvojici a některé dvojice odebrat. Přímočará implementace tohoto postupu vede k řešení, které vyžaduje čas lineární v délce seznamu v daném kroku, a tedy celková časová složitost našeho řešení je O(N2). Paměťová složitost je O(N).
Pokusme se časovou složitost navrhovaného řešení zlepšit. Vzhledem k tomu, že pracujeme se setříděnými posloupnostmi, ve kterých potřebujeme vyhledávat, přirozeně se nabízí použití binárních vyhledávacích stromů. Problémem je implementace operace simultánního přičtení hodnot ke všem prvkům ve stromě. Za tímto účelem si zavedeme zvláštní proměnnou, která bude určovat, o kolik se hodnoty ve stromě liší od těch, které by tam měly být, tj., hodnoty, které reprezentujeme, jsou hodnoty ve stromě zvýšené o hodnotu uloženou v této zvláštní proměnné. Operaci simultánního přičtení pak snadno implementujeme v konstantním čase změnou hodnoty této speciální proměnné. Hodnoty do stromu pak budeme vkládat snížené o hodnotu uloženou v této zvláštní proměnné.
Jak jsme již uvedli, v kroku algoritmu, kdy vytváříme seznam (k+1)-pří-pust-ných dvojic ze seznamu k-přípustných dvojic, je délka zpracovávaného seznamu nejvýše k+2≤N+1 a v každém z N-1 takových kroků do seznamu přidáme nejvýše jeden prvek. V jednom kroku algoritmu potřebujeme: (1) zvýšit hodnotu všech prvků ve stromě, (2) vyhledat vhodný index i0, (3) pokud takový index existuje, vložit jeden nový prvek do stromu a (4) případně některé prvky odstranit ze stromu. Operace (1), (2) a (3) v jednom kroku algoritmu vyžadují čas O(logN). Operací (4) je za celý běh algoritmu provedeno nejvýše N (ale v jednom kroku jich může být provedeno více) a každá z nich vyžaduje čas O(logN). Celková časová složitost takto implementovaného algoritmu je pak O(NlogN); paměťová složitost je O(N).
Nejjednodušší řešení používá myšlenku slévání: budeme postupně slévat všechny fronty (připomeňme, že jsou setříděné sestupně) do jedné, dokud neodebereme K prvků. V každém kroku vždy zvolíme největší prvek z prvních prvků front. Pokud budeme maximum přes všechny fronty hledat například pomocí haldy, bude celková složitost takového přístupu O(K logN). S tím se ale samozřejmě nespokojíme.
Nechť K-tý největší prvek je x. Zkusme dělat větší kroky: všechny fronty si rozdělme na skupiny nějaké velikosti S≥1 (tuto velikost určíme později) a výše popsaným způsobem odeberme ⌊K/S ⌋ skupin, přičemž skupiny porovnáváme dle velikosti jejich prvního (tedy největšího) prvku. Prvky, které ve frontách zbudou, označíme jako nepoužité. Nyní uvažme první prvek p v poslední odebrané skupině. Zjevně všechny nepoužité prvky jsou menší než p (jinak bychom při odebírání vybrali jinou skupinu). Snadno tedy vidíme, že p je větší nebo roven x, protože počet nepoužitých prvků je alespoň M-K, kde M je celkový počet prvků.
Co můžeme říct o odebraných skupinách? Nechť jsme z nějaké fronty postupně odebrali skupiny s1, ..., st. První prvek skupiny st je větší nebo roven p, proto všechny prvky ve skupinách s1, ..., st-1 jsou větší než prvek x. Skupina st by ale mohla obsahovat prvky menší než x. Do každé fronty tedy vraťme poslední skupinu, kterou jsme z ní odebrali, a ostatní odebrané skupiny prohlasme za zahozené. Je-li počet zahozených skupin z, ve výsledných frontách tedy chceme nalézt (K-zS)-tý největší prvek. Nyní můžeme celý postup opakovat s K := K-zS a s nějakou menší hodnotou kroku S.
V programu tedy nejprve zvolíme S jako největší mocninu dvojky menší než K, provedeme výše popsaný postup, zmenšíme S na polovinu, a toto opakujeme, dokud S≥1. V poslední iteraci, kdy S=1, odebíráme jednotlivé prvky, postupujeme tedy stejně jako v prvním algoritmu. Program tedy vždy skončí a vrátí x.
Zbývá určit jeho složitost. V každé iteraci zahodíme alespoň max(⌊K/S ⌋·S - N·S, 0) prvků, pro aktuální hodnoty K a S, proto prvků větších než x zbude do příští iterace nejvýše (N+1)·S. V následující iteraci tak odebereme maximálně (N+1)·S/(S/2)=2(N+1) skupin (tento odhad platí i pro první iteraci, kde díky volbě počáteční hodnoty S odebereme nejvýše dvě skupiny). Protože odebraní jedné skupiny trvá O(logN) a celkový počet iterací je O(logK), získáváme tak celkovou složitost O(N logK logN).
Na závěr zmiňme, že existuje řešení pracující v čase O(N logK), o kterém se navíc dá dokázat, že je optimální, svou složitostí však přesahuje rámec olympiády.
a) Nejprve si všimneme, že v logaritmickém prostoru dokážeme obejít jeden cyklus a najít jeho nejmenší prvek. Pak už stačí projít všechny prvky permutace a pro každý z nich zjistit, jestli je nejmenším prvkem cyklu, na němž leží. Takto každý cyklus započítáme právě jednou.
var n: integer; { zadaná permutace }
P: array [1..100] of integer;
c: integer; { počet nalezených cyklů }
i, j, m: integer; { pomocné proměnné }
begin
c := 0;
for i := 1 to n do { i = zkoumaný prvek }
begin
j := i; { pomocí j kráčíme po cyklu }
m := i; { m = nejmenší prvek cyklu }
repeat
if j < m then m := j;
j := P[j];
until j = i;
if m = i then c := c+1;
end;
end.
b) Jelikož mezi každými dvěma vrcholy u a v stromu existuje právě jedna cesta (bez opakování vrcholů), stačí zjistit, které hrany na této cestě leží, a spočítat je. Hranu na cestě z u do v přitom poznáme snadno: jejím odstraněním se u a v ocitnou v různých stromech.
Postačí tedy probírat jednu hranu za druhou a pokaždé spustit vzorové řešení úlohy P-II-4b z krajského kola, upravené tak, aby vybranou jednu hranu ignorovalo. K tomu nám jistě postačí logaritmické množství paměti.
Tím je úloha vyřešena. Popíšeme nicméně ještě jeden přístup, který nám dokonce dovolí cestu přímo sestrojit.
Opět vyjdeme z řešení úlohy P-II-4b. Připomeneme si, že jsme v něm postupným „obcházením” hran stromu došli z vrcholu u do vrcholu v. Jinými slovy, sestrojili jsme sled z u do v – tak se říká posloupnosti na sebe navazujících hran, v níž se mohou vrcholy i hrany libovolně opakovat.
Pomocí skládání log-space programů, které jsme odvodili v domácím kole, zkombinujeme funkci generující sled s novou funkcí, která z libovolného sledu z u do v vyrobí cestu z u do v.
Mějme sled u=t1,t2,...,tk=v. Pokud se v něm žádný vrchol neopakuje, neopakují se ani hrany, takže máme cestu. V opačném případě najdeme nějaký vrchol w, který se opakuje. Nechť ti je jeho první výskyt a tj poslední. Potom t1,...,ti-1,tj,...,tk je nějaký kratší sled z u do v (z původního sledu jsme „vystřihli” uzavřený sled z w do w).
Náš algoritmus tedy bude procházet daný sled vrchol po vrcholu, pokaždé ověří, jestli se daný vrchol opakuje, a pokud ano, vystřihne všechny vrcholy od prvního výskytu do posledního. Jelikož vystřižením nemohou přibývat nová opakování, stačí sled projít jednou zleva doprava.
{ Vrátí i-tou hranu sledu nalezeného řešením P-II-4. Za koncem sledu vrací -1. }
function sled(i: integer): integer;
var d: integer; { nalezená vzdálenost }
i, j, k: integer; { pomocné proměnné }
begin
d := 0;
i := 1; { i = pozice ve sledu }
while sled(i) <> -1 do
begin
d := d+1;
j := i; { hledáme další výskyty téhož vrcholu }
k := sled(i); { k = aktuální vrchol }
while sled(j) <> -1 do
begin
if sled(j) = k then
i := j+1;
j := j+1;
end;
end;
writeln(d);
end.