Čtvrtá série dvanáctého ročníku KSP

Řešení úloh

12-4-1 Magický zapletenec (Zadání)

Na tuto úlohu přišlo překvapivě málo řešení, i když jediná metoda řešení (backtracking) je jinak metodou hojně používanou. Opravovatelům není známé asymptoticky lepší řešení než projít všechny možné množiny vrcholů a otestovat o každé z nich, jestli po rozevření dané množiny kroužků vzniknou samé řetízky a že počet řetízků je menší než počet rozevřených kroužků. Navíc je třeba zvlášt otestovat, že zadání již není kružnice! Náš algoritmus by totiž na nezašmodrchaném řetízku odpověděl 1. Časová složitost bude O(2počet vrcholů).

A teď jak konkrétně budeme backtrackovat:

Program

Pavel Machek

12-4-2 Pyrus Achras (Zadání)

Ze zadání úlohy vyplývá, že se snažíme určit, zda nějaký bod (hruška) leží uvnitř konvexního obalu ostatních bodů (plot). Kdo nyní začal konstruovat konvexní obal, skončil s časovou složitostí alespoň Ω(n log n) (a často i se 3 stránkami programu, které jsem následně musel opravovat…). Nyní jak by mohlo vypadat řešení:

Všimneme si, že bod leží mimo konvexní obal množiny jiných bodů právě tehdy, když existuje úhel menší než 180 stupňů s vrcholem v tomto bodě obsahující všechny body dané množiny. Tento úhel se pokusíme najít.

Do zadaného bodu umístíme počátek soustavy souřadnic. Dále načteme první z bodů množiny. Tento bod nám určí vektor, který jistě leží uvnitř hledaného úhlu. Budeme nyní určovat levou a pravou (vzhledem k tomuto vektoru) hranici úhlu, obsahujícího všechny dosud načtené body. Na počátku jsou obě tyto hranice totožné s vektorem k prvnímu z bodů. Jestliže již máme zpracovánu část vstupu a načteme další bod, rozlišíme 3 případy:

  1. Vektor k načtenému bodu je vlevo od směru k prvnímu bodu. Pak ověříme, zda tento směr je vlevo od levé hranice, a je-li, příslušně ji upravíme.
  2. Vektor k načtenému bodu je vpravo od směru k prvnímu bodu. Řešíme analogicky.
  3. Oba vektory mají stejný směr; mají-li navíc stejnou orientaci, nic neděláme. Mají-li opačnou orientaci, zadaný bod leží na přímce spojující 2 body a tedy i uvnitř konvexního obalu.

Jestliže na konci leží levá hranice vlevo od pravé, máme hledaný úhel. Jinak takový úhel zjevně nemůže existovat (úhly mezi pravou a levou hranicí a mezi hranicemi a vektorem odpovídajícím prvnímu z bodů jsou menší než 180 stupňů, tedy máme-li libovolnou přímku procházející daným bodem, v obou polorovinách jí určených leží alespoň jeden z nich).

Polohu dvou vektorů určíme na základě jejich vektorového součinu (třetí složku doplníme nulovou). To je totiž vektor k nim kolmý takový, že tvoří kladně orientovanou soustavu. Stačí nám tedy spočítat třetí souřadnici tohoto součinu a podívat se na její znaménko.

Konečnost algoritmu je zřejmá (neobsahuje žádné netriviální cykly).

Časová složitost je lineární k počtu stromů, paměťová je konstantní.

Správnost algoritmu není zřejmá z popisu (což se mi bohužel všichni řešitelé, kteří se o něčem takovém jako důkaz zmínili, snažili tvrdit); nicméně uvedené skutečnosti jsou natolik intuitivně zřejmé, že skutečně formální důkaz (který by celou ideu spíše zamlžil) zde neuvedu.

Program

Zdeněk Dvořák

12-4-3 Šachová šlamastika (Zadání)

Pakliže jste měli štěstí, potkali jste na posledním KOSu (Konference odvážných starostů) starostu města Hauntry. Tento starosta byl neobyčejně výřečný a každého volky nevolky seznamoval s jeho vynikajícími výsledky v oblasti vyhledávání strašidelných domů. Ve zkrácené verzi problém spočíval v nalezení největšího možného bloku domů, jež oblažují svojí přítomností strašidla (kdo koho?). Asi vás již napadlo optimální řešení zadaného problému – použijeme dva zásadní triky. Jednak převedeme naši úlohu na známou strašidelnou (přesněji vyhledávání co největší jedničkové podmatice), druhak řešení této úlohy bezostyšně opíšeme.

Převod: Na naši matici položíme 'filtr', který vyznačí jedničkami místa, kde se vyskytuje 'správná' barva vzhledem k hledané šachovnici (správná je ta, kde očekávaná barva = skutečná barva). Tak v matici vzniknou jedničkové podmatice, které máme vyhledat. K našemu úžasu se však v matici objeví nulové podmatice, které odpovídají aplikaci non-filtru pro šachovnici o jedna posunutou (uvědomte si, že jsou jen dva typy hledaných šachovnic, které vzniknou posunutím = negací).

Nyní stačí vyhledat ony maximální jedničkové (nulové) podmatice a jsme hotoví. Druhý špinavý trik bude vyřešen tím, že nahlédnete do již řešené KSP úlohy 9-1-3, kde také najdete detaily (řešení úlohy 9-1-3 je otištěno na konci vzorových řešení). Abych však neriskoval (u)kamenování, uvedu alespoň myšlenku.

Použijeme opět dvou triků.

První: spočtu si pro danou matici spočtu dvě další A, B – na místa jedniček napíšeme počet jedniček, které se nachází přímo pod danou jedničkou (v matici A) a nad danou jedničkou (matice B) (včetně). Matici B dokáži snadno spočítat průchodem postupně po řádcích shora dolů (při výpočtu počtu jedniček nad aktuální budu využívat již spočteného počtu jedniček na předchozím řádku), matici A průchodem po řádcích zdola nahoru.

Druhý: Hledaná strana maximálního jedničkového obdélníku musí přiléhat buď k okraji matice, nebo k nulovému prvku. Protože jsme si kolem celé matice vytvořili pás nul, víme, že strana maximálního jedničkového obdélníka přiléhá k nějakému nulovému prvku.

Hledat obdélníky tedy můžeme tak, že budeme postupně procházet řádky shora dolů, zleva doprava. Vždy když narazíme na jedničku, která následuje po nule, tak začneme nový obdélník. Pro každý obdélník si udržujeme jednak minimum z počtu jedniček od aktuální řádky dolů, jednak minimum z počtu jedniček od aktuální řádky nahoru (tato minima dokážeme díky předpočítaným maticím A a B snadno v konstantním čase upravovat). Zřejmě vzdálenost k začátku obdélníka krát minimum nahoru plus minimum dolů nám dá obsah aktuálního obdélníka, který tedy stačí porovnat s obsahem dosud největšího nalezeného. Když se na aktuálním řádce vyskytne nula, aktuální obdélník již nemůže pokračovat, a proto ho ukončíme.

Celková paměťová i časová složitost je evidentně O(MN), kde N, M jsou rozměry matice, protože na každý prvek jsme sáhli nejvýše konstantněkrát.

Stran vašich řešení: poměrně často se ve vašich řešeních vyskytoval čas O(NM2) s transponováním matice, pakliže M>N. Vyskytlo se dokonce jedno řešení O(NM2) s paměťovou složitostí O(M).

Stran realizace: Filtr je možné definovat pomocí fce xor, posun šachovnice je možný provést „negací“ již zfiltrované matice. Byla by možná úprava algoritmu, jenž by vyhledával nuly a jedničky zároveň. Na asymptotické složitosti ale zřejmě nic nezmění. V programu se držím značení zavedeného v 9-1-3.

Program

Pavel Šanda

12-4-4 Barevné intervaly (Zadání)

Úkolem této úlohy bylo najít minimální počet barev potřebný k obarvení zadaných intervalů a jedno takové obarvení tak, aby žádné dva intervaly, které se překrývají, neměly shodnou barvu. Mezi došlými řešeními se vyskytla řada algoritmů – efektivních i méně efektivních. My si zde ukážeme hladový algoritmus, který tuto úlohu řeší v čase O(n log n), a důkaz jeho správnosti.

Algoritmus: Setřídíme si intervaly v neklesajícím pořadí podle souřadnic jejich počátků. Pak jim postupně v tomto pořadí přidělujeme barvy. Přidělená barva je libovolná již použitá barva různá od barev všech doposud obarvených intervalů, které se překrývají s právě barveným intervalem. Pokud žádná taková barva neexistuje vytvoříme novou barvu a interval obarvíme pomocí ní.

Tvrzení: Algoritmus použije na obarvení intervalů nejmenší možný počet barev a takto zkonstruované obarvení je korektní obarvení.

Důkaz: Kdyby algoritmem zkonstruované obarvení nebylo korektní, existovaly by alespoň dva překrývající se intervaly se stejnou barvou. To ale není možné, vzhledem k výběru barvy při barvení intervalu (vybereme vždy takovou, aby nekolidovala s doposud obarvenými intervaly). Zbývá tedy ukázat, že použitý počet barev je nejmenší možný. Označme si k maximální počet intervalů překrývajících se nad libovolným bodem reálné přímky. Libovolné korektní obarvení intervalů musí použít alespoň k barev (jinak by se nad některým bodem překrývalo více intervalů než máme barev). Ukažme, že náš algoritmus použije právě k barev, a proto bude počet barev jím použitý nejmenší možný. Kdyby jich použil více, pak jsme při barvení nějakého intervalu našli alespoň k s ním se překrývajících doposud obarvených intervalů, a tedy jsme museli vytvořit novou barvu. Označme takový interval I. Podle volby k ale víme, že intervalů překrývajících se nad jedním bodem je maximálně k, tedy i nad bodem odpovídajícímu počátečnímu bodu I se jich překrývá maximálně k. Všimněme si, že všechny doposud obarvené intervaly, které se překrývají s intervalem I, obsahují také počáteční bod I - barvíme je v pořadí vzrůstajících počátečních bodů intervalů. Tedy jich je nejvíce k-1 (bez intervalu I), což je spor s tím, že jsme při barvení intervalu I našli alespoň k doposud obarvených intervalů překrývajících se s I. Dokazované tvrzení tedy platí.

Nyní se zaměřme na efektivní implementaci tohoto algoritmu. Je potřeba umět rychle najít barvu pro nový interval, aby nekolidovala s předchozím obarvením. Pro tento účel si zřídíme zásobník barev. Budeme se pohybovat po hraničních bodech intervalů postupně zleva doprava a aktualní stav zásobníku bude odrážet, které barvy nejsou použity v intervalech obsahující bod na kterém stojíme. Když bude nějaká barva v zásobníku, znamená to, že jí můžeme obarvit interval začínající v bodě, na kterém právě stojíme. To, že zpracovávaný interval touto barvou obarvíme, znamená, že barva je použitá a musíme ji vyjmout ze zásobníku. Barvu do zásobníku vrátíme v okamžiku, když vstoupíme do koncového bodu intervalu, který jí byl obarven. Abychom mohli takto hezky popořadě postupovat po hraničních bodech intervalů, vytvoříme si pole začátků a konců intervalů a utřídíme ho. Po skončení algoritmu vypíšeme počet použitých barev a obarvení jednotlivých intervalů.

Paměťová složitost je lineární k počtu intervalů n, tj. O(n). Časová složitost zahrnuje čas na setřídění pole bodů (začátků a konců intervalů), a pak čas stravený algoritmem při procházení jednotlivých bodů a buď barvením intervalu nebo uvolněním barvy. Přidělit a uvolnit barvu intervalu umíme v konstatním čase, počet bodů je 2n, tedy časová složitost druhé fáze je O(n). Čas na utřídění pole bodů je závislý na použitém třídícím algoritmu, v případě HybridSortu je to v průměrném případě O(n), v nejhorším O(n log n). Ve vzorovém programu je použit QuickSort. Celková časová složitost je tedy O(n log n).

Program

Aleš Přívětivý

12-4-5 PRAM (Zadání)

Nejprve si popišme řešení úlohy a). Náš program bude pracovat v několika etapách. Po k etapách bude platit, že i-tá buňka globální paměti obsahuje součet min(i,2k) předcházejících buněk (počítáno včetně jí samé). Tedy například po první etapě bude šestá buňka obsahovat a5+a6, po dvou etapách bude obsahovat a3+a4+a5+a6 a po třech etapách bude obsahovat a1+a2+a3+a4+a5+a6. Je zřejmé, že po ⌈ log n⌉ obsahují všechny buňky globální paměti požadované součty (n je počet sčítaných čísel).

Spustíme n procesorů a každý z nich bude počítat součet v buňce gmem[cpuid]. Pokud je tento součet již dopočítaný, procesor se zastaví. V k-té etapě přičte procesor k obsahu buňky gmem[cpuid] obsah buňky gmem[cpuid-2k-1]. Protože před k-tou etapou obsahovala buňka gmem[cpuid] součet 2k-1 předchozích čísel a v buňce gmem[cpuid-2k-1] byl uložen součet min(cpuid-2k-1,2k-1) čísel, bude v gmem[cpuid] po k-té etapě součet min(cpuid,2k) předchozích čísel, což jsme požadovali.

Vytvoření samotného programu je již snadné. Místo toho, abychom si pamatovali v kolikáté etapě se nacházíme a z tohoto čísla pak počítali příslušnou mocninu dvojky, budeme si udržovat rovnou číslo 2k. Pokud toto počítadlo dosáhne našeho cpuid skončíme. V opačném případě přičteme ke gmem[cpuid] obsah globální paměťové buňky na pozici cpuid-2k. Z úvah prvního odstavce vyplývá, že poslední procesor dopočítá po O(log n) krocích. Počet použitých procesorů je O(n); naše implementace algoritmu běží dokonce i na CREW-PRAMu.

Program úlohy a

Řešení úlohy b) je ještě jednodušší než řešení úlohy a). Stačí si totiž uvědomit, že ⌈ log x⌉=n právě tehdy když 2n-1<x≤ 2n. Stačí tedy, když každý z x spuštěných procesorů ověří, že 2n-1<x≤ 2n, kde za n zvolí své cpuid. Je nasnadě, že jeden z procesorů ověří nerovnosti pro správné n, neboť pro všechna čísla x platí: ⌈ log x⌉≤ x. K ověření dvou výše uvedených nerovností použijeme následující zřejmé ekvivalence:

2n-1<x ⇔2n-1≤ x-1 ⇔(x-1)>>(n-1) ≠ 0
x≤ 2n ⇔x-1 < 2n ⇔(x-1)>>n = 0

Vytvořit požadovaný program je nyní již snadné; nesmíme však zapomenout ošetřit případ x=1, kdy je spravný výsledek ⌈ log 1⌉=0. Námi navržený algoritmus pracuje na CREW-PRAMu v konstantním čase (O(1)).

Program úlohy b

Daniel Kráľ