Čtvrtá série desátého ročníku KSP

Řešení úloh

• 10-4-1: Wagón klád
• 10-4-2: DĚLITEL
• 10-4-3: Sssssstttttrrrriiinng
• 10-4-4: Duraloví dravci

---

10-4-1 Wagón klád (Zadání)

---

Máme zadanou posloupnost délek klád a₁, a₂, … , a_n a máme vypsat všechny součty a_i+a_j takové, že i≠ j a bez opakování (n je délka posloupnosti). Bereme-li všechny kombinace součtů, zjistíme, že jich je maximálně 1/2·n·(n-1), přičemž některé se mohou opakovat. Nejjednodušší řešení by bylo vytvořit všechny tyto součty, pak je setřídit a vypsat je bez opakujících se součtů. Tento algoritmus by měl časovou složitost O(n²· log n) a paměťovou O(n²). Jelikož ale maximální povolená paměťová složitost je O(n), musíme vymyslet něco jiného.

Abychom se vyhnuli třídění, budeme součty generovat ve vzestupném pořadí. Klády si setřídíme vzestupně, tedy platí a₁≤ a₂≤ … ≤ a_n. To dokážeme při nejhorším v čase O(n²). Nyní si všimněme, že platí:

Takových posloupností máme n (pro každou kládu jednu) a pro každou kládu tvoříme pouze dvojice s kládami s vyšším indexem. A těchto n setřiděných posloupností nyní chceme sloučit do jedné velké, též setříděné posloupnosti – to provedeme následujícím postupem: U každé takové i-té posloupnosti

si budeme pamatovat index j_i, tj. první index, pro který součet a_i+a_ji nebyl ještě zpracován. Na začátku je pro všechny i-té posloupnosti hodnota indexu j_i=i+1, tj. kláda tvoří dvojici s následující kládou. V následujících krocích vybereme vždy minimální součet a_i+a_ji (pro všechna i, kde j_i≤ n) a pokud není roven předchozímu zpracovanému součtu, tak jej vypíšeme. Zároveň se posuneme na další člen i-té posloupnosti inkrementací j_i. Takto procházíme součty ve vzestupném pořadí, dokud máme nějaké součty k dispozici (dokud existuje i takové, že j_i≤ n).

Jestliže v každém kroku vybíráme minimum z n součtů s lineární časovou složitostí, dostaneme algoritmus s časovou složitostí O(n³) a paměťovou O(n). Toto lze ale ještě zlepšit, zkonstruujeme-li si pro vyhledávání minima haldu. Pak jsme schopni určit minimum z n prvků v konstantním čase a náhradu za právě odebraný prvek zatřídíme do haldy v čase O(log n), takže celková časová složitost se zlepší na O(n²· log n). Protože haldu z vás většina zná, nebudu jí ani operace na ní zde popisovat. Pro ty, kteří se s touto datovou strukturou nesetkali, doporučuji jednu z nejznámějších knih o algoritmech – Algorithms and Data Structures od Niklause Wirtha (slovenský předklad Algoritmy a štruktúry údajov).

K výpisu programu stojí snad jen za zmínku to, že pokud nějaká posloupnost skončí a nemůže dát další součet do haldy, vloží se tam fiktivní součet (větší než dosažitelný) a pokud je celá halda plná těchto součtů, tedy i ve vrcholu je fiktivní prvek, víme, že všechny posloupnosti poskytly již všechny své prvky a skončíme.

Program

Aleš Přívětivý

---

10-4-2 DĚLITEL (Zadání)

---

Většina z vás nevyužila nápovědu v zadání a aplikovala obyčejný Euklidův algoritmus s odčítáním, dosáhnuvši tím časové složitosti typu O((m+n)· log(m+n)). Cílem tohoto spisku je ukázat, že dělitele lze počítat daleko rychleji – konkrétně v čase O(log ²(m+n)). Tedy nejdříve stručně, jak na to:

1. Dokud jsou m i n sudá čísla, dělím obě dvěma. V proměnné k si zapamatuji, kolikrát jsem tak učinil.
2. Pokud m=n, končím a za výsledek prohlásím n·2^k.
3. Pokud je m či n sudé, dělím jej dvěma a jdu na [2].
4. Pokud m<n: n ←n-m, jinak m ←m-n.
5. Jdu na [2].

Ponejprv dokažme, že pokud se tento algoritmus zastaví, je jeho výsledkem největší společný dělitel [m,n] čísel m a n. Vyplývá to přímo z dodané nápovědy: V kroku [1] využíváme pravidla [2·x,2·y]=2·[x,y] (co jsme vydělili, na konci opět vynásobíme), krok [2] je podepřen triviálním faktem [x,x]=x, krok [3] pravidlem "x liché a y sudé ⇒[y,x]=[x,y]=[x,y/2]" a konečně krok [4] je klasické Euklidovo pravidlo [x,y]=[x-y,y]=[x,y-x].

Nyní dokážeme konečnost algoritmu, a to tím, že ověříme, že neučiníme více průchodů cyklem než je dvojnásobek počtu číslic ve dvojkovém zápisu čísel m a n dohromady:

• Pokud je v kroku [2] kterékoliv z čísel m, n sudé, v další iteraci cyklu se toto číslo o bit zkrátí (dělení dvěma v [3]).
• Pokud jsou v kroku [2] obě čísla lichá, jedním průchodem cyklu se jedno z nich stane lichým [4] a dalším se zkrátí [3].

Tudíž na každé zkrácení m či n o bit jsme potřebovali maximálně dva průchody cyklem, z čehož přímo dostávame jak konečnost algoritmu, tak časovou složitost O(log(m+n)·f), kde f říká, jak rychle jsme schopni počítat základní operace jako sčítání, odčítání, porovnávání a dělení dvěma.

A jak toto provést na Turingově stroji? Inu, inspirujeme se v mnohém úlohou 10-2-3:

• Zápis čísel zvolíme opět binární, prokládaný a pakovaný (to jest střídavě číslice z obou čísel počínaje nejnižším řádem a dvojici číslic zakódujeme na pásce jedním symbolem). Použijeme tedy abecedu {0,1,2,3,Λ,†}, kde 0 až 3 jsou číslice, Λ je prázdný symbol (na začátku i na konci vstupu) a † je pomocný symbol.
• Krok [1] provedeme tak, že na počátku výpočtu budeme všechny "dvojnuly" od začátku pásky přepisovat na † a nakonec pojedeme hlavou zpět, přepisujíce † zpět na 0 a zastavíme se o okraj pásky.
• Zjištění sudosti či lichosti čísla je triviální.
• Porovnání dvou čísel na rovnost, případně x<y lze provést v lineárním čase prostým průchodem od nejnižšího řádu k nejvyššímu.
• Odečtení dvou čísel taktéž.
• Vydělení jednoho z čísel dvěma odpovídá jeho posunutí po pásce o jedno políčko, rovněž pak v lineárním čase. (Je pouze nutno si uvědomit, že "proložené" číslice druhého čísla je žádoucí zachovat.)

Již z tohoto popisu plyne, že f=O(log(m+n)), tudíž celková časová složitost stroje je O(log ²(m+n)). Zbývá jen stroj zkonstruovat:

Martin Mareš

---

10-4-3 Sssssstttttrrrriiinng (Zadání)

---

Řešení, jak v řetězci délky n prohodit dva podřetězce (i,j) a (r,s) za podmínky 1≤ i≤ j<r≤ s≤ n v lineárním čase, je mnoho, proto zde uvedu jen to, které pokládám za nejelegantnější. Definujme rotaci řetězce kolem osy jako zobrazení, které z prvního písmene řetězce udělá poslední, z druhého předposlední … a z posledního písmene první. Každého uřčitě hned napadne algoritmus na rotaci řetězce kolem osy tak, aby pracoval korektně, v lineárním čase vzhledem k délce řetězce a potřeboval navíc pouze jednu proměnnou, potřebnou k výměně znaku. Nyní se podívejme, co se stane, když v zadaném řetězci rotujeme podřetězec (i,s) – tj. podřetězec obsahující oba podřetězce (i,j) a (r,s) a část mezi nimi. A ejhle, podřetězce se vyměnily a prostředek zůstal mezi nimi, tedy jsou na požadovaném místě, až na jedinou chybičku, a to, že oba podřetězce i prostředek mezi nimi jsou převráceny. To ale vyřešíme třemi rotacemi příslušných podřetězců … a máme výsledek. Protože se algoritmus skládá ze čtyřnásobného použití rotace (o které víme, že má lineární časové a konstantní paměťové nároky), je celková časová složitost algoritmu lineární, tj. O(s-i) a paměťová bez zpracovávaného řetězce konstantní, O(1). Algoritmus je tak triviální, že správnost a konečnost je ihned viditelná.

Program

Aleš Přívětivý

---

10-4-4 Duraloví dravci (Zadání)

---

Hledání cesty v grafu. Hmm, to zavání Dijkstrovým algoritmem… Ale zase tak jednoduché to nebude. Protože přesuny mezi letišti ve městě také něco stojí, budeme muset graf rozšířit. Konkrétně každé město rozdělíme na s vrcholů, každý odpovídá jednomu letišti. (Pro teď si představujme, že každá společnost má vlastní letiště.) Mezi letišti nataháme hrany, jejichž ceny budou odpovídat cenám za přeložení nákladu.

Tohle sice vypadá hezky, ale má to jednu nepříjemnou vlastnost: nefunguje to. V našem státě totiž bují byrokracie, a tak nám nikdo nezaručuje, že přeložení nákladu od společnosti 1 ke společnosti 2 nebude dražší než přeložení nákladu 1→3, 3→2. Zato si můžeme být jisti, že přeložení nákladu přes třetí společnost bude nezákonné.

Takže si každé letiště rozdělíme na příletovou a odletovou část. Nikdy nebude existovat hrana mezi odletovou a příletovou částí, zato však vždy bude existovat hrana příletová → odletová část stejné společnosti (překládat nemusíme) a bude mít cenu 0. To by mělo učinit byrokracii za dost.

K programu: Údaje budeme ukládat do trojrozměrných polí: V 1. rozměru bude město, ve 2. společnost (takže 1. a 2. rozměr dohromady určují letiště) a 3. rozměr bude část (0=příletová, 1=odletová), takže všechny 3 rozměry udávájí přesně jednu část letiště.

Všechno ostatní už je standardní Dijkstrův algoritmus. Vzhledem k tomu, že je to jeden z nejběžnějších algoritmů na hledání nejkratších cest v grafech (i v KSP se již vyskytl mnohokráte, viz např. úloha 8-5-4), nebudeme jej zde podrobně odvozovat a uvedeme pouze základní ideu: U každého vrcholu v grafu si pamatujeme vzdálenost d_v plus informaci o tom, zda je to vzdálenost finální či přechodná. Na počátku nastavíme d počátečního vrcholu na finální nulu a ostatních na přechodné +∞. V každém kroku vybereme vrchol w s nejmenší přechodnou vzdáleností, tu prohlásíme za finální a aktualizujeme přechodné vzdálenosti podle hran vedoucích z w (to jest pokud se někam umíme dostat přes w kratší cestou než jsme dokázali dříve, poznamenáme si tuto cestu namísto původní).

Bohužel, výpočetní složitost Dijkstrova algoritmu je výrazně ovlivněna datovou strukturou, jíž používáme na ukládání přechodných vzdáleností a hledání minim. Optimální výsledky lze dosáhnout s použitím Fibonacciho haldy (vyhledání i aktualizace v čase O(log k), viz úloha 8-5-4), leč její implementace je velice složitá, takže se spokojíme s obyčejným lineárním vyhledáváním v poli (O(k)), což nám dá celkovou časovou složitost O(n² s²) (n je počet měst, s počet společností) a paměťovou O(n²s+ns²).

Program

Pavel Machek

Menu