4. Delíme sa s jedlom vzorové riešenie

3 0
0 1 1
0 0 0
0 1 0

1
1

4 0
0 1 0 0
0 0 1 0
1 0 0 1
1 1 0 0

2
2 4

Prvé nápady

Situáciu z tejto úlohy si vieme predstaviť pomocou orientovaného grafu, kde vrcholy zodpovedajú vedúcim a od vedúceho \(i\) k vedúcemu \(j\) vedie hrana práve vtedy, keď vedúci \(i\) je ochotný podeliť sa s vedúcim \(j\). Chceme vybrať takú množinu vrcholov, aby bol každý vrchol v tejto množine alebo aby susedil s nejakým vrcholom z tejto množiny.

Najľahšie riešenie samozrejme dosiahneme tak, že každý vedúci donesie jedlo. Takto však bude musieť doniesť jedlo až všetkých \(n \leq 1000\) vedúcich, čo je veľmi neoptimálne.

O niečo lepšie riešenie vieme dosiahnuť tak, že zaručíme, aby každý vedúci, ktorý donesie jedlo, pokryl ešte aspoň nejakého jedného ďalšieho vedúceho, ktorý tak nebude musieť doniesť jedlo. To vieme spraviť tak, že popárujeme vedúcich do dvojíc \((1,2)\), \((3, 4)\) a tak ďalej, pričom v prípade nepárneho počtu vedúcich nám ostane na konci ešte jeden nespárovaný vedúci.

Vieme, že v každej dvojici je práve jeden vedúci ochotný podeliť sa s tým druhým, takže v každej dvojici sa nám stačí pozrieť na to, ktorý vedúci z danej dvojice to je. Potom stačí, aby tento vedúci doniesol jedlo, a pokryje tým aj druhého vedúceho z danej dvojice. Pre nepárne \(n\) posledného nespárovaného vedúceho vieme vyriešiť zrejme tak, že aj on samotný ešte prinesie jedlo.

Týmto postupom vieme vybrať \(\lceil n/2 \rceil\) vedúcich tak, že pokryjeme každého vedúceho, čo nám stačí na zisk \(2\) bodov. Časová aj pamäťová zložitosť tohto postupu je \(O(n^2)\) kvôli načítavaniu vstupu, zvyšok už prebehne v čase lineárnom od \(n\), keďže počet dvojíc je lineárny od \(n\) a v každej sa nám stačí pozrieť len na to, z ktorého vrcholu do ktorého vedie hrana.

Optimálne riešenie

Keď sa pokúsime vyššie uvedené riešenie vylepšiť a zaručiť tak napríklad pokrytie viacerých než dvoch vedúcich jedným vedúcim, zistíme, že to už takto ľahko zlepšiť nejde. Napríklad spomedzi trojice vedúcich už nemusíme vedieť vybrať jedného vedúceho, ktorým pokryjeme zvyšných dvoch.

Môže nám ale napadnúť pažravé (greedy) riešenie, v ktorom vždy vyberieme nejakého nepokrytého vedúceho, ktorý nám pokryje čo najviac ešte nepokrytých vedúcich. Takto vyberáme ďalších vedúcich s jedlom až dokým nepokryjeme úplne všetkých vedúcich. Toto riešenie znie prirodzene, no bez ďalšieho dôkazu nie je vôbec jasné, ako dobré v skutočnosti je.

Poďme sa bližšie pozrieť na jeden krok tohto postupu. Nech je ešte nepokrytých \(x\) vedúcich a my z nich vyberáme toho vedúceho, ktorý pokryje čo najviac nepokrytých vedúcich. Poďme spočítať, koľko vedúcich takto pokryjeme.

Tu nám pomôže grafová interpretácia tejto úlohy. Ľubovoľný nepokrytý vrchol totiž určite pokryje sám seba a okrem toho pokryje práve toľko vrcholov, koľko hrán z neho vedie k ešte nepokrytým vrcholom.

V podgrafe celého grafu tvorenom len nepokrytými vrcholmi a hranami medzi nimi pritom máme hranu medzi každou dvojicou rôznym vrcholom, a to orientovanú práve jedným smerom, takže hrán v tomto podgrafe je \(\binom{x}{2} = \frac12 x (x-1)\). Každá táto hrana vychádza z nejakého z \(x\) ešte nepokrytých vrcholov, takže z jedného vrcholu vychádza priemerne \(\frac12 (x-1)\) hrán.

Keď potom vyberieme nepokrytý vrchol, z ktorého vychádza najviac hrán do nepokrytých vrcholov, tak z neho bude určite vychádzať aspoň priemerný počet hrán, teda aspoň \(\frac12 (x-1)\). V opačnom prípade by totiž z každého nepokrytého vrcholu vychádzalo menej než \(\frac12 (x-1)\) hrán do nepokrytých vrcholov, a tak celkovo zo všetkých \(x\) nepokrytých vrcholov by dokopy vychádzalo menej než \(\frac12 x(x-1)\) hrán do ďalších nepokrytých vrcholov, teda hrán medzi nepokrytými vrcholmi by bolo menej než \(\frac12 x(x-1)\), čo je ale spor s tým, že hrán medzi danými vrcholmi je práve \(\frac12 x(x-1)\).

Vybraný vrchol tak pokryje sám seba a okrem toho ešte aspoň \(\frac12 (x-1)\) ďalších nepokrytých vrcholov, teda v jednom kroku pokryjeme aspoň \(1 + \frac12 (x-1) = \frac12 (x+1)\) ešte nepokrytých vrcholov. Všimnime si, že v jednom kroku pokryjeme vždy viac než polovicu všetkých ešte nepokrytých vrcholov, takže počet potrebných krokov ako aj počet vybraných vrcholov bude približne logaritmický oproti celkovému počtu vrcholov.

Poďme presne určiť potrebnú veľkosť vybranej podmnožiny vedúcich pre \(n \leq 1000\). Zrejme nám stačí určovať tento počet pre maximálny počet vedúcich, teda pre \(n=1000\). Po vybraní \(0\) vedúcich tak máme \(x=1000\) nepokrytých vedúcich a v každom ďalšom kroku nám počet nepokrytých vedúcich klesne z \(x\) aspoň na \(x - \frac12 (x+1) = \frac12 (x-1)\), pričom tento počet musí ostať celočíselný, takže v skutočnosti najväčší možný počet nepokrytých vedúcich po ďalšom kroku je \(\lfloor \frac12 (x-1) \rfloor\). Maximálne počty nepokrytých vedúcich po \(k\) vybraných vedúcich týmto postupom tak vieme postupne odsimulovať a zapísať do nasledovnej tabuľky:

Vidíme, že pre \(n \leq 1000\) skutočne stačí vybrať \(9\) vedúcich na pokrytie všetkých vedúcich, čo už stačí na zisk plného počtu bodov.

Zamyslime sa ešte nad tým, akú časovú a pamäťovú zložitosť má tento postup. Pri najjednoduchšom spôsobe implementácie prechádzame v každom kroku cez \(n\) vrcholov a pre každý nepokrytý vrchol zrátame, do koľkých ďalších nepokrytých vrcholov z neho vedú hrany, prechodom cez všetkých \(n\) možností na jeho suseda. Následne vrchol s maximálnym počtom susedov a aj všetkých jeho susedov označíme za pokrytých a pokračujeme ďalej. Takýchto krokov je \(O(\log n)\), takže takto dostávame celkovo časovú zložitosť \(O(n^2 \log n)\).

Toto vieme ešte mierne vylepšiť tak, že si v hešovacej tabuľke udržiavame všetky ešte nepokryté vrcholy a v každom kroku prechádzame len cez ne. Takto krok, v ktorom je nepokrytých vrcholov \(x\), zaberie čas \(O(x^2)\). Keďže zároveň v každom kroku klesne veľkosť nepokrytej množiny aspoň na polovicu, tak tento postup uskutoční rádovo \(n^2 + (n/2)^2 + (n/4)^2 + \dots + (n/n)^2\) operácií. Túto hodnotu vieme zhora ohraničiť \(n^2\) násobkom súčtom nekonečného geometrického radu s počiatočnou hodnotou \(1\) a kvocientom \(1/4\), teda hodnotou \(n^2 \cdot \frac{1}{1-\frac14} = \frac43 n^2\), takže časová zložitosť je teraz dokonca \(O(n^2)\).

Po hlbšom zamyslení vieme dokonca zistiť, že aj časová zložitosť pôvodného algoritmu bez hešovacej tabuľky je v skutočnosti \(O(n^2)\). V každom kroku totiž lineárne prechádzame všetkými vrcholmi, ale ďalej počítame počty hrán len pre tie nepokryté vrcholy. Keďže je krokov \(O(\log n)\), tak lineárne prechody všetkými vrcholmi vyjdú dokopy len na čas \(O(n \log n)\) a prechody všetkými hranami, kde za prvý vrchol vezmeme vždy len nejaký nepokrytý vrchol, zaberie čas rádovo \(n\cdot n + n/2 \cdot n + n/4 \cdot n + \dots + n/n \cdot n\), čo je opäť zhora ohraničené súčtom nejakého nekonečného geometrického radu, ktorého hodnota je tentokrát \(2n^2\), takže aj časová zložitosť pôvodného algoritmu je \(O(n^2)\)

Pamäťová zložitosť je \(O(n^2)\), keďže si musíme pamätať informácie o všetkých hranách.