4. Energetické pole vzorové riešenie

2 5
0 0 1 1 1
0 0 1 1 1

4

4 4
0 0 0 0
1 4 4 3
1 5 6 3
1 2 2 2

7

Hrubá Sila

Na začiatok si preformulujme zadanie úlohy pomocou všeobecnejších pojmov, a potom si ukážeme prvé jednoduché riešenie tejto úlohy.

Máme tabuľku, ktorá bola ofarbená postupnosťou ofarbení jednotlivých stĺpcov a riadkov v nejakom poradí. Platí pritom, že sme vždy ofarbili celý daný stĺpec/riadok tou istou farbou. Našou úlohou je určiť, koľko najmenej takýchto ofarbení potrebujeme použiť na dosiahnutie tabuľky zo vstupu. Všimnime si, že ak jeden riadok či stĺpec ofarbíme druhýkrát, všetka informácia o prvom ofarbení sa stratí. Vďaka tomu môžeme predpokladať, že vo výslednom ofarbení bol každý riadok aj každý stĺpec zafarbený najviac raz.

Tu sa naskytá nápad na jednoduché riešenie: Keďže každý riadok aj stĺpec sme zafarbili najviac raz, ak si zoberieme všetky možné zoradenia stĺpcov a riadkov, tak môžeme v danom poradí skúšať odfarbovať stĺpce a riadky tabuľky. Riadok či stĺpec budeme môcť odfarbiť iba vtedy, ak sú všetky zafarbené políčka v ňom jednej farby. V prípade, kedy sa nám podarí celú tabuľku vyčistiť najskôr, dostaneme optimálne riešenie. V tomto riešení teda hľadamé postupnosť ofarbení riadkov a stĺpcov tak, že pre každú postupnosť odzadu (odfarbovaním) overíme, či vstupná tabuľka mohla vzniknúť touto postupnosťou.

Odfarbenie riadka/stĺpca sa dá jednoducho implementovať tak, že odfarbený riadok/stĺpec z tabuľky odstránime (budeme ho ďalej ignorovať), pretože nám nezáleží na tom, aké farby boli “pod posledným náterom”. Namiesto skúšania všetkých permutácií riadkov a stĺpcov by sme tiež mohli myšlienku riešenia implementovať aj mierne efektívnejšie – pomocou backtracku (rekurzívne prehľadávanie s návratom).

Takéto priame a myšlienkovo jednoduché riešenie musí vyskúšať všetky permutácie riadkov a stĺpcov¹, ktorých je \((r+s)!\) a pre každú permutáciu musí overiť, či vedie k tabuľke zo vstupu, napríklad v čase \(O(rs)\). Celé riešenie tak bude mať časovú zložitosť \(O((r+s)! \cdot rs)\), vďaka čomu na bežnom počítači vyrieši vstupy s \(r+s < 10\).

Greedy riešenie

Pri opravovaní vašich riešení sme sa dozvedeli, že vďaka tomu, že sa na vstupe nachádzali len korektné zadania (každá ofarbená tabuľka bola výsledkom farbenia riadkov a stĺpcov), sa táto úloha sa dala vyriešiť aj pažravým (greedy) prístupom.

Hlavná myšlienka pažravého riešenia je, že sa pokúsime tabuľku postupne od konca odfarbovať tak, ako v riešení hrubou silou. Ak ale máme na výber z viacero možností čo spraviť (môžeme odfarbiť viacero stĺpcov alebo môžeme odfarbiť riadky aj stĺpce), nebudeme sa rekurzívne rozvetvovať a skúšať všetky možné poradia, ale jednoducho odfrabíme všetky jednofarebné stĺpce alebo riadky jednej farby naraz, skoro vždy v ľubovoľnom poradí.

Jediné špeciálne prípady nastanú vtedy, ak nám zostáva tabuľka, kde sú všetky riadky jednofarebné, všetky stĺpce jednofarebné alebo ak sa po odstránení jednofarebných stĺpcov/riadkov dostaneme do takejto situácie. Vtedy sa nám môže oplatiť odfarbiť všetky stĺpce okrem stĺpcov jednej farby a zvyšné stĺpce odfarbiť pomocou odfarbenia riadkov, ak je riadkov menej ako stĺpcov.

Takéto riešenie sa pomerne ľahko vymyslí a naprogramuje, no tá najťažšia časť pri ňom je dokázať, že vždy vedie k optimálnemu riešeniu. Dôkazom si tiež overíte, že ste pri vymýšľaní postupu nezabudli na žiadne špeciálne prípady. Mnohí z vás stratili body na nepremyslení si špeciálnych prípadov alebo na nedôslednom dôkaze (keďže sme greedy riešeniu spočiatku neverili, bolo nás nutné presviedčať). Rozhodli sme sa teda napísať časť dôkazu, ktorý zachytáva hlavné myšlienky toho, prečo pažravé riešenia môžu fungovať a otázky nad ktorými sa bolo potrebné sa zamyslieť.

Zadefinujme si poriadne všetky situácie, ktoré môžu nastať. Počas celého riešenia (odfarbovania) musí platiť, že sa v tabuľke vždy nachádza aspoň jeden celý riadok alebo stĺpec. Vzhľadom na to, že riadky sa stanú stĺpcami keď tabuľku otočíme o 90 stupňov, budeme hovoriť len o prípadoch, kedy máme aspoň jeden jednofarebný riadok.

1. V tabuľke sú iba jednofarebné riadky. Rôzne riadky môžu byť rôznych farieb. Takáto situácia je veľmi blízko k odfarbeniu celej tabuľky – už nám stačí odfarbiť len všetky riadky, prípadne možno riadky poslednej farby odfarbiť po stĺpoch.
2. V tabuľke je aspoň jeden nejednofarebný riadok. Tabuľka obsahuje jeden alebo niekoľko jednofarebných riadkov, ktoré sú všetky tej istej farby a neobsahuje žiaden jednofarebný stĺpec. V tomto prípade existuje len jediná cesta ako pokračovať ďalej v riešení – odstránime všetky tieto riadky.
3. V tabuľke je aspoň jeden nejednofarebný riadok. Tabuľka obsahuje jeden alebo niekoľko jednofarebných riadkov, ktoré sú aspoň dvoch rôznych farieb a neobsahuje žiaden jednofarebný stĺpec. V tomto prípade máme na výber – riadky ktorej farby odstránime najskôr?
4. V tabuľke je aspoň jeden nejednofarebný riadok. Tabuľka obsahuje aspoň jeden jednofarebný riadok a aspoň jeden jednofarebný stĺpec, ktoré sú (musia byť) všetky tej istej farby. Tu máme opäť na výber – odstránime najprv riadky alebo stĺpce?

Môžete si rozmyslieť, že iné situácie (až na triviálne – všetky políčka jednej farby a prázdna tabuľka) už nikdy nenastanú.

Čo robiť v situácii 4? Ak sa odobraním riadka dostaneme do situácie 1 s jednofarebnými stĺpcami, môže sa nám oplatiť teraz neodstrániť stĺpec tejto farby, lebo výhodnejšie môže byť jeho odstránenie na konci, v podobe riadkov. Existuje ešte nejaká iná situácia, kedy neodstrániť aj riadok aj stĺpec (prípadne všetky jednofarebné riadky aj stĺpce)? Nie. Ak po odstránení riadkov nie sme ešte v situácii 1, znamená to, že na doriešenie úlohy je potrebné odoberať ešte stĺpce a potom ešte riadky inej farby. To ale znamená, že naše jednofarebné stĺpce budeme musiť tiež odobrať, a teda ich môžeme odobrať hneď teraz! V skoro všetkých prípadoch je teda jedno, či odstránime najprv riadky, najprv stĺpce alebo všetko naraz.

Čo robiť v situácii 3? Na to, aby sme pohli v riešení ďalej (do inej situácie) musíme buď odobrať všetky jednofarebné riadky (dostanem sa do 1, 2 alebo 3, kde dostaneme jednofarebné stĺpce) alebo odoberieme všetky riadky okrem riadkov jednej farby (dostaneme sa do 2 alebo 4). Úvahu si môžeme zjednodušiť tak, že nikdy neodstránime všetky riadky ale vždy zachováme riadky jednej farby a potom sa budeme rozhodovať ako keby sme boli v situácii 4 (alebo 2). Ak sa potom znova rozhodneme odobrať riadok, dosiahneme rovnaký výsledok ako keby sme rovno odstránili všetky riadky. Poslednou otázkou teda zostáva to, či závisí na tom, ktoré riadky jednej farby ponecháme ako posledné. Na tomto ale záleží len vtedy, ak by sme sa z následnej situácie 4 dostali do 1. Inak v situácii 4 tieto riadky aj tak ostránime a znova teda vo väčšine prípadov nezáleží na tom, ktorú farbu ponecháme!

Konkrétne riešenia špeciálnych prípadov sa dali vyriešiť najjednoduchšie tak, že v každom kroku odsimulujeme pár krokov algoritmu hrubou silou. Dali sa tiež navrhovať konkrétne postupy riešenia jednotlivých špeciálnych prípadov, no tie by si vyžiadali ešte viac dokazovania.

Daľej nasleduje naše pôvodné vzorové riešenie, ktoré je možno náročnejšie (alebo trikovejšie) na vymyslenie, no jednoduchšie vidno, že je správne.

Optimálna postupnosť farbení a náčrt lepšieho riešenia

Pozrime sa znovu na nejakú postupnosť farieb, ktorá je optimálnym riešením tejto úlohy. Keďže každé políčko tabuľky je nejako zafarbené, tak musel byť zafarbený buď každý stĺpec alebo každý riadok. Predpokladajme, preto, že počas procesu bol každý riadok aj každý stĺpec zafarbený práve raz. Potom si vieme všetky riadky a stĺpce zoradiť do jednej postupnosti, podľa toho, v akom poradí boli ofarbené. Všimnime si, že prvý stĺpec alebo prvý riadok, ktorý sme ofarbili, na výsledné ofarbenie tabuľky vôbec nevplýva, keďže všetky riadky resp. stĺpce boli neskôr prefarbené. Preto ho v optimálnom riešení nezafarbíme, keďže aj tak nič nemení. Povedzme, že to bol \(i\)-ty riadok. Keďže sme ho nezafarbili ani raz, tak podľa neho vieme zistiť, akými farbami boli zafarbené všetky stĺpce a podľa týchto stĺpcov vieme zistiť ako (resp. či) boli zafarbené zvyšné riadky. Riešením úlohy potom bude počet stĺpcov \(+\) počet riadkov, ktoré sme zafarbili.

Ideálne riešenie

Keďže vieme, že jeden z riadkov alebo stĺpcov nebol v optimálnom riešení zafarbený, môžeme ich všetky prejsť a pre každý zistiť, či to mohol byť daný riadok/stĺpec. Najprv zistíme, či sú farby riadkov a stĺpcov, ktoré sú implikované týmto riadkom/stĺpcom, konzistenté s tabuľkou vo vstupe. Ak áno, tak vieme, koľko zafarbení by sme museli použiť. Ak je tento počet menší, ako počet prefarbení v doteraz najlpšom riešení (ktoré sme dostali tak, že sme predpokladali, že nezafarbený bol iný riadok/stĺpec), tak sme našli lepšie riešenie, ktoré si uložíme.

Náš program teda bude vyzerať nasledovne. Budeme mať funkciu, ktorej určíme jeden riadok, o ktorom budeme predpokladať, že nebol zafarbený. Táto funkcia nám vráti počet ofarbení riadkov a stĺpcov potrebných na ofarbenie tabuľky. Podľa farieb v určenom riadku určíme farby, ktorými boli zafarbené jednotlivé stĺpce. Potom prejdeme všetky políčka v tabuľke, pričom ak dané políčko nie je farby príslušného stĺpca, priradíme jeho farbu k danému riadku. Ak mal tento riadok už priradenú nejakú farbu, ktorá je odlišná od farby políčka, tak nebude existovať žiadne riešenie, pretože každé políčko môže mať farbu len od stĺpca alebo od riadka. V takomto prípade môžeme vrátiť \(r+s\), keďže optimálne riešenie je od \(r+s\) ostro menšie. Ak nenájdeme žiaden spor, zrátame počet riadkov, ktorým sme priradili farbu, pripočítame ho ku počtu stĺpcov a toto číslo vrátime.

Túto funkciu spustíme postupne na všetkých riadkoch tabuľky, pričom si uložíme minimum čo nám vrátila. Keďže sme leniví a nechce sa nám robiť samostatnú funkciu pre stĺpce, tabuľku následne transponujeme (vymeníme riadky za stĺpce a naopak) a zopakujeme to isté, čo sme spravili predtým.

Časová zložitosť takéhoto riešenia bude \(O((r+s) \cdot rs)\) keďže pre každý potenciálne nezafarbený riadok/stĺpec prechádzame celú tabuľku. Jeho pamäťová zložitosť bude \(O(rs)\), keďže najväčšie, čo si kedy pamätáme, je samotná tabuľka a tú si potrebujeme pamätať celú.

Nájde náš algoritmus skutočne správne ofarbenie tabuľky?

Tu by bolo na mieste poznamenať, že predpokladáme, že riešenie, ktoré sme našli je naozaj riešením, a že takýmto počtom ofarbení naozaj vieme získať tabuľku zo vstupu. Overili sme to, či sme niektoré riadky neofarbili dvoma farbami. Podobne aj pre stĺpce. No neoverili sme to, či sa tabuľka dá naozaj škontruovať, a či by pri takejto konštrukcii nemohli vzniknúť cykly. Pod cyklom myslíme prípady, kedy by sme museli riadok \(i\) zafarbiť skôr ako stĺpec \(j\), lenže zároveň by sme museli stĺpec \(j\) zafarbiť skôr ako riadok \(i\), viď. obrázok, kde sa dané zafarbenie nedá skonštruovať:

Žltý stĺpec bol zafarbený pred zeleným riadkom. Ten bol zafarbený pred modrým stĺpcom. Modrý stĺpec musel byť zafarbený pred červeným riadkom, takže sme červený riadok museli zafarbiť po žltom stĺpci. No vidíme, že žltý stĺpec sme museli zafarbiť po červenom riadku, a obe tieto podmienky sa nedajú splniť naraz.

Jeden spôsob, akým by sme tento problém mohli vyriešiť, je detekcia cyklov. Mohli by sme si skonštruovať orientovaný bipartitný graf, v ktorom vedie hrana z riadku do stĺpca vtedy, keď sme riadok ofarbili neskôr a hrana zo stĺpca do riadku, keď sme ofarbili neskôr stĺpec. Následne by nám stačilo overiť, že sa v grafe nevyskytuje cyklus.

Namiesto toho si ale môžeme dokázať, že za predpokladu, že vstupná tabuľka je ofarbiteľná, sa takýto cyklus nebude v žiadnom nájdenom riešení vyskytovať. Rozoberme si dva prípady: prvý, keď sú všetky hrany tohoto cyklu (čiže políčka, ktoré ležia na prienikoch riadkov a stĺpcov cyklu) mimo určeného nezafarbeného riadku; a druhý, keď sa nejaká hrana (políčko) nachádza v tomto riadku.

V prvom prípade sa tento cyklus v tabuľke nachádzal aj predtým, ako sme sa rozhodli, že náš riadok bude vo výslednom riešení ten, ktorý nebol ofarbený. Toto sa ale nemohlo stať, keďže zadanie úlohy garantuje, že pre tabuľku na vstupe existuje nejaké riešenie.

Druhý prípad, kedy sa náš zvolený riadok nachádza v cykle, sa rovnako nemôže stať. O tomto riadku predpokladáme, že sme ho nezafarbili, a teda nebol zafarbený pred ani po žiadnom stĺpci (mohli by sme povedať, že bol zafarbený pred všetkými stĺpcami, tým by sme ale vylúčili akýkoľvek cyklus).

Pri riešení úlohy by ste si mali byť istí, že váš algoritmus produkuje správne riešenia. V tejto úlohe ste teda mali na výber buď implementovať hľadanie cyklov, alebo dokázať, že aj riešenie bez ich hľadania bude vždy fungovať.

def zisti_pocet_ofarbeni(tabulka, nezafarbeny_riadok):
    r = len(tabulka)
    s = len(tabulka[0])

    farby_stlpcov = [tabulka[nezafarbeny_riadok][j] for j in range(s)]
    farby_riadkov = [-1 for i in range(r)]

    for y in range(r):
        for x in range(s):
            if tabulka[y][x] != farby_stlpcov[x]:
                if (farby_riadkov[y] != -1 and farby_riadkov[y] != tabulka[y][x]):
                    return r + s
                farby_riadkov[y] = tabulka[y][x]
    
    pocet_ofarbeni = s
    for y in range(r):
        if farby_riadkov[y] != -1:
            pocet_ofarbeni += 1

    return pocet_ofarbeni


r, s = map(int, input().split())
tabulka = []
for i in range(r):
    tabulka.append(list(map(int, input().split())))

odpoved = r + s - 1
for i in range(r):
    odpoved = min(odpoved, zisti_pocet_ofarbeni(tabulka, i))

tabulka = [*zip(*tabulka)]  # sikovna implementacia transponovania tabulky
for i in range(s):
    odpoved = min(odpoved, zisti_pocet_ofarbeni(tabulka, i))

print(odpoved)