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

Řešení úloh

13-5-1 Bláznivé hodiny (Zadání)

Řešitelé této úlohy se rozdělili na tři kategorie. První a bezkonkurečně největší byla kategorie simulantů. Její příslušníci se rozhodli hodiny prostě simulovat, což je sice funkční leč značně pomalý (jak si také někteří uvědomovali) přístup. Tomu odpovídalo i bodové hodnocení těchto řešení. Druhá kategorie věštců obsahovala pouze Lukáše Turka, který rychlé řešení uhodl, nicméně již nebyl schopen ho dokázat. Třetí kategorie pamětníků obsahovala dva řešitele, kteří si vzpomněli, že tato úloha již byla kdysi uvedena ve slovenském KSP. Tito řešitelé dodali optimální řešení.

A nyní k samotnému řešení. Budeme postupně počítat tiky způsobené kuličkami s číslem větším nebo rovným i. Pro i = n (n je celkový počet kuliček) je zřejmě poček tiků ti = 0. Když máme počet tiků spočítaný pro i, můžeme ho spočítat pro i-1 podle následující úvahy: Na počátku je pořadí kuliček … , i-1, i, i+1, i+2, … . Když se i-1 dostane na první pozici a přesouvá se dozadu, tak přeskočí všechny kuličky s čísly 3… i-2 (ty se totiž mohou vyskytovat pouze na pozicích 1…i-1). Protože kuliček s těmito čísly je pouze i-4, přeskočí ještě další tři kuličky s čísly vyššími než i-1. Protože každá kulička s číslem větším než i-1 přeskočí při přesunu dozadu kuličku s číslem i-1, dostane se tato kulička na počátek vždy po třech „počítaných“ ticích. Tedy počet tiků způsobených kuličkami s čísly většími nebo rovnými i-1 je ti-1=⌊ti/3⌋+ 1. Celkový počet tiků je zřejmě t3. Sestavit algoritmus využívající výše uvedeného vzorce je již triviální záležitostí.

Správnost algoritmu byla ukázána v popisu, algoritmus bude mít časovou složitost O(n) a paměťovou O(1).

Poznámka pro zvídavé: Výše uvedená tvrzení o složitosti nejsou úplně přesná. Jak si totiž snadno spočtete, hodnota výsledku roste exponenciálně k n (řádově jako (4/3)n). Proto pro velká n již není zcela přijatelná představa, že všechny operace probíhají v konstantním čase a potřebují konstantní paměť – skutečný počet potřebných bitů bude řádově lineární k n a třeba čas na jedno sčítání bude přinejlepším O(n). Celkově tedy složitost pro náš algoritmus v případě času vyjde O(n2) a v případě paměti O(n). Takovéto detailní úvahy o složitosti po vás samozřejmě ve většině úloh nechceme, spíše je zde uvádíme jako ukázku toho, že ne vždy je u složitosti vše tak zřejmé, jak to na první pohled vypadá…

Program

Jan Kára

13-5-2 Holiči (Zadání)

Naše řešení bude mít dvě části: V první prozkoumáme, kteří trpaslíci určitě nemohou a kteří naopak musí navštívit stejného holiče, ve druhé pak zkonstrujeme optimální rozdělení trpaslíků. Téměř všechna řešení, která jsme obdrželi, se skládala z těchto dvou částí – první z nich nečinila nikomu větší problémy, naopak druhou správně vyřešil jen málokdo. Naše řešení by mělo být pochopitelné i bez znalosti teorie grafů, nicméně pro ty sečtělejší z vás, bude řeč teorie grafů na několika místech zmíněna. Trpaslíky lze totiž reprezentovat vrcholy grafu, přičemž dva vrcholy budou spojeny hranou, pokud se tito dva trpaslíci nesnášejí. My pak chceme nalézt nezávislé množiny vrcholů A a B, tak aby se velikosti A a B lišily co nejméně.

Na chvíli si představme, že trpaslík s číslem 1 půjde k prvnímu holiči. Potom všichni trpaslíci, se kterými se nesnáší musí jít k druhému holiči, všichni trplaslíci, kteří nesnášejí některého z trpaslíků, co musí jít k druhému holiči, musí jít k prvnímu holiči atd. Náš program tedy pošle prvního trpaslíka k prvnímu holiči, ty se kterými se nesnáší k druhému atd. Pokud nastane situace, že některý trpaslík nemůže jít k ani jednomu z holičů, pak trpaslíky zřejmě nelze k holičům rozdělit. V opačném případě, jsme mohli zjistit, že k trpaslíků musí jít k prvnímu holičí, l k druhému a zbylí mohou jít k libovolnému z holičů, protože vychází dobře se všemi těmito k+l trpaslíky. Na těchto k+l trpaslíků zapomeneme a vybereme ze zbylých trpaslíků jednoho a zopakujeme stejný postup. Takto získáme několik dvojic skupin trpaslíků o velikostech k1,k2,… a l1,l2,… , přičemž trpaslíci z různých skupin v každé této dvojici musí jít k různým holičům, ale na tom, kterého holiče navštíví trpaslíci ze skupin z různých dvojic nezáleží. V řeči teorii grafů: Rozložíme graf na komponenty souvislosti, zkontrolujeme, že všechny tyto komponenty tvoří bipartitní graf, a nalezneme jejich partity.

Nyní zbývá rozřadit trpaslíky v jednotlivých skupinách k holičům. K tomu použijeme metodu zvanou dynamické programování. Deficitem budeme nazývat rozdíl počtu trpaslíků přiřazených prvnímu a druhému holiči. Pro každé i od 0 do počtu dvojic skupin, si spočítáme jakých všech různých deficitů lze dosáhnout (rozdělením prvních i dvojic skupin trpaslíků mezi holiče) za předpokladu, že trpaslíci od (i+1)-ní dvojice dále jsou rozděleni mezi holiče tak, že trpaslíci z první skupiny z dvojice jdou k prvnímu holiči a trpaslíci z druhé skupiny z dvojice jdou k druhému holiči. Hodnoty si budeme udržovat v poli velikosti N (N je počet trpaslíků) – vždy si budeme pamatovat, zda lze daného deficitu dosáhnout a v kladném případě která dvojice skupin je poslední invertována (tj. trpaslíci z první skupiny jdou k druhému holiči a naopak). Pro i=0 je inicializace pole triviální. V i-té iteraci pole projdeme a ke všem hodnotám, které obsahuje přičteme dvojnásobek rozdílu počtu trpaslíků v druhé a první skupině z i-té dvojice – tak získáme nový možný deficit a pokud již není v poli uložen, tak ho tam uložíme.

Správnost algoritmu je zřejmá z popisu. Program je pouhým přepisem výše popsaného postupu. Časová složitost algoritmu je O(N2) a paměťová je O(N+M), kde N je počet trpaslíků a M je počet dvojic nesnášejících se trpaslíků. Paměťovou složitost by bylo možné zlepšit na O(N) lepší implementací první části algoritmu (vstup bychom zpracovávali rovnou při načítání), nicméně toto zlepšení zde nebudeme popisovat.

Program

Dan Kráľ

13-5-3 Optimální strom (Zadání)

Většina z vás tento problém řešila pomocí jednoduchého algoritmu používajícího haldu. Ten má ale složitost O(N log N) a naši úlohu šlo řešit i lépe. Optimálních řešení bylo opravdu pomálu (přesněji dvě) a to s časovou složitostí O(N).

A teď již k popisu algoritmu. Na vstupu podle zadání dostaneme setříděnou posloupnost délek. V každém kroku se rozhodneme sloučit dvě nejkratší posloupnosti. Jejich délky tedy můžeme z posloupnosti vyřadit a místo nich do posloupnosti vložit součet jejich délek. Abychom mohli rychle nacházet nejmenší délky, potřebujeme posloupnost udržovat setříděnou. Na to použijeme drobný trik – přidáme si pomocnou frontu, do které budeme vždy na konec ukládat právě vzniklé součty. Tato fronta bude vždy utříděna, protože minulé součty které do této fronty byly již přidány byly součty dvou v té době nejmenších čísel, a tedy i jejich součet bude nejmenší. Když pak hledáme dvě nejmenší čísla z posloupnosti, tak budeme hledat jak v číslech z původní posloupnosti, tak v nově vytvořené frontě součtů. A to je vše. Algoritmus má časovou i paměťovou složitost O(N).

Nyní ještě důkaz správnosti algoritmu. Postup slévání si můžeme představit jako binární zakořeněný strom. V jeho listech budou délky vstupních posloupností, u vnitřního vrcholu bude délka posloupnosti vzniklé slitím dvou posloupností odpovídajících synům vrcholu. Pokud máme vstupní posloupnost délky d v n-té hladině, potom nám tato posloupnost přidá do celkového počtu porovnání n·d. Nadále zkoumejme strom s nejmenším počtem porování. V nejhlubší hladině určitě musí mít slity dvě nejkratší posloupnosti (a ty mi přesně navrhujeme slévat nejdříve), protože pokud bychom se na počátku rozhodli sloučit jiné než dvě nejkratší posloupnosti, byla by v nejhlubší (n-té) hladině posloupnost s délkou větší než d a jak si snadno spočtete, celkový počet porovnání by se zvýšil. V dalších krocích pak jsme vlastně v přesně stejné situaci jako v prvním kroku – stačí když zapomeneme na listy odpovídající sloučeným posloupnostem. Tím je správnost tohoto algoritmu dokázána.

Program

Tomáš Vyskočil

13-5-4 Generátor (Zadání)

Úloha byla jednoduchá a většina z vás si s ní hravě poradila. Stačí si uvědomit fakt, že pokud se nějaké číslo v posloupnosti vyskytuje alespoň dvakrát, pak se v ní vyskytuje alespoň dvakrát i poslední číslo AN. Nechť Ai je první takové číslo, které se v posloupnosti vyskytuje vícekrát a Ai+k je jeho druhý výskyt. Pak zřejmě platí i Ai = Ai+k = Ai+2k = ... , a tedy i pro j ≥ i plati Aj = Aj+k = Aj+2k = ... . Položme j = N - k, vzhledem k i + k ≤ N platí j ≥ i, a tedy AN-k = AN.

Nyní už je algoritmus nasnadě. Zjistíme si AN, a pak porovnáním s prvky A1, ... AN-1 zjistíme, zda se s některým z těchto čísel neshoduje. Pokud ano, generátor je vadný, pokud ne, generátor je v pořádku. To vše zvládneme otestovat s konstantní paměťovou složitostí (což byla podmínka zadaní), a budeme k tomu potřebovat 2 N - 3 dotazů na následující náhodné číslo. Vzhledem k tomu, že posloupnost si musíme alespoň jednou projít celou, to asymptoticky lépe nejde.

Program

Aleš Přívětivý

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

Tato úloha byla, pravda, poněkud zběsilá, ale nebojte se, řešení nezůstane pozadu. Před startem se raději ještě jednou podívejte do popisu Ksp-Lispu, jak funguje eval a quote a už se držte, jedeme s kopceeeeee!

Každý objekt bude ve skutečnosti jednoduchá speciální forma, která neudělá nic jiného než že zavolá funkci objcall a předá jí jednak, co se přesně má s objektem udělat (to jest jméno metody a seznam všech jejích parametrů) a jednak seznam metod tohoto objektu (unikátní pro každý objekt, bude se totiž při přidávání nových metod modifikovat). Funkce object tedy pouze vytvoří takovou speciální formu a připojí k ní seznam metod, který bude buďto kopií seznamu metod předka, dědíme-li, nebo kopií seznamu systémových metod:

(define (object &rest parent)
  (list
    'special
    '(op &rest args)
    (list 'objcall
          (list quote
            (copy-list
               (if parent
                  ((geta parent) get-attrs)
                  default-attrs)))
          'op
          'args)))
(define (copy-list l)
  (if l
    (cons (geta l) (copy-list (getb l)))
    nil))

Dále si nadefinujeme seznam systémových metod, všechny z nich budou ukazovat na funkce téhož jména s hvězdičkou na začátku:

(set 'default-attrs (list
  (cons 'get-attrs   *get-attrs)
  (cons 'get-method  *get-method)
  (cons 'def-method  *def-method)
  (cons 'def-attr    *def-attr)
))

Pokud chceme zavolat metodu, stačí pomocí get-method vyhledat, která funkce této metodě odpovídá, a zavolat ji s patřičnými parametry; jako první parametr opět předáváme seznam metod našeho objektu.

(define (objcall obj op args)
  (eval
    (cons
      (list quote (*get-method obj op))
      (cons 'obj args))))

Metoda get-attrs je ze všech nejjednodušší: má vrátit seznam všech metod a atributů, a to je přesně její argument:

(define (*get-attrs obj)
   obj)

Metoda get-method vyhledá v seznamu metodu daného jména a vrátí její definici, pokud žádná taková neexistuje, vrátí odkaz na chybovou metodu undefined-method:

(define (*get-method obj op)
  (if obj
    (if (eq (geta (geta obj)) op)
      (getb (geta obj))
      (*get-method (getb obj) op))
    *undefined-method))
(define (*undefined-method obj &rest ignored)
  (print 'Undefined 'method 'called))
Definice nové metody je také poměrně snadná: stačí do seznamu, který jsme dostali jako parametr, připsat novou položku, případně pokud již metoda tohoto jména existovala, tak její položku přepsat. K tomu nám dopomůže, že víme, že seznam je zaručeně neprázdný, protože vždy obsahuje alespoň systémové metody. 
(define (*def-method obj op val)
  (if (eq (geta (geta obj)) op)
    (cons (cons op val) (getb obj))
    (setb obj
      (if (getb obj)
        (*def-method (getb obj) op val)
        (cons (cons op val) nil)))))

A nakonec přidání nového atributu: každý atribut je vlastně také metoda, která si pamatuje nějakou konstantu a pokud je zavolána bez parametru, vrátí tuto konstantu, pokud s parametrem, pak předefinuje sebe sama na verzi s konstantou nahrazenou tímto parametrem (to je jednodušší než definici funkce nějak přetvářet):

(define (*def-attr obj attr val)
  (*def-method obj attr
    (list 'lambda '(obj &rest x)
      (list if 'x
        (list '*def-attr 'obj
            (list quote attr)
            (list geta 'x))
        (list quote val))))
  val)

Tak, a střecha nad náš objektový domeček právě dosedla, ještě pročistit komín a namontovat anténu pro připojení k Internetu :-) Pěkné prázdniny a (see you (+ 1 this-year)).

Martin Mareš