6. Egyptské pyramídy vzorové riešenie

3 7

9

12 23

1

7 20

397944

Zopakujme si zadanie úlohy. Máme spočítať počet pyramíd, ktoré majú \(h\) poschodí, vrchné je veľkosti \(1\times 1\), spodné \(x\times x\) a poschodia medzi sú “takmer štvorce”, teda ich šírka a dĺžka sa nelíši o viac ako 3. Navyše sa poschodia postupne od spodu zužujú, presnejšie, šírka aj výška každého poschodia je aspoň o 2 menšia ako poschodia priamo pod ním.

Vždy, keď riešime problém s počítaním možností mali by sme sa zamyslieť, či nevieme využiť dynamické programovanie. Pri tejto technike si najskôr sformulujeme problém a následne skúšame vypočítať jeho riešenie na základe jemu podobných podproblémov.

Nie vždy je vhodné si ako problém zobrať úlohu zadania, skôr by malo platiť, že pomocou zvoleného problému vieme ľahko na zadanie odpovedať. V tomto prípade je to však pomerne ľahké a priamo zo zadania vyplýva nasledovná otázka: Koľkými spôsobmi vieme postaviť korektnú pyramídu výšky \(n\), ktorej spodné poschodie má veľkosť \(w\times h\)?

Keďže pyramídy nemusia mať vždy štvorcové podstavy, problém sme si trochu zovšeobecnili na podstavy \(w \times h\). Stále však vieme ľahko odpovedať na pôvodnú otázku, stačí, keď nastavíme \(w = x\) a \(h = x\).

Ďalším krokom je zistiť, či vieme na túto otázku odpovedať pomocou výsledkov pre jednotlivé podproblémy. Čo to vlastne ten podproblém je? Je to pôvodná otázka, do ktorej dosadíme iné, menšie parametre. Teda napríklad, koľko je pyramíd výšky \(n-1\) s veľkosťou základne \(4\times 3\). Aby sme nemuseli našu otázku vždy rozpisovať, označme si počet pyramíd výšky \(n\) so základňou \(w \times h\) ako \(P(n, w, h)\).

Náš pôvodný problém je nájsť hodnotu \(P(n, x, x)\). Ako takéto pyramídy vyzerajú? Ich spodné poschodie je veľké \(x \times x\) a potom sú tam poukladané zvyšné poschodia. Tieto zvyšné poschodia však tvoria korektnú pyramídu výšky \(n-1\). Jediné čo nevieme je, akú podstavu tieto menšie pyramídy majú. Uvedomme si však, že napríklad, každú pyramídu výšky \(n-1\), ktorej podstava je \((x-2) \times (x-2)\) vieme postaviť na poschodie \(x \times x\) a dostať tak pyramídu, ktorú hľadáme. Tým pádom, hodnota \(P(n, x, x)\) obsahuje všetky možnosti \(P(n-1, x-2, x-2)\).

A to je už skladanie podproblémov. Vidíme, že ak vypočítame \(P(n-1, x-2, x-2)\), táto hodnota nám pomôže pri výpočte hľadaného \(P(n, x, x)\). No ale \(P(n-1, x-2, x-2)\) je ten istý problém, len trochu menší, na jeho riešenie preto môžeme použiť ten istý postup. A to je základnou myšlienkou dynamického programovania.

Ak chceme vypočítať \(P(n, x, x)\), musíme zistiť, aké všetky pyramídy veľkosti \(n-1\) vieme položiť na poschodie \(x \times x\). Ich výšku poznáme, stačí teda skúsiť všetky možnosti pre podstavu. Z toho plynie nasledovný jednoduchý program. Odporúčam si ho prečítať, ak ste sa s dynamickým programovaním ešte nestretli. Pekne ukazuje, aká jednoduchá je to technika, keď si položíte správnu otázku.

#include <cstdio>
#include <algorithm>
using namespace std;

int MOD = 1000000;
int Mem[300][700][700];

// počet pyramíd výšky n, ktorých podstava je veľká w krát h
int P(int n, int w, int h) {
    // skontroluj najjednoduchšie prípady a už zapamätané riešenia
    if(n == 1 && w == 1 && h == 1) return 1;
    if(n == 1) return 0;
    if(w <= 0 || h <= 0) return 0;
    if(Mem[n][w][h] != -1) return Mem[n][w][h];
    // vyskúšaj všetky možné podstavy
    int res = 0;
    for(int i = 0; i < w-1; i++)
        for(int j = 0; j < h-1; j++) {
            if(abs(i-j) > 3) continue; // skontroluj, či je to takmer štvorec
            res += P(n-1, i, j);
        }
    return Mem[n][w][h] = (res % MOD);
}

int main() {
    int n,x;
    scanf("%d %d",&n,&x);
    // nastavím pole Mem na -1 - nič ešte nemáme spočítané
    for(int i=0; i<300; i++)
        for(int j=0; j<700; j++)
            for(int k=0; k<700; k++)
                Mem[i][j][k] = -1;
    
    printf("%d\n",P(n,x,x));
}

Vo vyššie uvedenom programe si všimnite dve dôležité veci. Jednak, naša rekurzia musí mať ukončenie. To je väčšinou určené podproblémom, ktorý vieme vyriešiť ručne. V našom prípade pyramída výšky 1 s podstavou \(1 \times 1\), ktorá je naozaj len jedna. Takisto si však treba dať pozor na prípady, ktoré už k riešeniu nevedú. Druhým pozorovaním je, že aby sme dookola nepočítali tie isté veci, pamätáme si už vypočítané výsledky v poli Mem[]. Táto technika sa volá memoizácia a výrazne zrýchľuje väčšinu rekurzívnych funkcií. Naozaj jediné čo s Mem[] robíme je, že si do tohto poľa vkladáme vypočítané hodnoty a ak sa pýtame na niečo, čo už máme zapamätané, vrátime namiesto toho túto hodnotu.

Aká je časová zložitosť nášho programu. Pri takomto type rekurzií sa to v skutočnosti odhaduje pomerne ľahko. Stačí zistiť koľko rôznych podproblémov môžeme riešiť a ako dlho nám trvá riešenie jedného z nich. Možných podproblémov je \(n \cdot x \cdot x\) – všetky možnosti pre výšku, šírku a dĺžku pyramídy. Výpočet jednej možnosti je pritom \(x \cdot x\), pretože musíme vyskúšať všetky možnosti pre šírku a dĺžku podstavy o poschodie vyššie. Celková zložitosť je preto \(O(nx^4)\).

Zapojenie “takmer štvorcov”

Naše riešenie je príliš pomalé, je však zrejmé, že to tak vôbec nemusí byť a veľa vecí sme si zbytočne zjednodušili. Napríklad sme nijak nevyužili fakt, že jednotlivé poschodia musia byť takmer štvorce. Skúšame preto úplne zbytočné možnosti ako \(P(10, 9, 3)\). Síce vieme spočítať počet takýchto pyramíd, ale na čo nám sú, ak podstavu \(9 \times 3\) nikdy nevieme použiť? Toto platí o rekurziách a dynamikách aj všeobecne. Keď sa ich snažíme zrýchliť, vždy si treba klásť otázku, či niečo nepočítame dvakrát, poprípade zbytočne.

Zapojenie takmer štvorcov ovplyvňuje dve miesta v kóde – počítanie možných podstáv pre nižšie pyramídy a samotný počet a tvar podproblémov. Začnime tým prvým. V predchádzajúcom riešení sme pre pyramídu výšky \(n-1\) skúšali všetky možné šírky a dĺžky pre podstavu. My však vieme, že ich rozdiel môže byť najviac 3. Ako v riešení vyskúšať všetky takéto veľkosti? Uvedomme si, že stále chceme skúšať každú možnú šírku, k danej šírke však už neskúšame všetky dĺžky, ale iba tých 7 zaujímavých – o 3 menšiu až o 3 väčšiu ako šírka. Toto zrýchli počítanie možností na \(O(x)\), keďže 7 je iba malá konštanta.

Druhú úpravu musíme spraviť priamo vo formáte podproblému, nechceme počítať a vôbec dovoľovať podproblémy, ktoré nás nezaujímajú. Jeden z dôvodov je napríklad aj ten, že sa nám tým zmenší veľkosť nášho poľa Mem[], čo je dôležité, pretože vytvoriť pole nejakej veľkosti trvá rovnako veľa času. Ak by sme teda tieto podproblémy nepočítali, ale mali by sme pre ne vytvorené miesto v pamäti, vôbec by sme si nepomohli. Náš problém si preto preformulujeme na Koľkými spôsobmi vieme postaviť korektnú pyramídu výšky \(n\), ktorej spodné poschodie má šírku \(w\) a dĺžku o \(dx\) inú? Pričom samozrejme \(dx\) môže mať iba hodnoty \(-3\) až \(3\).

Ako sa zmenila časová zložitosť našeho riešenia? Počet podproblémov je už iba \(n \cdot 7x\) – určíme si výšku, šírku a dĺžka už môže mať iba jednu zo 7 možností na základe šírky. A jeden podproblém vypočítame v čase \(7x\) – skúsime každú šírku a iba 7 okolitých dĺžok. Výsledné riešenie má teda zložitosť \(O(n \cdot x^2)\).

K implementácii tohto riešenia ešte dodajme, že je ťažké si pole indexovať zápornými číslami, preto \(dx\) nebude nadobúdať hodnoty \(-3\) až \(3\) ale \(0\) až \(6\). Počet hodnôt je rovnaký, sú kladné, je však na nás, aby sme sa v nich nedoplietli a správne ich používali.

#include <cstdio>
#include <algorithm>
using namespace std;

int MOD = 1000000;
int Mem[2000][5000][7];

// počet pyramíd výšky n, ktorých podstava je veľká w krát w+dx-3
int P(int n, int w, int dx) {
    int h = w + dx - 3;
    // skontroluj najjednoduchšie prípady a už zapamätané riešenia
    if(n == 1 && w == 1 && dx == 3) return 1;
    if(n == 1) return 0;
    if(w <= 0 || h <= 0) return 0;
    if(Mem[n][w][dx] != -1) return Mem[n][w][dx];
    // vyskúšaj všetky podstavy tvaru takmer štvorca
    int res = 0;
    for(int i = 0; i < w-1; i++)
        for(int j = -3; j < 4; j++) {
            if(h - (i + j) < 2) continue;
            res += P(n-1, i, j + 3);
        }
    return Mem[n][w][dx] = (res % MOD);
}

int main() {
    int n,x;
    scanf("%d %d",&n,&x);
    // nastavím pole Mem na -1 - nič ešte nemáme spočítané
    for(int i=0; i<2000; i++)
        for(int j=0; j<5000; j++)
            for(int k=0; k<7; k++)
                Mem[i][j][k] = -1;
    
    printf("%d\n", P(n,x,3));
}

Rýchlejšie počítanie jedného podproblému

Predchádzajúce riešenie však stále nie je dostatočne rýchle. Nie je však veľa vecí, ktoré by sme vedeli zmeniť. Počet podproblémov už veľmi nezmeníme, predsa len, musíme si pamätať výšku a veľkosť základne. To znamená, že treba zrýchliť výpočet jedného podproblému. Pri aktuálnom riešení postupne skúšame všetky o jedno nižšie pyramídy, ktoré sa zmestia na zadanú podstavu. Bohužiaľ, my poznáme odpoveď iba pre konkrétnu veľkosť podstavy a preto musíme robiť všetky tie skúšania. Čo by sa ale stalo, keby sme namiesto toho vedeli odpovedať na nasledovný problém: Koľkými spôsobmi vieme postaviť korektnú pyramídu výšky \(n\), ktorej spodné poschodie je nanajvýš \(w\) široké a \(w + dx\) dlhé? Označme si túto hodnotu \(T(n, w, dx)\). Potom predsa platí, že \(P(n, w, dx) = T(n-1, w-2, dx)\), pretože sa viem rovno dozvedieť počet pyramíd, ktoré viem dať na podstavu \(w \times (w + dx)\).

No dobre, ale pomohli sme si vôbec? Lebo sme si iba vytvorili nový dynamický problém, ktorý však stále potrebujeme vedieť vypočítať. Ako však uvidíme, vyriešiť tento problém je o niečo jednoduchšie. Takže ešte raz, hľadáme počet pyramíd výšky \(n\), ktorých podstava je nanajvýš \(w \times (w+dx)\). Medzi ne určite patria pyramídy, ktorých podstava je presne takto veľká. A tých vieme, že je \(T(n-1, w-2, dx)\). Následne už len potrebujeme pripočítať pyramídy, ktorých podstava je menšia. Menšia môže byť v šírke alebo dĺžke. Čo keby ich šírka bola najviac \(w-1\)? Potom počet takýchto pyramíd je \(T(n, w-1, dx+1)\) – sú vysoké \(n\) poschodí, ich šírka je \(w-1\) a ich dĺžka je rovnaká ako pred tým, čo spôsobí, že \(dx\) sa zväčší o 1 (lebo \(w\) sa o 1 zmenšilo). A keď chceme pyramídy, ktoré majú kratšiu dĺžku, dostaneme hodnotu \(T(n, w, dx-1)\). No a hodnoty \(T()\) zahŕňajú všetky nanajvýš takto veľké pyramídy, nemusíme preto skúšať všetky možné veľkosti podstavy.

Toto avšak nie je všetko, musíme si uvedomiť chybu v našom riešení. Hodnoty \(T(n, w-1, dx+1)\) a \(T(n, w, dx-1)\) obsahujú totiž niekoľko rovnakých pyramíd. Presnejšie, každá pyramída výšky \(n\), ktorej podstava je nanajvýš \((w-1) \times (w+dx-1)\) spadá pod obe tieto čísla, pretože takto veľké podstavy sú rovnako nanajvýš veľké ako podstavy \((w-1) \times (w+dx)\) a aj podstavy \(w \times (w+dx-1)\). No dobre, ale tieto pyramídy sú práve pyramídy \(T(n, w-1, dx)\) a ak sme ich započítali dvakrát, tak ich potrebujeme raz odpočítať. To nás dostáva k výslednému vzorcu:

\[T(n, w, dx) = T(n-1, w-2, dx) + T(n, w-1, dx+1) + T(n, w, dx-1) - T(n, w-1, dx)\]

Malá poznámka na záver. Tento vzorec je dobrý, ale občas nemusí byť úplne pravidvý. Totiž podstavy \((w-1) \times (w+dx)\) nemusia už byť platné, lebo ich rozdiel je priveľký. V takom prípade túto hodnotu nepripočítavame, čím nám nevzniknú duplikáty a teda nechceme ani odčítavať \(T(n, w-1, dx)\). To sú však skôr implementačné detaily, na ktoré si treba dať pozor, keď sa však budete zamýšľať nad tým, čo píšete a čo tie veci znamenajú, ľahko sa im vyhnete.

Vo výsledku hodnoty \(P()\) ani nepotrebujeme počítať, celú úlohu vieme vyriešiť pomocou hodnôt \(T()\). A aká je zložitosť? Počet podproblémov \(T()\) je stále \(n \cdot 7x\). Akurát ich počítanie sa zrýchlilo, pretože nám stačí vypočítať vyššie uvedený vzorec, čo trvá konštantne veľa času. Celková časová zložitosť je \(O(nx)\). Pamäťová zložitosť je totožná počtu podproblémov, teda tiež \(O(nx)\). Túto by sme vedeli síce zmenšiť, ak by sme použili dynamické programovanie namiesto rekurzie s memoizáciou, takéto riešenie však nebolo vyžadované.

#include <cstdio>
#include <algorithm>
using namespace std;

int MOD = 1000000;
int Mem[2000][5000][7];

// počet pyramíd výšky n, ktorých podstava je nanjvýš veľká w krát w+dx-3
int T(int n, int w, int dx) {
    int h = w + dx - 3;
    // skontroluj najjednoduchšie prípady a už zapamätané riešenia
    if(n == 1 && w >= 1 && h >= 1) return 1;
    if(w <= 0 || h <= 0) return 0;
    if(Mem[n][w][dx] != -1) return Mem[n][w][dx];
    // spočítaj možné pyramidy
    int res = T(n-1, w-2, dx);
    bool t = true;
    if(abs(w-1-h) <= 3) res += T(n, w-1, h-(w-1)+3);
    else t = false;
    if(abs(w-h+1) <= 3) res += T(n, w, (h-1)-w+3);
    else t = false;
    // ak som zarátal duplikáty
    if(t) res -= T(n, w-1, dx);
    return Mem[n][w][dx] = ((res%MOD + MOD) % MOD);
}

int main() {
    int n,x;
    scanf("%d %d",&n,&x);
    // nastavím pole Mem na -1 - nič ešte nemáme spočítané
    for(int i=0; i<2000; i++)
        for(int j=0; j<5000; j++)
            for(int k=0; k<7; k++)
                Mem[i][j][k] = -1;
    
    printf("%d\n",T(n-1, x-2, 3));
}