2. Totálny zabiják vzorové riešenie

2 3
-1 1

-1
0
1

3 7
-1 0 1

-1
-1
0
0
0
1
1

Najprv vyriešime ľahšiu úlohu (aj keď ťažko predstaviteľnú) a to takú, že budeme predpokladať, že Emko až taký hlúpy nie je. To znamená, že nie je ochotný zaplatiť za objednávku niektorého z nepriateľov, teda všetky čísla na vstupe budú nezáporné.

Hlavná myšlienka

Keďže chceme vypisovať hodnoty možných účtov od najmenšieho, najrozumnejšie je všetkých kandidátov na najlacnejší účet nahádzať do minimovej haldy a potom odtiaľ vyberať vždy najlacnejší. Kandidátov ale máme všetky podmnožiny, čo je teda až \(2^n\) prvkov v halde. Stačí si však uvedomiť, že kandidátmi na najlacnejší (ešte nevypísaný účet) nie sú od začiatku všetky podmnožiny, ale sa nimi stanú až neskôr.

Kandidáti

Vieme napríklad povedať, že ak \(A\) je podmnožinou \(B\), tak \(A\) vypíšeme určite skôr, lebo \(B\) získame z \(A\) pridaním niekoľko nezáporných prvkov. Takže množina sa stane kandidátom až keď vypíšeme všetky jej podmnožiny, a dovtedy ju do haldy vôbec nemusíme pridávať. Čo teda spôsobí, že v halde sa vyskytne výrazne menej vecí, keďže \(k\) je relatívne malé.

Vyššie uvedená úvaha sa ale dá potiahnuť ešte ďalej. Vieme si vybudovať graf závislostí, kde vrcholy sú možné účty a orientovaná hrana z \(A\) do \(B\) bude znamenať, že \(B\) pridáme do haldy (stane sa kandidátom) keď vypíšeme \(A\).

Od takéhoto grafu budeme požadovať viacero vecí. Za prvé si musíme byť istý, že \(A\) je lacnejší ako \(B\), teda že sa od nás nečakalo, že vypíšeme \(B\) a \(B\) sme ešte nemali ani v halde. A zároveň nechceme ten istý účet pridávať do haldy viackrát, teda do jedného vrchola môže smerovať najviac jedna hrana. Nakoniec musí byť každý vrchol dosiahnuteľný z vrcholu reprezentujúceho najlacnejší účet.

Rozmyslite si, prečo sú horeuvedené tri podmienky nutné a zároveň postačujúce na to, aby náš algoritmus (\(k\)-krát vyber najlacnejšieho kandidáta z haldy a pridaj do nej nových kandidátov) fungoval správne.

Ako rozumne zvoliť graf?

Ak máme vrchol reprezentujúci podmnožinu \(\lbrace a_1, a_2, ..., a_n \rbrace\), tak budú z neho viesť hrany do vrcholov reprezentujúcich množiny \(\lbrace a_1, a_2, ..., a_n, b \rbrace\) a \(\lbrace a_1, a_2, ..., a_{n-1}, b \rbrace\), kde \(b\) označuje najmenšie číslo väčšie ako \(a_n\).

Zjavne platí, že do každého vrchola vedie len jedna hrana. A tiež hrany vedú smerom od lacnejších účtov ku drahším, keďže prvý typ hrany vedie ku nadmnožine a pri druhom type vymeníme \(a_n\) za \(b\), čo je aspoň tak veľké číslo. A nakoniec, na príklade ilustrujeme, akým spôsobom vieme dosiahnuť každý vrchol (a všeobecný prípad nechávame na rozmyslenie): ak sú všetky čísla \(1, 2, 3, 4, 5, 6, 7, 8\), tak napríklad vrchol \(\lbrace 1, 3, 4, 7\rbrace\) dosiahneme takto:

\[ \lbrace 1 \rbrace \rightarrow \lbrace 1, 2 \rbrace \rightarrow \lbrace 1, 3 \rbrace \rightarrow \lbrace 1, 3, 4 \rbrace \rightarrow \lbrace 1, 3, 4, 5 \rbrace \rightarrow \lbrace 1, 3, 4, 6 \rbrace \rightarrow \lbrace 1, 3, 4, 7 \rbrace \]

Riešenie našej podúlohy

To čo teraz vieme spraviť je, že na začiatku pridáme do haldy najlacnejší prvok, a následne \(k\)-krát vyberieme z haldy najlacnejší prvok, vypíšeme ho, a pridáme \(2\) nasledujúcich kandidátov do haldy. Na to aby sme o kažom vrchole vedeli povedať, kam smerujú jeho hrany a vedeli vypísať jeho hodnotu, nám stačí si pamätať súčet jeho členov a najväčší prvok.

Riešenie ak je Emko hlúpy

Toto vieme upraviť na úlohu, ktorú sme už vyriešili. Stačí ak spustíme náš algoritmus na absolútnych hodnotách a odpočítali vždy súčet záporných čísel na vstupe. Prečo to funguje? Totiž ak sa rozhodneme neakú podmnožinu vypísať, tak vlastne sa rozhodneme vypísať túto podmnožinu s tým, že tam pridáme všetky záporné čísla okrem tých ktoré sme už vybrali (v absolútnej hodnote) a teda sa nám akoby vynulujú.

Prvýkrát, keď by sme mali vypísať nulový účet, ho na výstup nedáme (lebo neprázdny účet nás nezaujíma).

Čo sa týka časovej zložitosti, tak potrebujeme načítať vstup a v \(k\)-kolách vždy jeden prvok odstrániť a dva pridať do haldy, teda \(O(n + k \log k)\).