Zadanie

Romanko, ako správny maturant, využil Vianočné prázdniny naplno. Posledný týždeň školy mu síce všetci učitelia pripomínali, ako dôležité je sa cez prázdniny venovať štúdiu, ale však čo – na to bude dosť času neskôr – pred Vianocami sa predsa ide nakupovať! No a po Vianociach si predsa tiež Romanko nebude kaziť náladu školou. Oveľa príjemnejšie je cez deň spať a v noci hrať počítačové hry. A po Silvestri? To je predsa perfektný týždeň na lyžovačku!

Na konci prázdnin si teda Romanko po veľmi “produktívne” strávenom čase pozrel, aké domáce úlohy to vlastne cez ne mal stihnúť. Otvoril si svoj zápisníček a so zhrozením zistil, že je tam práce skoro na tri týždne (aká to náhoda, všakže?). Najťažšou úlohou je veľký projekt z informatiky. Čo teraz bude robiť? Ak svoj projekt z informatiky nespraví, bude mať len dve možnosti: odísť zo školy a zamestnať sa ako vývojár webových stránok, alebo dajako uprosiť svoju učiteľku informatiky, aby ho nechala prejsť s odretými ušami. V momentálnom stave však, napriek Romankovým vynikajúcim presvedčovacím schopnostiam, jeho projekt určite stačiť nebude.

Romanko si však spásonosne spomenul, že kedysi, keď namiesto vypracovávania dôležitých esejí riešil programátorské úlohy na SPOJi, mu pán profesor Demáček za každú vyriešenú úlohu napísal na vyvesenú tabuľu malé, bezvýznamné plus. Tieto pluská ale občas neboli vôbec malé (čím ťažšiu úlohu Romanko vyriešil, tým väčšie plus mu profesor napísal) a nemuseli by byť ani bezvýznamné – mohol by predsa svoju učiteľku presvedčiť, aby mu ich uznala ako bonusové body z programovania!

Utekal teda do Školského Výpočtového Laboratória a uprel pohľad na tabuľu s pluskami. Och, nie! Nejaký darebák ju nenávratne počmáral. Čo bude teraz robiť? Počmárané pluská mu učiteľka v žiadnom prípade neuzná! So slzami na krajíčku a niektorými cezeň si skleslo sadol na zem a prehodnocoval svoje životné rozhodnutia. Našťastie ste práve okolo Romanka išli vy. Vypočuli ste si jeho príbeh, a dali ste mu návrh – ak vám dá zvyšné horalky, ktoré ušetril pri podplácaní trpaslíkov, tak mu pomôžete spočítať, koľko plusiek ostalo na tabuli nepočmáraných. Romanko samozrejme nemal príliš na výber, a pristúpil na vaše podmienky.

Úloha

Tabuľa v Školskom Výpočtovom Laboratóriu je štvorcová a má stranu dĺžky \(n\) milimetrov. Pre potreby úlohy si ju vieme predstaviť ako mriežku pozostávajúcu z \(n\) riadkov. V každom riadku je \(n\) štvorčekových políčok o veľkosti \(1 \times 1\) milimeter a každé z týchto políčok môže byť popísané alebo nepopísané.

Nepočmárané plus veľkosti \(v\) je štvorec so stranou dĺžky \(2v + 1\) milimetrov, v ktorom je celý stredný riadok a stredný stĺpec popísaný, a všetky ostatné políčka v ňom sú nepopísané.

Za nepočmárané plus veľkosti \(v\) dostane Roman \(v\) bonusových bodov.

Každé nepočmárané plus veľkosti aspoň 2 obsahuje vo svojom strede menšie nepočmárané pluská. Za tieto menšie pluská však Roman už ďalšie body pochopiteľne nedostane.

Roman vám ukázal počmáranú tabuľu. Pomôžte mu zistiť, koľko bonusových bodov vie získať!

Formát vstupu

V prvom riadku je číslo \(n (1 \leq n \leq 2\,000)\) – veľkosť tabule. Nasleduje \(n\) riadkov, každý presne \(n\) znakov dlhých – obrázok tabule. Znak '#' predstavuje popísané políčko, znak '.' nepopísané políčko.

Formát výstupu

Vypíšte jediné číslo – počet bonusových bodov, ktoré Roman vie získať, a znak nového riadku.

Príklad

Input:

3
.#.
###
.#.

Output:

1

Takto vyzerá nepočmárané plus veľkosti 1. Romanko zaň dostane 1 bonusový bod.

Input:

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

Output:

3

V pravom dolnom rohu je nepočmárané plus veľkosti 1. Štvorec s ľavým horným rohom na druhom políčku druhého riadku a s pravým dolným rohom na 6. políčku 6. riadku je nepočmárane plus veľkosti 2. Romanko teda vie získať najviac \(1+2=3\) body.

Štvorec s rohmi na políčkach \((1,1)\) a \((7,7)\) je počmárané plus, keďže v pravom dolnom rohu mu zavadzajú popísané políčka menšieho pluska.

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)\)

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.