První série třináctého ročníku KSP

Řešení úloh

13-1-1 Logické výrazy (Zadání)

V zadání této úlohy se vyskytlo několik nejasností:

Pro autorské řešení jsem zvolil zřejmě nejobtížnější variantu – čísla neomezené velikosti a negace všech (∞) bitů (kterážto varianta negace se mi zdála nejlogičtější; její základní vadou je, že negace přirozeného čísla pak není přirozené číslo, nýbrž nějaká (nekonečná) posloupnost nul a jedniček).

Základní myšlenka algoritmu je tato: máme 2 zásobníky - jeden pro operátory, druhý pro čísla. Postupně načítáme jednotlivé tokeny (čísla nebo operátory). Načteme-li číslo, uložíme ho na zásobník čísel. Načteme-li operátor, podíváme se, zda předchozí operátor (uložený na vrcholu zásobníku operátorů) má vyšší prioritu; má-li, vyhodnotíme ho (odebereme ho ze zásobníku operátorů, ze zásobníku čísel odebereme operandy, provedeme příslušnou operaci a výsledek uložíme na zásobník čísel) a zkontrolujeme operátor pod ním. To opakujeme, dokud nenarazíme na operátor s nižší prioritou (nebo dno zásobníku); poté ho uložíme na zásobník operátorů. Při tomto postupu každý operátor vyhodnotíme po vyhodnocení předchozí a následující části výrazu ohraničené operátory nižší priority, což je přesně to, co chceme.

Zbývá ošetřit několik dalších záležitostí:

Tento algoritmus (až na vyhodnocování operací) má lineární časovou i paměťovou složitost, neboť na každý operátor sáhneme právě dvakrát – jednou při jeho vkládání do zásobníku, jednou při jeho vyhodnocování.

Nyní k samotné realizaci operací. Základním problémem je negace, kterou nechceme vyhodnocovat pokaždé znova (jinak bychom na výrazu typu !!!…111… nabrali kvadratickou časovou složitost). Proto si u čísla budeme pamatovat, je-li znegováno. Je nyní ovšem nutno dávat trochu pozor při implementaci zbytku operací. Jak po chvíli uvažování nahlédneme (detaily viz program), všechny ostatní operace lze provést v čase lineárním k délce kratšího z nich. Vzhledem k  tomu, že kratší z operandů vždy po provedení operace zahodíme a výsledek ukládáme na místo, kde byl delší z nich, čas potřebný k provedení jedné operace je úměrný délce, o kterou se zkrátí součet délek všech operandů, tj. dohromady přes všechny operace nemůže být delší než O(N). Tedy algoritmus má časovou i paměťovou složitost lineární.

Ještě poznámku k chybě, která se vyskytla v mnoha řešeních: většina operací s řetězci má časovou složitost úměrnou délce řetězců v ní užitých (to, že string v Pascalu vypadá stejně jako ostatní jednoduché typy, na tom nic nemění). Tedy např. cyklus tvaru

var a,b:string;
for i:=length(a)+1 to length(b) do
   a:='0'+a;
má časovou složitost O((rozdíl délek a a b)×(délka b)), tedy až kvadratickou!

Program

Zdeněk Dvořák

13-1-2 Centrum (Zadání)

Sotvaže se po království roznesl problém, kam umístit ředitelství drah, rozpadla se tamější společnost na dvě nestejnoměrně velké části. Ta větší navrhovala předefinovat polohu centra a přesunout ředitelství spolu s menedžmentem někam opodál, nejlépe na jiný kontinent, přičemž své návrhy doplňovala kupou vylepšovacích nápadů, jimiž se k mé převeliké lítosti nebudeme dále zabývat. Ta menší část se k problému postavila přeci jen realističtěji a počala se zabývat pouze vylepšovacími návrhy na naložení s ředitelstvím (ocet?). Nemohu smlčet, že se objevila i mikroskopická skupinka lidí, jež se začali problémem seriózněji zabývat.

Jedni (šťastnější) se snažili v grafu hledat nejdelší cestu, v jejímž středu nalezli hledané centrum (zdůvodni!) – byli-li to navíc staří kmeti, uchovávající paměť rodu, vzpomněli, že se kdes řešila obdobná úloha (12-1-2) a lineární čas jim zpravidla neutekl. V jiných se pro změnu přihlásil o slovo pravěký instinkt sběračů plodin a začali ze stromu v postupných vlnách odtrhávat listy až zbyly poslední dva (či jeden) vrcholy, které mohou být oba centrem grafu. Zbyla ještě nepočetná skupina šťastlivců, hledajících nejhlubší podstromy našeho stromu.

Následují méně šťastní – ti si např. nevšimli, že náš graf je strom (též zdroj mnoha chyb v odhadech časových složitostí) a bez skrupulí zavedli matici sousednosti, nedbajíce při tom nárůstu na minimálně kvadratickou složitost. O nic lépe nedopadli ani oddaní fandové Dijkstry, kteří v každém městě posílali poslíčky, by zjistili nejvzdálenější města, a tak grafem pobíhalo křížem a krážem stádo poslů, aby zjistili vzdálenost, kterou již před nimi desetkrát zjistil někdo jiný…

Ačkolivěk nejsem vegetariánem, přidám se dnes na stranu požíračů listoví. Nejprve několik pozorování: Náš graf o n vrcholech je strom. Pro n≥ 3 centrum zřejmě není listem. Dále – odtrhnutím všech listů se nemění poloha centra (vzhledem k tomu, že max. cesty (rozuměj takové, jež nelze prodloužit) musí končit v listech, všechny se zmenší o 1 a nerovnosti zůstanou zachovány). A konečně – pro n≤ 2 je centrum libovolný vrchol a protože pro n≥ 3 existuje vždy vrchol stromu, který není listem, vždy nám alespoň jeden vrchol zbyde.

Z toho plyne algoritmus: Odtrhnu všechny listy. Jedná se o strom, tedy vzniknou nové listy. Opakuji do okamžiku n≤ 2, kdy je nalezení centra triviální.

Implementace: Fronta, do které si postupně ukládám listí určené k utrhnutí. Při každém utržení vkládám do fronty nově vzniklé listy. (Rozmysli, proč nelze použít zásobník!)

Čas: Na každý vrchol sáhnu jednou O(n) a u každého vrcholu hledám sousedy – stromeček má v celém grafu lineární počet sousedů, tedy O(n)+O(n) = O(n). V každém kroku odstraním jeden lístek, takže je patrná i konečnost.

Paměťová složitost je O(n) (je sice pravda, že v programu můžete vidět pole se sousedy velikosti O(n2), ale z něj se využívá pouze O(n) prvků a nebyl by nejmenší problém toto pole upravit na n spojových seznamů sousedů, které by skutečně využívaly pouze paměti O(n)).

Program

Pavel Šanda

13-1-3 Stabilní úsek (Zadání)

Většina z vás by asi strýčka Skrblíka potěšila fungujícím programem, který by mu zřejmě pomohl k ještě většímu jmění. Někdy by se ale dlooouho načekal…Až na pár světlých výjimek poslali všichni více či méně elegantní řešení pracující s kvadratickou časovou a lineární paměťovou složitostí. Ta trocha ostatních úlohu vyřešila buď v čase O(N log N) a pamětí O(N), nebo v čase O(ND) a pamětí O(D). Posledně jmenovaní dostali nejvíce bodů. Pochvalu si zaslouží Peter Krčah za nejelegantnější řešení v O(N2), které bylo asi na 20 řádků podobně jako řešení Petera Belly v O(ND). My zde ukážeme algoritmus s časovou složitostí O(N log D) a paměťovou O(D). Ukážeme také, že si nepotřebujeme pamatovat celou posloupnost najednou v paměti. A jak tedy na to? Budeme se postupně ptát na členy posloupnosti a po načtení k-tého členu budeme schopni určit nejdelší stabilní úsek končící právě v k-tém členu. Takto snadno nalezneme i nejdelší stabilní úsek v celé posloupnosti. Všichni jste si správně uvědomili, že nějaká posloupnost celých čísel je stabilní, právě když je rozdíl maxima a minima ze členů této posloupnosti menší nebo roven D. Teď již k vlastnímu algoritmu. Předpokládejme, že známe nejdelší stabilní úsek končící k-tým členem dané posloupnosti. Začátek tohoto úseku si označme s. Nyní obdržíme další člen x a chceme určit nejdelší stabilní úsek v posloupnosti končící členem s indexem k+1, tj. aktualizovat s tak, aby úsek as …ak+1 byl stabilní. Pro k si ještě pamatujeme dvě hodnoty a a b – minimum a maximum z hodnot prvků nejdelšího stabilního úseku končícího členem ak. Zřejmě platí, že rozdíl čísel b a a je menší nebo roven D. Také si v nějaké prozatím blíže nespecifikované datové struktuře, označme ji T, pamatujme všechny různé hodnoty, které se v tomto stabilním úseku vyskytly, a u každé této hodnoty si ještě budeme pamatovat pozici jejího posledního výskytu. Uvědomme si, že počet prvků struktury T nepřekročí D+1. Prvky struktury T si také ještě pamatujme v nějakém seznamu (v programu je pro jednoduchost použit spojový seznam), jehož prvky jsou seřazeny podle indexu v posloupnosti. Každý prvek z T bude v dvojici s právě jedním prvkem ze seznamu (odborně se tomu říká bijekce). Proč seznam, ukážeme dále.

A jak teď toto množství informace aktualizujeme? Rozlišme tři případy:

  1. a ≤ x ≤ b – vše je v pořádku. Číslo x můžeme s klidným srdcem přidat do zatím nalezeného stabilního úseku, aniž bychom jeho stabilitu narušili. Hodnoty proměnných a, b, s se nemění.
  2. x<a – v tomto případě již musíme býti obezřetnější. Může se totiž stát, že přidáním prvku x můžeme stabilitu prozatím nalezeného úseku končícího na pozici k narušit (víme totiž, že b-a může být až D). Nově tvořený stabilní úsek nemůže obsahovat prvky s hodnotami, které jsou větší než x+D. Všechny takové prvky proto z T vyhodíme a podle toho samozřejmě upravíme i počátek nového úseku (proměnná s). Musíme také zrušit všechny prvky, které se v posloupnosti vyskytly dříve než nějaký právě zrušený prvek s největším indexem. Tyto prvky by sice svojí hodnotou obstát mohly, ale stabilní úsek musí být souvislý. S tímto úkolem nám pomůže právě již zmíněný seznam. Jednoduše sekvenčně smažeme všechny starší prvky, které se do této doby vyskytovaly v T. A kde bude počátek nového úseku? Inu, ten bude bezprostředně za zrušeným prvkem s největším indexem. Nakonec položíme a:=x a do b vložíme maximum z hodnot prvků posloupnosti tvořící nový stabilní úsek (tedy maximum z prvků struktury T). To je vše.
  3. x>a – tento bod je analogický jako bod 2) a snadno si ho rozmyslíte stejně jako korektnost uvedeného postupu.

Nyní, nezávisle na hodnotě, x buď vložíme do T, pokud tam ještě není, nebo pouze aktualizujeme příslušnou hodnotu posledního výskutu x. Teď již jen zbývá popsat datovou strukturu T. Rozumné je T implementovat jako nějaký binární vyhledávací strom, který nám umožní vykonávat operace vložení a vyjmutí prvku stejně jako vyhledání minima resp. maxima v čase úměrném logaritmu počtu prvků struktury T neboli O(log D). Takovou vlastnost mají například AVL stromy, B-stromy a amortizovaně i splay stomy, na kterých se příkladně dá elegantně provést operace zrušení podstromu. Jelikož popisy těchto základních datových struktur včetně jejich implementací najdete v každé slušné učebnici programování a implementace jsou poměrně zdlouhavé (udržování základních vyvažovacích vlastností pomocí rotací apod.), jsou v programu uvedeny jen hlavičky těchto funkcí. Vše ostatní je uvedeno v plném rozsahu.

Jelikož vkládáme a rušíme každý prvek posloupnosti ve stromu T resp. v seznamu nejvýše jednou a obojí je v čase nejvýše O(log D) resp. O(1), je časová složitost popsaného algoritmu opravdu O(N log D). Paměťová složitost je O(D). Nakonec ještě poznamenejme, že se tato úloha dá řešit mnoha jinými algoritmy a jen s použitím statických datových struktur. Kvůli přehlednosti však byla v programu zvolena varianta s dynamickou alokací proměnných. Toť vše.

Program

Jakub Bystroň

13-1-4 Stoky (Zadání)

Myšlenka algoritmu, kterým budeme zadanou úlohu řešit, je jednoduchá – budeme si udržovat množinu I těch sběrných míst, kde by mohl být vývod do čističky, a v každém kroku vyřadíme jedno sběrné místo z množiny I: Zvolíme dvě sběrná místa X a Y z množiny I a zeptáme se, zda teče voda z X do Y – pokud teče, pak X můžeme vyřadit z množiny I, protože určitě není vývodem; pokud neteče, pak naopak můžeme z množiny I vyřadit Y, protože Y nemůže být v tomto případě vývodem. Aby náš algoritmus měl požadovanou konstantní paměťovou složitost, budeme postupovat tak, aby množina I byla vždy nějaký interval, tj. rovnala se všem celým číslům od A do B; v každém kroku se zeptáme, zda teče voda ze sběrného místa A do B a jedno z těchto míst z množiny I vyřadíme, tj. zvětšíme A o 1, pokud voda teče z A do B, nebo zmenšíme B o 1 v opačném případě. Po N-1 dotazech (N je počet sběrných míst), bude množina I jednoprvková a tedy jsme nalezli hledaný vývod z kanalizačního systému. Ve zdrojovém kódu algoritmu v Pascalu si všiměte, že používá pouze dvou proměnných, a to A a B.

Ze zadání úlohy plyne, že vývod ze systému existuje. Kdyby toto nebylo splněno, můžeme spustit náš algoritmus, jako kdybychom tuto skutečnost měli zaručenu, a pro sběrné místo, které náš algoritmus určí jako výtok z celého systému, tuto skutečnost jednoduše pomocí N-1 dotazů ověřit.

Program

Daniel Kráľ

13-1-5 LISP (Zadání)

a) Jelikož náš dialekt Lispu neobsahuje žádné konstrukce pro zápis cyklů, budeme si muset pomoci jinak, a to použitím rekurze. Myšlenka je snadná: minimum z jednoprvkového seznamu je jeho první prvek, minimum z libovolného delšího seznamu je buďto opět jeho první prvek nebo minimum ze zbytku seznamu, podle toho, co je menší (a na tom nic nezmění ani matoucí zadání vyžadující, aby se funkce jmenovala max). A také se snadno naprogramuje:

  (define (max l)
    (if (and (getb l)
             (> (geta l) (max (getb l))))
      (max (getb l))
      (geta l)
    )
  )

Tak s chutí do toho a půl je hotovo (ještě nám přeci zbývá část b) … jenže ouha, to, co jsme právě stvořili, je program z čeledi želvovitých, který už nad krátkým vstupem bude přemýšlet celé věky. Pokud mu totiž zadáte nalézt minimum z klesající posloupnosti délky n, bude minimum z posloupnosti délky n-1 počítat dvakrát, pro každou z nich pak dvakrát z délky n-2 atd., zkrátka a dobře na to celé spotřebuje čas minimálně 2n. Ale stačila by maličkost, a to zapamatovat si někde, kolik vlastně minimum ze zbytku posloupnosti vyšlo, abychom ho v případě, že je menší než první prvek, mohli přímo vrátit jako výsledek a nemuseli ho počítat znovu. K tomu nám pomůže například primitivum let:

  (define (max l)
    (if (getb l)
      (let ((m (max (getb l))))
        (if (< (geta l) m)
          (geta l)
          m
        )
      )
      (geta l)
    )
  )

A nebo bychom si mohli zvlášť nadefinovat minimum ze dvou čísel a poté minimum ze seznamu jako minimum z jeho prvního prvku a minima ze zbytku:

  (define (max2 x y)
    (if (< x y) x y)
  )
  (define (max l)
    (if (getb l)
      (max2 (geta l) (max (getb l)))
      (geta l)
    )
  )

Obě tato řešení mají lineární časovou a paměťovou složitost (každá úroveň rekurze přispěje konstantním časem a konstantní pamětí a zavolá následující úroveň nejvýše jednou). Ještě si ukážeme, jak snadno sestrojit funkci, která přímo počítá minimum ze všech svých parametrů, takže jí nemusíte předávat všechna čísla jako seznam, a navíc dodefinovává minimum z prázdného seznamu jako nil:

  (define (pmax &rest l) (and l (max l)))

Pokud bychom chtěli výpočet maxima naprogramovat rovnou s &rest, musíme si dát pozor na to, jak naši funkci volat rekurzivně, abychom jí opravdu předali seznam parametrů a nikoliv celý seznam jako jeden parametr. K tomu nám pomůže funkce (apply f '(...)) počítající (f ...):

  (define (apply f l) (eval (cons f l)))

(zkonstruuje si seznam odpovídající volání funkce f se správnými parametry a pak jej pomocí eval vyhodnotí). Pak bude naše funkce max vypadat takto:

  (define (pmax a &rest l)
    (if l
      (max2 a (apply 'pmax l))
      a
    )
  )

b) Porovnávání objektů podle struktury je o něco těžší, ale také se dá snadno popsat rekurzívně: dva objekty jsou equal tehdy, jsou-li eq nebo jsou-li oba z nich páry, jejichž první i druhé složky jsou equal. A to ověříme například následující funkcí:

  (define (equal x y)
    (or (eq x y)
        (and (pair? x)
             (pair? y)
             (equal (geta x) (geta y))
             (equal (getb x) (getb y))
        )
    )
  )

Časová i paměťová složitost jsou opět nejvýše lineární (vzhledem k velikosti porovnávaných objektů včetně všeho, na co se odkazují).

Martin Mareš