Druhá série patnáctého ročníku KSP

Řešení úloh

15-2-1 Zatížení (Zadání)

Zadání úlohy bylo formulované tak, aby napovědělo, že silniční síť mezi městy bude poměrně hustá a že úředníků je opravdu obrovské množství. Někteří řešitelé zaslali navíc i dobrá řešení jiných případů, za což mají samozřejmě pochvalu.

Jelikož úředníků je tak mnoho, potřebujeme co nejvíce urychlit operaci vyhledání délky nejkratší cesty mezi dvěma městy – vrcholy grafu. Nejlépe v konstatním čase tak, že si na začátku předpočítame do matice nejkratší vzdálenosti z každého města do každého. Budeme pak pro každého úředníka pouze sahat do tabulky a počítat z hodnot průměr. K výpočtu matice nejkratších vzdáleností si představíme neobyčejně elegantní Floyd-Warshallův algoritmus, který by neměl chybět v repertoáru žádného programátora.

Budeme si po řadě pro k,i,j=1,…,n počítat čísla T
k
i,j
, kde T
k
i,j
nadefinujeme jako „délka nejkratší cesty z vrcholu i do j, která používá pouze vrcholy s čísly 1,…,k a i,j“. Na začátku tedy do T
0
i,j
načteme vzdálenosti vrcholů i a j, případně 0 pro i=j a ostatní hodnoty nastavíme na nekonečno. Nechť nadále máme hodnoty Tl pro l<k už spočítané. Když určujeme hodnotu T
k
i,j
, bude jí menší z čísel T
k-1
i,j
a T
k-1
i,k
+ T
k-1
k,j
– tedy délky staré minimální cesty, kde ovšem není povolený vrchol k, a délky cesty procházející z vrcholu i do vrcholu j přes vrchol k. Poslední tabulka Tn tak bude obsahovat nejkratší cesty z každého vrcholu do každého.

Protože se při výpočtu díváme pouze na hodnoty z Tk-1, stačí používat dvě tabulky, Tk-1 a aktuální Tk. Ona ale dokonce stačí tabulka jediná. Podíváme se na předpis

T
k
i,j
= min{T
k-1
i,j
, T
k-1
i,k
+ T
k-1
k,j
}
a uvědomíme si, že nevadí, když je část tabulky už přepsaná novými hodnotami. V prvním případě určitě bude na přepisovaném místě ještě stará hodnota T
k-1
i,j
. V případě druhém pak podle toho, jak jsme si nadefinovali hodnoty T, nutně platí T
k-1
i,k
=T
k
i,k
a T
k-1
k,j
=T
k
k,j
.

Paměťová složitost tak bude kvadratická. Povšimněte si, že na realizaci algoritmu postačí pouhé tři vnořené for-cykly s podmínkou. Algoritmus tedy pracuje v kubickém čase vzhledem k počtu vrcholů. Do konečné časové složitosti musíme ještě započítat dotazy do tabulky (na což mimochodem spousta řešitelů zapomněla) – počet úředníků není konstanta, takže dostaneme čas O(N3+K).

Poznámka pro koumáky: K výpočtu matice vzdáleností se dá také použít obměna Dijkstrova algoritmu, která při každém spuštění najde z jednoho vrcholu délky cest do všech ostatních. Když potom použijeme implementaci Dijkstry s Fibonacciho haldami – ďábelskou datovou strukturou, která algoritmus urychlí na O(N log N +M), dostame celkový čas O(N2 log N +NM +K).

Program

Tomáš Valla

15-2-2 Závorky (Zadání)

Do popisu správného uzávorkování se nám bohužel vloudila chyba (správně mělo na konci být „druhý znak dvojice A se vyskytuje před prvním, nebo za druhým znakem dvojice B.“), ale naštěstí se všichni řešitelé spoléhali na intuitivní představu a téměř nikdo si toho ani nevšiml. Úloha patřila k těm jednodušším, pouze někteří si závorky zcela zbytečně načetli do paměti a pak je sekvenčně četli.

A takto mohlo správné řešení vypadat: Postupně budeme číst závorky. Je-li to levá, přidáme si ji na vrchol zásobníku. Načteme-li ale pravou, spárujeme ji s poslední ještě nespárovanou levoui (ta je na vrcholu zásobníku) a tu ze zásobníku odstraníme. Pak všechny ( mezi touto dvojicí budou mít příslušející ) také mezi nimi (jinak jsme ji měli spárovat s právě spárovanou pravou). Platí-li toto pro všechny dvojice, pak pokud se druhý znak dvojice A vyskytuje za prvním znakem dvojice B, druhý znak B se nutně musí vyskytovat před druhým znakem A. Pokud navíc na konci nezbyde žádná nespárovaná závorka, jedná se o správné uzávorkování.

Pokud nastane případ, že je na vstupu ) a nemáme žádnou nespárovanou levou závorku, pak od tohoto znaku nalevo je více pravých závorek než levých, a proto určitě nemůžeme všechny pravé spárovat a uzávorkování není korektní. Také pokud na konci zbyde nespárovaná (, uzávorkování není korektní. V ostatních případech algoritmus najde správné spárování.

Nám ale stačí rozhodnout, zda správné spárování existuje, takže místo zásobníku použijeme počitadlo nespárovaných (.

Časová složitost je lineární k délce posloupnosti, paměťová konstantní (resp. jak jeden řešitel poznamenal logaritmická – potřebujeme proměnnou dost velkou na to, aby se do ní vešel počet závorek).

Program

Josef Cibulka

15-2-3 Defragmentace (Zadání)

Tak jak se tato úloha řešila? Většina z vás měla řešení funkční, bohužel ne vždy optimální. Hodně z vás zde používalo třídění, které okamžitě zhoršilo časovou složitost na O(M log M) (M je počet bloků) a přitom nebylo třeba.

Jak tedy vlastně měl program vypadat? Nejprve si řekneme základní myšlenku: Jakmile najdeme blok, budeme se ho snažit přesunout hned na správné místo. Pokud je toto místo již obsazeno, tak nejdříve přesuneme ten a tak dále (rekurzivně). Problémy nastanou až pokud se vytvoří cyklus, tedy pokud se na sebe začnou bloky navzájem odkazovat. Tento problém se řeší odsunutím jednoho bloku na volné místo a po přesunutí zbytku cyklu přesunem bloku z volného místa na cílové umístění. A to je celé. A nyní jak to napsat efektivně?

Označme si počet všech použitých bloků (bloků všech souborů dohromady) M. A budeme zde používat pole minimálně velikosti M, které bude na i-té pozici ukazovat, kde má prvek z i-té pozice být. Nejdříve se „zbavíme“ bloků, které jsou uloženy na pozici na disku větší než M. Protože žádný blok nemá skončit na pozici vetší než M, nemůže při přemísťování těchto bloků vzniknout cyklus. Snadno tedy tyto bloky přesuneme na jejich pozice.

V druhém kroku se pokusíme odstranit i zbylé „špatně“ umístěné bloky. Jak tyto bloky poznáme? Opět jednoduše nahlédneme, že pokud je blok špatně umístěn, musí ležet na „cyklu z bloků“ – po přesunech z první části je totiž každý blok oblasti 1…M obsazen (máme M bloků v oblasti velké M). Stačí tedy vždy pro každý špatně umístěný blok projít cyklus, posunout po něm bloky (k tomu potřebujeme jeden volný blok – použijeme blok M+1, jehož existenci nám zaručuje zadání) a tím je všechny správně umístit.

Tedy dohromady první krok zabere O(M) a druhý krok zabere opět O(M) a tedy celková časová složitost je linearní a paměťová také.

Program

Tomáš Vyskočil

15-2-4 Žabky (Zadání)

Nejprve si rozmysleme, jaký musí být minimální možný počet skoků. Uvažme nějakou pozici žabek na značkách. Dvojici žabek nazveme špatnou, pokud pořadí těchto dvou žabek je opačné než má být ve výsledné pozici. Žabky mohou dělat skoky dvou typů – skoky „ob žabku“ a skoky na sousední políčko. Skok ob žabku mění počet špatných dvojic o jedna (buď zvyšuje nebo snižuje), zatímco skok na sousední políčko na tento počet nemá vliv. Protože v počáteční pozici je n·(n-1)/2 špatných dvojic žabek a v koncové pozici naopak žádné špatné dvojice nejsou, musí žabky provést alespoň n·(n-1)/2 skoků ob žabku.

Nyní odhadneme minimální nutný počet skoků na sousední políčko. Je-li n liché, pak žádné optimální řešení nemůže obsahovat za sebou více než (n-1)/2 skoků ob žabku (nakreslete si obrázek!). Tedy minimální počet skoků na sousední políčko v libovolném optimálním řešení musí být alespoň n·(n-1)/2·(2/(n-1))-1=n-1. Rovnost v posledním případě nastane právě tehdy, když po každých (n-1)/2 skocích z celkových n·(n-1)/2 skoků ob žabku následuje jeden skok na sousední políčko, ale v takovém případě nebude na závěr prázdné místo na jedné z krajních značek, což je v rozporu s požadavky zadání úlohy. Tedy můžeme uzavřít, že celkový počet skoků musí být alespoň n·(n-1)/2+n=n·(n+1)/2 (je-li n liché).

Zbývá nám případ, kdy je n sudé. Podívejme se, jak skoky na sousední políčko rozdělují optimálního řešení na bloky skoků ob žabku. Bloky skoků ob žabku, které jsou liché v pořadí, mohou mít délku nejvýše n/2, a ty, jejichž pořadí je sudé, délku n/2-1. Pokud n≥ 4, pak podobně jako v předchozím odstavci, zjistíme, že počet skoků na sousední políčko musí být alespoň n(n-1)/2·(2/(n-1))-1=n-1. Tento odhad se opět nabývá pouze tehdy, pokud všechny „liché“ bloky mají délku n/2 a „sudé“ bloky délku n/2-1. V takovém případě ale na závěr nebude volná pozice na některé z krajních značek a tedy celkové počet skoků musí být i v tomto případě alespoň n(n+1)/2. Poznamenejme, že ve vyloučeném případu n=2, je optimální počet skoků roven jedné.

Nyní si ukážeme, jak žabky mohou n(n+1)/2 skoky obrátit své pořadí (pokud n≥ 3). Podrobně rozebereme případ, kdy n je sudé, a případ, kdy n je liché jen stručně naznačíme. Nechť n=2k (k≥ 2). Počáteční pozice žabek je následující (* označuje volnou pozici):

1 2 3 4 5 6 ...2k-3 2k-2 2k-1 2k *

Nyní proveďme k skoků ob žabku a na závěr jeden skok na sousední políčko. Nové pořadí žabek tedy bude:

2 * 1 4 3 6 ...2k-5 2k-2 2k-3 2k 2k-1

Nyní proveďme k-1 skoků ob žabku opačným směrem a na závěr opět jeden skok na sousední políčko:

2 4 1 6 3 8 ...2k-5 2k 2k-3 2k-1 *

Žabka s číslem jedna je nyní na pozici, kde původně byla žabka číslo 3. Zopakujeme-li výše uvedený postup ještě jednou, dostane se žabka číslo 1 na pozici, kde byla žabka číslo 5 (po jednom zopakování je na této pozici žabka číslo 3). Po k-1 opakováních výše uvedeného postupu bude žabka s číslem 1 na pozici, kde byla původně žabka číslo 2k. Podobně nahlédneme, že žabka s číslem 3 skončí na značce, kde původně byla žabka číslo 2k-2, žabka s číslem 5 na značce žabky číslo 2k-4, atd. Obecně žabka s číslem i stojí nyní na značce, kde byla žabka číslo n-i+1. Žabky tedy stojí v opačném pořadí, než jaké bylo na začátku. Celkový počet skoků, které provedly, je pak:

k·(k+1+(k-1)+1)=k(2k+1)=
n(n+1)
2

V případě, že n=2k+1 pro k≥ 1, vykonají žabky (k+1)-krát následující schéma skoků

1 2 3 4 5 6 ...2k-3 2k-2 2k-1 2k 2k+1 *
* 1 3 2 5 4 ...2k-3 2k-4 2k-1 2k-2 2k+1 2k

proložené k-krát následujícím schématem:

* 1 3 2 5 4 ...2k-3 2k-4 2k-1 2k-2 2k+1 2k
3 1 5 2 7 4 ...2k-1 2k-4 2k+1 2k-2 2k *

Podobně jako v minulém případě, kdy n bylo sudé, lze nahlédnout, že žabky budou na konci stát na značkách v opačném pořadí. Celkový počet skoků bude:

(k+1)·(k+1) + k·(k+1)=(2k+1)(k+1)=
n(n+1)
2

Program s časovou složitostí O(n2), kde n je počet žabek, pokud vypsání jednoho kroku zabere konstantní čas, je nyní již snadné vytvořit.

Program

Dan Kráľ

15-2-5 Haskell (Zadání)

Nejprve si nadefinujme třídu vypisovatelných typů:

class Printfovatelny x where
  format::x->Char       - - znak ve formatovacim retezci; parametr neni pouzit,
                        - - uvadime ho jen kvuli typove kontrole (parametr x
			- - musi byt v typu kazde tridove funkce, jinak by
			- - se nedalo poznat, kterou instanci pouzit)
  tiskni::x->String     - - prevede x na retezec
 
instance Printfovatelny Int where
  format = const 'd'
  tiskni = show
 
instance Printfovatelny Char where
  format = const 'c'
  tiskni c = [c]

Dále bychom chtěli, aby i String byl Printfovatelny. To má drobný háček v tom, že String není typ, ale pouze zkratka pro [Char], a z technických důvodů pro něj není možné přímo definovat instanci. Musíme proto použít drobný trik:

class Znak x where
  mkChar::x->Char
  unChar::Char->x
 
instance Znak Char where
  mkChar = id
  unChar = id
 
instance (Znak a) => Printfovatelny [a] where
  format = const 's'
  tiskni = map mkChar

Podívejme se na typ požadované funkce printf:

printf "test"               - -  printf :: String->String
printf "cislo %d" (7::Int)  - -  printf :: String->(Int->String)
printf "%s %d" "a" (7::Int) - -  printf :: String->(String->(Int->String))

Tedy chceme, aby typ printfu vypadal takto:

printf :: (Printf x) => String -> x

kde budeme chtít zaručit to, že

Samotná třída Printf vypadá takto:

class Printf x where
  printf':: String->
            - - uz zformatovana cast retezce (v obracenem poradi, od konce k zacatku; String je vlastne spojovy seznam, pridavani na zacate  je mnohem rychlejsi)
	    String->
	    - - zbytek formatovaciho vzoru
	    x
	    - - a parametry
 
instance (Znak a) => Printf [a] where
            - - zadny parametr, pouze vystupni typ = String
  printf' konec fmt = map unChar (reverse konec ++ fmt)
            - - obrat jiz sformatovanou cast a pripoj za ni zbytek
	    - - formatovaciho vzoru (pro uplnou korektnost bychom
	    - - jeste meli testovat, zda neobsahuje dalsi %c, d nebo s)
 
instance (Printfovatelny a,Printf b) => Printf (a->b) where
  printf' konec "" x = error "Prilis mnoho parametru"
                - - dosel nam formatovaci vzor
  printf' konec ('%':c:rest) x =
                - - dorazili jsme k prislusnemu vzoru
    if format x == c
      then printf' (reverse (tiskni x) ++ konec) rest
                - - OK
      else error "Spatny typ"
                - - chyba
  printf' konec (h:t) x = printf' (h:konec) t x
                - - jenom pismeno

a vlastní funkci printf již napíšeme snadno:

printf :: (Printf x) => String -> x
printf fmt = printf' [] fmt

Zdeněk Dvořák