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

Řešení úloh

13-4-1 Fotografové (Zadání)

Již samotné bodové hodnocení této úlohy naznačuje, že tato úloha patří mezi ty obtížnější v našem semináři. Celkem přišlo šest řešení, z nichž pouze dvě obsahovala správný (tedy funkční) polynomiální algoritmus, byť ne s optimální časovou složitostí a navíc bez kompletního důkazu správnosti.

Program řešící tuto úlohu samozřejmě nejprve načte počet domů v Nudlové Lhotě a popis snímků Alfonse a Adalberta. Nejprve si povšiměme, že pokud Adalbert chce mít na svém snímku pouze dva domy, pak je nutné tyto dva domy natřít stejnou barvou. Abychom se takovýchto speciálních případů zbavili, postavíme mezi takové dva domy zídku a spojíme je v jeden (v našem programu to bude odpovídat vhodnému přečíslování domů v Nudlové Lhotě). Tím Adalbert bude spokojený se všemi svými snímky, které původně obsahovaly oba takto spojené domy (a tedy tyto Adalbertovi snímky z dalšího zpracovávání vyřadíme). Pokud se nám stane, že na některém z Alfonsových snímků bude nyní již jen jediný dům (vzniklý z několika původních), pak zřejmě domy v Nudlové Lhotě nelze obarvit dle požadavků obou umělců a náš program o tom vypíše vhodnou zprávu.

Předpokládejme tedy nadále, že každý Adalbertův snímek obsahuje alespoň 3 domy. Domy ve Lhoťě si očíslujeme od jedné podél cesty. Obarvení prvních k domů (tj. těch s čísly 1 až k) nazveme optimální, pokud:

Index poslední dvojice obarvení je největší číslo i takové, že existuje j (i<j≤ k), že domy i a j jsou obarveny stejnou barvou. Pokud jsou všechny domy obarveny různými barvami, je index poslední dvojice roven nule. Označme dále bk počet barev a ik index poslední dvojice optimálního obarvení prvních k domů. Zřejmě platí bk+1≤ bk+1. Uvažujme nějaké optimální obarvení prvních k domů a dále označme x a y barvu (k-1)-ního a k-tého domu podle tohoto obarvení. Potom platí: Právě provedený rozbor případů nám dává návod na konstrukci optimálního obarvení všech domů v Nudlové Lhotě.

Zkusme se nyní zamyslet nad samotnou implementací výše popsaných myšlenek. Náš program se skládá z procedur nacti, spoj a spocitej. První z procedur, nacti, načte počet domů v Nudlové Lhotě a informace o snímcích, které chtějí umělci pořídit. Druhá procedura „staví“ zdi mezi ty dvojice domků, které chce samostatně vyfotografovat Adalbert: Hodnota spojit[i] v poli spojit je true, pokud Adalbert chce pořídit fotografii s domy i-1 a i. Hodnota spojen_na[i] pole spojen_na udává číslo domu s původním číslem i po postavení zídek a spojení domů dohromady. Povšimněte si, jak je v této proceduře vyřešen test, zda došlo ke spojení dvou domů v rámci jedné větší Adalbertovy fotografie či zda došlo ke spojení všech domů z jedné Alfonsově fotografii. Do pole spojeno uloží tato procedura pro každý dům, z kolika původních domů se skládá.

Obraťme nyní naši pozornost k proceduře spocitej. Budeme postupovat dle výše uvedeného postupu a do pole barev budeme ukládat počty barev, které používá optimální obarvení prvních k domů, do pole barva barvu k-tého domu v optimálním obarvení a do pole posledni index poslední dvojice optimálního obarvení. Aby náš algoritmus byl co nejrychlejší, tak si před samotným výpočtem uložíme do pole ruznost, zda Alfons chce pořídit fotografii dané dvojice domů (ruznost[i] je true, pokud Alfons chce vyfotografovat samostatně dvojici domů s čísly i-1 a i). Do pole ruznost ukládáme informace o Adalbertových snímcích; číslo ruznost[i] je rovno největšímu j takovému, že Adalbert chce pořídit snímek pravě domů s čísly j až i.

Časová a paměťová složitost naší implementace popsaného algoritmu je lineární, tedy O(N+M), kde N je počet domů Nudlové Lhoty a M je počet snímků, které chtějí oba umělci pořídit.

Program

Dan Kráľ

13-4-2 Okružní jízda (Zadání)

Na úvod si zopakujeme značení ze zadání: L budiž délka závodní trasy, K počet stanovišť na ní a p1, … , pK vzdálenosti jednotlivých stanovišť od hlavního města ležícího na trati. a1, … , aK pak jsou počty kilometrů, které lze ujet na benzín načerpaný na daném stanovišti.

A nyní již samotné řešení. Předpokládejme na chvíli, že auto může jet na dluh – to znamená, že objem benzínu v nádrži může být dočasně záporný. Uvědomíme-lisi, že množství benzínu rozestavěné podél trati stačí přesně na projetí okruhu, je zřejmé, že auto bude mít jak na startu tak v cíli prázdnou nádrž.

Nechejme auto vyjet z prvního stanoviště. Pro účely snažšího zápisu si přidáme stanoviště K+1 ve vzdálenosti L + p1, které bude v podstatě shodné s prvním stanovištěm, pouze nám umožní vyhnout se rotaci. Označme si bi objem benzínu v okamžiku, kdy auto přijíždí do města i, ještě než natankuje. Je zřejmé, že

bi = (∑
i-1
j=1
ai) - (pi - p1), b1 = bK+1 = 0.
Označme si jako m číslo stanoviště, ve kterém nabývá posloupnost { bi }
l
i=1
minimum. Ukážeme, že toto stanoviště (anebo jakékoliv jiné, ve kterém má bi stejnou hodnotu) je jediné správné startovní stanoviště.

Stačí uvážit, co by se stalo, kdybychom vyjeli z jiného stanoviště. Posloupnost bi by se zrotovala o příslušný počet stanoviště doleva a hodnoty bi by se posunuly tak, že v počátečním stanovišti by byly 0. Pokud se tedy v počátečním stanovišti nenabývalo minimum, bude mít bm hodnotu menší než 0, a tedy autu někde dojde benzín.

Pokud chceme, aby objem benzínu nebyl nikde záporný, musíme tedy startovat ze stanoviště m.

Program je přímou implementací uvedeného postupu. Oproti tomuto textu je zjednodušen ve smyslu, že auto necháváme vyjíždět z nultého kilometru místo prvního stanoviště, což nám objemy benzínu zmenší o konstantu. Jeho časová složitost O(K) je nejlepší možná, protože každý vstup musíme alespoň přečíst, paměťová složitost O(1) také nejde vylepšit.

Program

Robert Špalek

13-4-3 Fazolky (Zadání)

Tato úloha byla dosti jednoduchá, a tak se značné části z vás se podařilo nalézt optimální algoritmus pro tuto úlohu. Algoritmus postupně prochází kalíšky od prvního k poslednímu. Průběžně si udržuje počet fazolek mi, které je nutné přesunout mezi kalíšky i a i+1. Pokud je tento počet kladný, je třeba přesouvat doprava, pokud je počet záporný, je třeba přesouvat doleva. Jak tento počet udržovat? Mezi kalíšky nula (ten vlastně neexistuje) a jedna je to zřejmě nula (tedy m0=0). Mezi kalíšky i a i+1 je to pak mi-1+pi-1, kde pi je počet fazolí v i-tém kalíšku. Tento vztah snadno ověříme:
  • Pokud je mi-1≥ 0, tak bylo do kalíšku i z kalíšku i-1 třeba přesunout mi-1 fazolí. V kalíšku tedy budeme mít mi-1+pi fazolí. Jednu fazoli musíme v kalíšku nechat a zbytek odsunout dále doprava (vlevo již z indukčního předpokladu nemají žádné uplatnění – mi-1 by totiž v tom případě mohlo být menší a nebyl by to tedy nutný počet fazolí).
  • Pokud je mi-1<0, tak bylo z kalíšku i do kalíšku i-1 třeba přesunout -mi-1 fazolí. V kalíšku i již máme pi-1 volných fazolí. Pokud tyto fazole nestačily na pokrytí přesunu, je třeba ještě z kalíšku i+1 do kalíšku i dodat -mi-1-pi+1 fazolí (tedy mi je rovno dokazovanému výrazu). Pokud fazole stačily na pokrytí, tak je jejich zbytek nutno odsunout doprava, a tedy dokazovaný výraz pro mi též platí.
Nyní když máme dokázaný vztah pro nutný počet přesunů mezi kalíšky i a i+1, je již zřejmé, že celkový počet tahů musí být ∑
n-1
i=1
|mi|. Algoritmus tedy pouze průběžně přičítá absolutní hodnoty ze spočteného nutného počtu přesunů k celkovému počtu tahů.

Algoritmus má lineární časovou složitost k počtu kelímků a konstantní paměťovou složitost (nikdy si nepotřebujeme pamatovat více než počet fazolí v aktuálním kelímku, nutný počet přesunů a celkový počet tahů). Správnost algoritmu byla ukázána v popisu.

Program je přímou implementací algoritmu. Za drobnou poznámku snad stojí pouze to, že k celkovému počtu tahů je v programu přičteno i mn. To je ale pro korektní vstup vždy nula, takže nezpůsobí žádnou chybu.

Program

Jan Kára

13-4-4 Vodárna (Zadání)

Naštěstí se po přijetí konečného plánu „Co s tunami (shnilých) malin stávkujících zemědělců“ neozval jekot žádného Ancijáše (kormutlivě poukazuje na nesmyslnost data termínu platnosti) a celá věc se tedy mohla předat skupině odborníků (která spokojeně valíc svoji kuličku poznání, nemá pokdy rozvažovat o  finalitě svého konání), jež se začala problémem obírat.

Jako obvykle existovalo několikero různých variant řešení – mohlo se speciálním způsobem využít barvení grafu (rozuměj obšlehnout loňskou olympiádu), různě komplikované varianty prohledávání do šířky v opačném směru, nežli jsou orientovány hrany, a konečně se nechalo vystačit i s klasickým prohledáváním do šířky – toho se přidržíme i my.

Vezmeme si libovolný bod grafu x a označíme si všechny vrcholy v grafu, do kterých se lze z x dostat (včetně x samotného). Buďto jsou označeny všechny vrcholy grafu (x je pak kandidát na hledaný vrchol), anebo nám zůstal alespoň jeden neoznačený vrchol y – v tom případě zvolíme x = y a jdeme opět od začátku (Nerušíme však předchozí označení u vrcholů!).

Nechť z je poslední zvolený x. Pak pokud má naše úloha řešení, tak z je jedním z nich. Důkaz tohoto tvrzení je jednoduchý: Nechť pro spor nějaký vrchol r je řešením a vrchol z řešením není. Zřejmě ze žádného z předtím volených x nemohla vést cesta do r, protože potom by z x vedla cesta přes r do všech vrcholů a x by bylo řešením. Tedy v okamžiku počátku prohledávání ze z bylo r ještě „netknuté“. Po konci prohledávání už ale byly projité všechny vrcholy. Tedy existovala cesta ze z do r a ze z přes r se šlo dostat všude. Spor.

Stačí tedy po nalezení vrcholu z (1. fáze) zjistit, zda-lise z něj dostanu do všech vrcholů grafu (2. fáze).

Na zjišťování dosažitelnosti vrcholů mi v obou částech algoritmu stačí klasické prohledávání do šířky. Dále si povšimněme, že pokud v 1. fázi hledám dosažitelné vrcholy z x, mohu ignorovat ty větve výpočtu, kde narazím na již označený vrchol (nic nového z toho nevytěžím).

Stran složitostí: Časová složitost je O(m+n), kde n je počet vrcholů a m je počet hran. V 1. fázi z každého vrcholu hledám maximálně jednou (pak je již označen jako prohledaný). Samotné hledání sice nemusí trvat konstatní čas (vzhledem k počtu vrcholů), ale uvědomte si, že všechny vrcholy, které naleznu při hledání, označím a z označených vrcholů již nehledám. Nalezení všech sousedů jednotlivých vrcholů pak v sumě odpovídá počtu hran v celém grafu. Ve 2. fáze je klasický průchod do šířky, tedy opět O(m+n).

Paměťová složitost je O(n2), přičemž by šlo modifikací programu živořiti (z čeho to slovo jen vzniklo?) i na O(m+n). Vzhledem k tomu, že v každém kroku obarvím alespoň jeden vrchol je zřejmá i konečnost.

Program

Pavel Šanda

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

Stejně jako pro úlohu z minulé série, i zde výtečně poslouží prohledávání do šířky, tentokráte ale bude krapet složitější, neboť si budeme muset pamatovat, ve kterých vrcholech jsme již byli, abychom se nezacyklili. Hledání cesty z v do w tedy bude vypadat asi takto:

  1. Fronta Q na začátku obsahuje v, předchůdce pv nastavíme na ∅.
  2. Dokud je Q neprázdná, odeber z ní vrchol x, všechny jeho dosud neoznačené sousedy označ, přidej je na konec fronty a nastav jejich py na x.
  3. Pokud je vrchol w označený, nejkratší cestu nalezneme „přeskákáním“ po px z w zpět do v. V opačném případě neexistuje z v do w žádná cesta.

Takový algoritmus by si jistě zasloužil důkaz správnosti: Algoritmus se určitě zastaví, a to po nejvýše lineárním počtu kroků, protože každý vrchol a každou hranu grafu projde maximálně jednou. Navíc vrcholy prochází v pořadí podle rostoucí vzdálenosti od v: nejdříve vrchol v samotný, pak všechny vrcholy ve vzdálenosti 1, pak všechny ve vzdálenosti 2 atd., přesněji vždy, když z fronty vybírá vrcholy vzdálené k, přidává na její konec vrcholy vzdálené k+1. Přitom px vždy ukazuje na předposlední vrchol na nejkratší cestě z v do x (a z toho přímo plyne, že nalezená cesta je opravdu nejkratší a že pokud nějaká cesta existuje, tak ji nalezneme). To celé snadno dokážeme indukcí: pro počáteční vrchol v tvrzení jistě platí. Víme-li, že platí pro všechny vrcholy ve vzdálenosti <k, podívejme se na situaci v okamžiku, kdy byl do fronty zařazen poslední vrchol vzdálený k-1 (podle indukčního předpokladu byl tento vrchol i všechny vrcholy bližší k v určitě ohodnoceny správně, mají správná px a první vrchol ve vzdálenosti k-1 nebyl dosud z fronty odebrán). Algoritmus nyní přidá do fronty právě vrcholy vzdálené k: cokoliv přidá, je dosud neoznačený soused nějakého vrcholu vzdáleného k-1 (a ten nemůže mít vzdálenosti větší než k, jenže menší také ne, neboť to by byl již označený); naopak každý vrchol vzdálený k přidá, neboť má nějakého souseda vzdáleného k-1 a toho zaručeně máme ve frontě; px přitom vždy nastaví právě na tohoto souseda, což je přesně předchůdce x na nejkratší cestě z v. A tím je celé tvrzení dokázáno. (Mimochodem, celé prohledávání jsme mohli ukončit už v okamžiku, kdy jsme dorazili do w, ostatní hodnoty totiž nalezení nejkratší cesty ani její tvar nemohou ovlivlit. Toho také v našem programu využijeme.)

Stačí již maličkost: naprogramovat náš algoritmus v Ksp-Lispu tak, aby všechny grafové operace i operace s frontou pracovaly v konstantním čase, a tím pádem celý program běžel v čase O(m+n) (lineární v počtu vrcholů a počtu hran grafu).

Frontu reprezentujeme stejně jako v minulé sérii, tj. jako seznam, u nějž si budeme pamatovat místo pro čtení a pro zápis. Značkování a uchovávání px vyřešíme tak, že číslo cx vrcholu x uvedené na začátku seznamu, kterým je vrchol reprezentován, nahradíme u označkovaných vrcholů dvojicí (cx,px), což můžeme snadno rozlišit od původních čísel pomocí pair?. Nesmíme ale zapomenout na konci uvést graf do původního stavu, k tomu nám poslouží zapamatovaný začátek původní fronty – všimněme si, že operace s frontou jsou nedestruktivní, tedy že z ní nikdy prvky neodebíráme, jen si posouváme ukazatel na první nezpracované políčko, takže na konci výpočtu bude seznam reprezentující frontu obsahovat právě všechny označkované vrcholy.

A teď již program:

; Přidá všechny sousedy na seznamu next na konec
; fronty tail, označkuje je, nastaví předchůdce na from
; a vrátí nový konec fronty.

(define (add-neigh tail next from)
   (if next
      (let ((v (geta next)))
         (if (pair? (geta v))
            (add-neigh tail (getb next) from)
            (block
               (setb tail (list v))
               (seta v (cons (geta v) from))
               (add-neigh (getb tail)
                          (getb next)
                          from))))
      tail)
)

; Prohledá graf do šířky: head je začátek fronty,
; tail její konec, target vrchol, na kterém se má
; prohledávání zastavit. Vrátí t nebo nil podle toho,
; zda cesta do target existuje.

(define (bfs tail head target)
   (if head
      (let ((v (geta head)))
         (if (eq v target)
            't
            (bfs (add-neigh tail (getb v) v)
                 (getb head) target)))
      nil)
)

; Rekonstruuje nejkratší cestu z v do w podle zpětných
; ukazatelů pw a přidá na její konec seznam l.

(define (trace-back w l)
   (if w
      (trace-back (getb (geta w))
                  (cons (geta (geta w)) l))
      l)
)

; Odstraní značky ze všech vrcholů ve frontě head.

(define (cleanup head)
   (if head
      (block
         (seta (geta head)
               (geta (geta (geta head))))
         (cleanup (getb head)))
      nil)
)

; Hledání cesty osobně: založí frontu obsahující
; počáteční vrchol, prohledá do šířky, zrekonstruuje
; cestu a vyčistí graf.

(define (path x y)
   (let ((queue (list x))
         (z (seta x (list (geta x))))
         (result (bfs queue queue y))
         (p (if result
               (trace-back y nil)
               nil)))
      (cleanup queue)
      p)
)

Martin Mareš