Bruteforce

Najjednoduchší spôsob, ako úlohu riešiť bez ohľadu na efektivitu, je hrubou silou. Konkrétne sa to dá stihnúť v $O(n^22^{2n})$ dynamickým programovaním - mám $O(2^{2n})$ stavov, podľa toho, ktoré body v rovine sú už odstránené. Pre každý takýto stav vypočítam, či je možné odstrániť všetky ostatné body, až na ten jeden, ktorý má na konci zostať neodstránený, a to tak, že vyskúšam aktivovať každý z $O(n)$ bodov typu A, ktoré zostávajú, v kombinácii s každým bodom typu B, čo sa dá s trochou predpočítania vzdialeností stihnúť v čase $O(n^2)$. Pokiaľ takto nájdem nejaký stav, ktorý vedie k riešeniu, uložím si, ktoré body treba aktivovať tak, aby som sa k riešeniu dostal. Na konci sa len pozriem na stav, kde žiadne body nie sú odstránené, a uvidím, či existuje cesta vedúca k riešeniu. Ak áno, konštrukciu zhotovím jednoducho tak, že budem po týchto odkazoch skákať, kým neodstránim všetky potrebné body.

Optimálne riešenie

Teraz sa zamyslime, ako túto úlohu riešiť omnoho efektívnejšie. Zabstraktnime najprv zadanie - máme nejaké body typu A. Každý takýto bod má nejaké vzdialenosti od každého bodu typu B. Uvedomme si, že vzdialenosti od bodov typu B, ktoré sú vzdialenejšie ako ten, ktorý nechceme odstrániť, sú irelevantné, pretože určite nebude možnosť ich nikdy odstrániť. Rovnako tak môžeme potom odignorovať aj vzdialenosť od toho bodu samotného, keďže ho nikdy nebudeme odstraňovať. Po takejto úvahe sme zadanie úlohy zjednodušili na nasledovný formát: každý z $n$ bodov typu A má niekoľko susedných bodov typu B (ktorých je tiež $n$), ktoré majú od neho rôzne vzdialenosti. Našou úlohou je odstrániť všetky takéto body postupne tak, že vždy s bodom typu A odstránime aj jeden zo susedných bodov typu B takých, že všetky bližšie body typu B sme už odstránili.

Teraz si uvedomme, že k riešiteľnosti takéhoto zadania poznáme očividnú nutnú podmienku - v grafe susedov musí existovať úplné párovanie. Tak môžeme zbehnúť algoritmus Hopcroft-Karp, ktorý nám nájde maximálne párovanie v bipartitnom grafe v čase $O(n^{2.5})$. Pokiaľ výsledné párovanie nebude úplné, môžeme hneď odpovedať NIE. Ale čo ak úplné bude? Môžeme skúsiť na základe tohto úplného párovania zostrojiť riešenie zadania…

Máme teda bipartitný graf, poznáme jeho úplné párovanie, a navyše máme pre každý bod typu A dané, ktoré body typu B sú s ním momentálne aktivovateľné (sú mu najbližšie z tých neodstránených). Pokiaľ niektorá dvojica v párovaní pozostáva z bodu typu A, a bodu typu B, ktorý je s ním aktivovateľný, môžeme oba odstrániť a pokračovať v konštrukcii zredukovaným prípadom. Komplikovanejší prípad je, keď ani jedna dvojica párovania nie je spolu aktivovateľná. Vtedy ale vieme párovanie upraviť tak, aby sa taká dvojica našla - pre každý bod typu A určíme nejaký bod typu B, s ktorým je aktivovateľný. Vždy to bude iný bod, než ten, s ktorým je spárovaný, preto určite vznikne nejaký cyklus, v ktorom sa striedajú hrany z párovania s hranami, ktoré spájajú dva spolu aktivovateľné body. Jednoducho párovanie upravíme tak, že invertujeme hrany podľa tohto cyklu - odstránime tie, ktoré v ňom sú, a pridáme tie zvyšné hrany tohto cyklu. Stále pôjde o úplné párovanie, a navyše budú zaručene existovať spárované spolu aktivovateľné body. Tento postup teda v čase $O(n^2)$ určite povedie ku správnemu riešeniu.

Vidíme teda, že ak úplné párovanie neexistuje, odpoveď je záporná, a ak existuje, určite vieme na jeho základe nájsť konštrukciu, a teda odpoveď je kladná. Časová zložitosť riešenia je $O(n^{2.5})$, a pamäťová stačí $O(n^2)$.