5. Obezlička vzorové riešenie

3
.#.
###
.#.

1

8
...#....
...#....
...#....
########
...#....
...#..#.
...#.###
...#..#.

3

Stručný obsah podčlánkov je nasledovný:

• Hrubá sila: riešenie overovaním všetkých štvorcových plôch z ich ľavého horného rohu \(O(n^5)\).
• Dá sa to aj múdrejšie: overovanie štvorcov zo stredu \(O(n^4)\).
• Pozrime sa na to bližšie: správny odhad časovej zložitosti riešenia \(O(n^2)\).

Hrubá sila

V tomto najjednoduchšom riešení by sme sa postupne chceli pozrieť na všetky štvorcové oblasti tabule, zistiť, ktoré z nich sú nepočmáranými pluskami a na základe toho zistiť, koľko bodov Roman dostane.

Každý štvorec (každé plusko) je na tabuli určený jeho ľavým horným rohom a dĺžkou strany. Ak si teda fixne zvolíme jedno políčko \((i,j)\), chceme postupne skúšať dĺžky strany \(3,5,7,...\) (teda štvorce s ľavým horným políčkom \((i,j)\) a pravým dolným políčkom postupne \((i+2,j+2),(i+4,j+4),...\))

Ak máme vybraný štvorec s rohovými políčkami \((i,j)\) a \((i+x,j+x)\), vieme ľahko overiť, či je tento štvorec nepočmáraným pluskom. Stačí prejsť jeho všetky políčka v cykle a overiť, že tie, ktoré sú v strednom riadku (teda \((i+x/2,j), (i+x/2,j+1), (i+x/2,j+2), ..., (i+x/2,j+x)\)) alebo v stredom stĺpci (teda \((i, j+x/2), (i+1, j+x/2), ... (i+x, j+x/2)\)) musia byť popísané (#), a ostatné nepopísané (.).

Ako ale zistiť počet bonusových bodov? V zadaní sa písalo: “Za plus veľkosti \(v\) dostane Roman \(v\) bodov, no každé plus veľkosti aspoň 2 obsahuje vo svojom strede menšie pluská a za tie už Roman body nedstane.”

Pre správny výpočet výsledku nám však stačí len zistiť počet štvorcov, ktoré sú pluskami. Neveríte?

Ak je na tabuli plusko veľkosti 1, nájdeme práve jeden štvorec (so stranou dĺžky 3), ktorý ho obsahuje. Ak je plusko veľkosti 2, vytvára tak na tabuli dve štvorcové oblasti, ktoré sú pluskami – jedna oblasť je štvorec so stranou dĺžky 5 a druhá oblasť je menší štvorec so stranou dĺžky 3, v strede väčšieho štvorca. Plusko veľkosti 3 nám vytvorí 3 štvorcové oblasti ktoré sú pluskami atď. Trik je v tom, že v tomto riešení dáme každému štvorcu, ktorý je pluskom len jeden bod. Väčšie pluská preto ohodnotíme presne toľkými bodmi, ako si to vyžadovalo zadanie.

#include <iostream>

using namespace std;

char tabula[2000][2000];

int je_stvorec_plusko(int r, int c, int v)
{
    for(int i=0; i<v; ++i)
        for(int j=0; j<v; ++j)
            //ak nie sme v strednom riadku/stĺpci a políčko je popísané
            if(i != v/2 && j != v/2 && tabula[r+i][c+j] == '#')
                return 0;
            //ak sme v strednom riadku/stĺpci a políčko je nepopísané
            else if ( (i == v/2 || j == v/2) && tabula[r+i][c+j] == '.')
                return 0;
    return 1;
}

int main()
{
    int n;
    cin >> n;

    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
            cin >> tabula[i][j];

    int body = 0;
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<n; ++j)
        {
            for(int v=3; i+v<=n && j+v<=n; v+=2)
            {
                body += je_stvorec_plusko(i, j, v);
            }
        }
    }

    cout << body << "\n";
}

Políčok je na tabuli \(n^2\) a dĺžka strany každého štvorca môže byť rádovo až \(n\). Overiť, či je štvorec nepočmárané plus nám v najhoršom prípade trvá toľko krokov ako je jeho obsah, čo je v najhoršom prípade \(n^2\). Dokopy je teda počet krokov zhora ohraničený \(n^2 \cdot n \cdot n^2\), teda časová zložitosť bude \(O(n^5)\).

Pamätať si pritom musíme celú tabuľu, takže potrebná pamäť bude kvadratická v závislosti od rozmeru tabule – \(O(n^2)\).

Riešenie vieme ešte zlepšiť niekoľkými trikmi. O veľa štvorcoch napríklad veľmi rýchlo zistíme, že sú počmárané; vtedy môžeme rovno prestať kontrolovať zvyšok štvorca. Dá sa ukázať, že toto vylepšenie zníži časovú zložitosť na \(O(n^4)\). Takisto sa ľahko môže stať, že veľa štvorcov na tabuli spĺňa jednu z podmienok (každý štvorec na prázdnej tabuli má všetky nie-stredné riadky a stĺpce správne, a každý štvorec na úplne popísanej tabuli má všetky stredné riadky a stĺpce správne). Aby nás takéto vstupy menej trápili, mohli by sme napríklad na začiatok vyskúšať zopár náhodných políčok v strednom riadku/stĺpci a niekoľko náhodných políčok mimo, či naše plusko nekazia. Existuje viacero takýchto podobných vylepšení, ktoré mohli riešenie urýchliť, a získať teda trochu viac bodov na testovacích vstupoch. Napriek tomu takéto optimalizácie väčšinou nemenia časovú zložitosť algoritmu, keďže pri odhade časovej zložitosti uvažujeme ten najhorší možný prípad.

Dá sa to aj múdrejšie?

Vyššie uvedené riešenie sa síce dalo všelijakými ad-hoc trikmi vylepšovať, nevie sa však nijak zbaviť základnej myšlienky, že pre každé z \(n^2\) políčok skúša rádovo \(n\) dĺžok strán štvorcov, a tie (v najhoršom prípade) celé prekontroluje. Pre \(n\) blížiace sa k \(2000\) je teda riešenie príliš pomalé.

Zväčšovanie štvorcov z ľavého horného rohu má principiálne ten problém, že ak zmeníme dĺžku strany štvorca, ktorý chceme overiť, veľa políčok v ňom bude zohrávať inú úlohu. Popísané políčka, ktoré nám pri jednej dĺžke strany zavadzali, môžu byť pri ďalšej dĺžke strany práve tými potrebnými políčkami v strednom riadku alebo stĺpci, a naopak. Kvôli tomu musíme pri zmene dĺžky strany štvorca prakticky všetky políčka znova overovať. Jednoduchšie povedané, vždy keď zmeníme dĺžku strany štvorca ktorý chceme overiť, a vždy keď zmeníme políčko, ktoré skúšame ako ľavý horný roh, zahadzujeme všetku doteraz získanú informáciu, a preto musíme overovať veľa políčok, aby sme zistili, či nový štvorec je alebo nie je nepočmárané plus.

Vieme nejakým spôsobom upraviť náš prvý algoritmus tak, aby sme využili predošlé informácie, ktoré máme z overovania menších štvorcov?

Vieme – stačí si štvorec definovať pomocou súradníc jeho stredného políčka a dĺžky jeho strany. Opäť budeme teda overovať všetky štvorce – najprv si zvolíme stred štvorca \((i, j)\) a potom budeme zväčšovať jeho dĺžku strany \(v = 3, 5, 7, ..., n\). Keď vieme, že štvorec so stranou dĺžky \(v\) je nepočmárané plus, a chceme overiť štvorec so stranou dĺžky \(v+1\), máme už zaručené, že celé “vnútro” je správne, a stačí nám teda overiť “nové” políčka – teda okraje štvorca. Keď ale zistíme, že štvorec je počmárané plusko, všetky väčšie štvorce s týmto stredom budú tiež počmárané a môžeme tak prestať overovať štvorce s týmto stredom.

#include <iostream>

using namespace std;

char tabula[2000][2000];

bool je_stvorec_plusko(int r, int c, int v)
{
    //pozrieme sa či nové políčka v strednom riadku a stĺpci sú popísané
    if(tabula[r+v][c]!='#' || tabula[r-v][c]!='#' || tabula[r][c-v]!='#' || tabula[r][c+v]!='#')
        return false;

    //skontrolujeme či nové vonkajšie riadky a stĺpce sú nepopísané
    for(int i=1; i<=v; ++i)
    {
        if(tabula[r+i][c-v]=='#'||tabula[r+i][c+v]=='#')
            return false;
        if(tabula[r+v][c-i]=='#'||tabula[r+v][c+i]=='#')
            return false;
        if(tabula[r-i][c-v]=='#'||tabula[r-i][c+v]=='#')
            return false;
        if(tabula[r-v][c-i]=='#'||tabula[r-v][c+i]=='#')
            return false;
    }

    return true;
}

int main()
{
    //vstup môže mať až 4,000,000 znakov, zrýchlime načítavanie
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, body = 0;
    cin >> n;

    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
            cin >> tabula[i][j];

    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<n; ++j)
        {
            if(tabula[i][j]=='.') continue;
            //zväčšujeme dĺžku strany o 1 kým rám štvorca so stredom v [i][k] sedí
			int v = 1;
          	while(i+v<n && j+v<n && i-v>=0 && j-v>=0 && je_stvorec_plusko(i,j,v)) ++v;
            body += v-1;
        }
    }

    cout << body << "\n";

    return 0;
}

Ako vieme zatiaľ zhora odhadnúť zložitosť tohto riešenia? Pre každé políčko, ktorých je \(n^2\), máme cyklus ktorý beží (v teoretickom, najhoršom možnom prípade) najviac \(n\)-krát, a zakaždým kontroluje nové políčka štvorca, teda okraj štvorca. Ten má rádovo \(n\) políčok. Dokopy teda dostávame horný odhad \(O(n^2 \cdot n \cdot n) = O(n^4)\).

Pozrime sa na to bližsie

Napriek tomu, že náš odhad \(O(n^4)\) je správny (algoritmus skutočne urobí na tabuli so stranou \(n\) najviac rádovo \(n^4\) operácií), tento odhad nie je tesný. V tejto časti si ukážeme, že v skutočnosti je vyššie popísaný algoritmus omnoho rýchlejší.

Pri políčkach, ktoré nie sú stredom žiadneho nepočmáraného plus, naše overovanie skončí veľmi rýchlo – najneskôr po skontrolovaní prvých deviatich políčok, teda v konštantnom čase. Overovanie takýchto políčok teda dokopy zaberie \(O(n^2)\) času.

Keď skúšame políčko, ktoré je stredom nepočmáraného plus s ramenom \(v\) (ale už nie väčšieho), skontrolujeme štvorec so stranou \(2v+1\), čo nám zaberie \((2v+1)^2\) krokov. Následne ešte skúsime plusko zväčšiť, ale nepodarí sa nám to a prestaneme. V najhoršom prípade teda prejdeme všetky políčka štvorca so stranou \(2v+3\). Dokopy teda urobíme rádovo \(v^2\) krokov.

Inak povedané, ak sú na tabuli pluská veľkostí \(v_1,v_2,...,v_k\) (pričom počítajme len tie najväčsie; nepočítajme tie, ktoré sú v strede väčšieho pluska), na ich overenie bude tento program potrebovať rádovo \({v_1}^2 + {v_2}^2 + ... + {v_k}^2\) krokov.

Teda náš algoritmus vykoná rádovo toľko operácií, koľko je súčet plôch nepočmáraných plusiek na tabuli. Má teda zložitosť opísateľnú ako \(O(n^2 + \mbox{plocha plusiek})\) (\(O(n^2)\) kvôli načítaniu vstupu a políčkam, ktoré nie sú stredom žiadneho pluska). A toto je pre náš algoritmus veľmi prospešné – pluská si totiž, z hľadiska algoritmu, navzájom zavadzajú. Chceme už vlastne len dokázať, že nepočmárané pluská sa nevedia ľubovoľne prekrývať a na tabuli ich teda bude relatívne málo.

Zoberme si teda ľubovolné políčko \((i,j)\). Pozrieme sa naň toľkokrát, do koľkých nepočmáraných plusiek patrí. Ak je na \((i,j)\) znak #, môže to byť buď stred pluska (teda patrí do práve jedného), alebo byť hornou/dolnou stranou stredného stĺpca, resp. ľavou/pravou stranou stredného riadku. V tejto situácii môže zároveň patriť do najviac jedného ďalšieho nepočmáraného pluska.

Na tomto obrázku sú farebne vyznačené tie #, ktoré patria do dvoch nepočmáraných plusiek (a teda náš algoritmus sa na ne pozrie dvakrát). Žiadnu mriežku však ako okraj platného pluska nebude skúšať viac ako dvakrát.

Podobná úvaha platí aj pre nepopísané políčka – každé nepopísané políčko môže patriť do najviac štyroch nepočmáraných plusiek (do ľavej hornej časti jedného, pravej dolnej časti druhého, …).

Na tomto obrázku sú farbene vyznačené tie bodky, ktoré patria do viacerých nepočmáraných plusiek. Pritom všetky patria do práve dvoch plusiek s výnimkou bodky v úplnom strede obrázku, ktorá patrí do všetkých štyroch plusiek.

Keďže pri overovaní jedného pluska sa na každé jeho políčko pozrieme len raz, a každé políčko v najhoršom prípade patrí do štyroch rôznych nepočmáraných plusiek, vyplýva z toho, že na každé políčko tabule sa pri overovaní pozrieme najviac štyrikrát. Políčok je \(n^2\), a teda časová zložitosť je \(O(n^2)\).

Opäť si pamätáme celú tabuľu, teda pamäť je stále \(O(n^2)\)