5. Obytná štvrť vzorové riešenie

2

11
23

6

112111
234521
111321
112311
121311
111211

Úloha sa dala riešiť nasledujúcimi troma nástrojmi (prípadne kombináciou týchto nástrojov). Počty bodov, ktoré sa dali získať, sú len odhadované a dosť záviseli od šikovnosti a množstva času venovaného tejto úlohe.

1. Použitím ceruzky a papiera sa dalo získať 7 až 9 bodov z 12.
2. Využitím počítača na prechádzanie všetkých možností a automatizovanie manuálnej roboty sa dalo získať 9 až 11 bodov.
3. Využitím počítača a programov špecializovaných na rýchle riešenie optimalizačných úloh, sa dalo získať 10 až 12 bodov.

Bez ohľadu na to, ktorý nástroj použijeme, ak chceme získať veľa bodov, tak postup riešenia bude vyzerať približne takto:

1. Malé plány (s rozmermi do 8) vyriešime samostatne.
2. Následne vymyslíme čo najlepší spôsob, ako vyrobiť nekonečne veľký plán mesta. Teda odmyslíme si okraje a skúsime nájsť nejaký plán – nejakú “kachličku” – ktorú môžeme ľubovoľne veľa krát ukladať veľa seba a pod seba, a stále bude spĺňať podmienky zo zadania. Budeme sa snažiť dosiahnuť čo najvyššiu priemernú výšku kachličky.
3. Veľké plány mesta vyrobíme tak, že naukladáme vedľa seba niekoľko kópií kachličiek a pridáme okraje plánu.

Malé plány

Takto vyzerajú optimálne riešenia pre \(n \in \{3,5,8\}\) aj so súčtom výšok budov.

20          170
241         12413231
132         14324152
241         25135241
            43251432
63          11342514
23131       24515323
14523       13234131
42314       24142142
31452
21231

Prvé dva sa dajú nájsť ručne alebo inteligentným skúšaním všetkých možností na počítači. Pre \(n=8\) vieme bezbolestne ručne/pomocou počítača nájsť riešenie s počtom poschodí medzi \(160\) a \(166\), ale na optimum treba trocha väčšie kladivo.

Väčšie kladivo môže byť napríklad nejaký heuristický algoritmus – to je taký, ktorý síce nemusí vždy dosiahnuť najlepší výsledok, ale väčšinou sa mu to podarí a navyše je veľmi rýchly. Ako príklady uvedieme simulované žíhanie, genetické programovanie alebo hillclimbing, viac si o nich môžete nájsť na internete, ale konkrétne v tejto úlohe pravdepodobne nebudú veľmi úspešné.

Lepšie je použiť ILP, Integer Linear Programing, čiže celočíselné lineárne programovanie, o ktorom si podrobnejšie môžete prečítať v zadaní 5. príkladu 4. série, 31. ročníka (old.ksp.sk/wiki/uploads/Zadania/ps314.pdf). Pointa je v tom, že úlohu zapíšeme ako skupinu podmienok a výraz, čo chceme maximalizovať, v špecifickom formáte. Táto skupina podmienok a výraz sa nazýva celočíselný lineárny program. Potom na internete dokážeme nájsť nástroje, ktoré vedia hľadať optimálne riešenia pre takéto programy. Ako dobré cvičenie si môžete naštudovať ILP z vyššie uvedeného odkazu alebo inú heuristickú metódu a pomocou nej vytvoriť čo najlepší plán mesta. V tomto vzorovom riešení sa však uspokojíme s 10 bodmi za program a ďalej sa týmto sofistikovaným nástrojom nebudeme venovať.

Inteligentné skúšanie všetkých možností.

Zlé skúšanie možností je nasledovné: Pre každé políčko máme \(5\) možností aká budova tam môže byť, takže vygenerujeme všetkých \(5^{n^2}\) rôznych miest. Overíme, ktoré z miest vyhovujú podmienkam zo zadania, a vyberieme z nich najlepšie (podľa počtu poschodí).

Riešenie by sa najjednoduchšie implementovalo tak, že plochu budeme generovať po jednotlivých políčkach rekurzívne. Teda si spravíme funkciu vygeneruj(x,y), ktorá vyskúša všetkých \(5\) možností čo môže byť na políčku x,y a pre každú možnosť zavolá vygeneruj(nasledujúce políčko po x,y). Nech x je číslo riadku a y číslo stĺpca. Riadky aj stĺpce číslujeme od 1 po n. Keď chceme políčka prechádzať po riadkoch, tak nasledujúce políčko po x,y má súradnice x + y/n, y mod n + 1. Keď sa takto dostaneme na riadok n+1, tak sme vygenerovali celú plochu a ostáva nám overiť, či vyhovuje zadaniu. Keďže pre každé políčko sme skúsili všetky možné výšky, nestane sa nám, že by sme na nejaký plán zabudli.

vygeneruj(x, y):
    pokiaľ y>n:
        pokiaľ Plocha vyhovuje zadaniu a má zatiaľ najväčší počet poschodí:
            aktualizuj najlepšie riešenie
        koniec
    pre i od 1 do 5:
        Plocha[x][y] = i
        vygeneruj(x + y/n, y%n + 1)

vygeneruj(1,1)
vypíš najlepšie riešenie

Prečo je toto zlé? Lebo je to pomalé a veľa roboty sa robí zbytočne. Už pre \(n = 4\) by výpočet trval asi hodinu. A pre \(n = 5\) by sme sa nedočkali výsledku ani do konca roka. Skúsime to teda zlepšiť.

Pri inteligentnom skúšaní všetkých možností musíme priebežne kontrolovať, či vôbec má zmysel pokračovať ďalej. Pokiaľ napríklad prvé dve budovy budú \(5\) a \(5\), tak už nemá zmysel skúšať, ako by vyzeral zvyšok mesta, pretože určite nebude vyhovovať zadaniu.

vygeneruj(x, y):
    pokiaľ y>n:
        skontroluj Plochu a prípadne aktualizuj najlepšie riešenie
        koniec
    skontroluj Plochu, či ma zmysel pokračovať
    ak nemá zmysel pokračovať:
        koniec
    pre i od 1 do 5:
        Plocha[x][y] = i
        vygeneruj(x + y/n, y%n + 1)
        Plocha[x][y] = 0

Čím lepšie naprogramujeme funkciu na kontrolu, tým menej možností bude program skúšať. Jednoduchá kontrola, ktorá veľmi pomôže, je prejsť všetky nenulové políčka v poli Plocha a pre každé z nich overiť, či by sa dali doplniť okolité nuly tak, aby malo políčko okolo seba všetky menšie čísla (tak ako to káže zadanie). Celá kontrola sa dá implementovať v čase \(O(n^2)\). Konkrétnu implementáciu si môžete pozrieť na spodku tohoto vzorového riešenia.

Trocha času sa dá ušetriť aj zvolením si vhodného programovacieho jazyka, napríklad C++ je asi desaťnásobne rýchlejšie než Python.

Nekonečne veľký plán mesta

Chceli by sme mať čo najvyššie budovy, ale celé nám to kazia okraje, lebo budovy na okraji majú málo susedov. Keby sme povedali, že budovy úplne vľavo susedia s tými úplne v pravo a budovy v prvom riadku susedia s budovami v spodnom riadku, mohli by sme dosahovať plány s oveľa lepším skóre.

Napríklad plán

1323
2414
1525

má priemernú výšku budovy \(2.75\). (Pre porovnanie, optimálny plán pre \(5\times 5\) podľa pôvodných pravidiel, mal priemernú výšku \(2.52\)). Keď sa potrápime trocha viac, nájdeme optimálny plán s rozmermi \(5\times 5\) (s tým, že protiľahlé okraje susedia):

12345
45123
23451
51234
34512

Tento plán má priemernú výšku \(3\). Ukladaním takejto “kachličky” ľubovoľne veľakrát pod seba a vedľa seba vieme vytvoriť nekonečnú plochu s priemernou výškou \(3\). Aby sme nemuseli hľadať ďalšie plány, ukážeme si, že lepšia priemerná výška sa nedá dosiahnuť.

Horné ohraničenie

Každá budova, ktorá nemá \(1\) podlažie, musí susediť s jednopodlažnou budovou. Jedna jednopodlažná budova môže susediť s najviac \(4\) ďalšími budovami, inými slovami, jedna jednopodlažná budova dovolí najviac štyrom budovám mať viac poschodí. Z toho vyplýva, že aspoň jedna pätina všetkých budov je jednopodlažná.

Podobne dvojpodlažná budova môže mať okolo seba najviac \(3\) vyššie budovy (lebo musí mať vedľa aspoň jednu jednopodlažnú). Preto aspoň štvrtina z budov, ktoré nie sú jednopodlažné, sú dvojpodlažné. Analogicky ukážeme, že aspoň tretina zo zvyšných budov sú trojpodlažné a aspoň polovica zo zvyšku je štvorpodlažná.

Jednoduchou matematikou môžeme spočítať, že priemerná výška budov potom nemôže byť viac ako tri.

Skladanie veľkých konečných plôch

Po tom, ako sme našli “kachličku” \(5\times 5\), môžeme nadobudnúť presvedčenie, že najlepší plán mesta pre veľké \(n\) bude vyzerať zhruba takto:

????????????????...?
?123451234512345   ?
?451234512345123   ?
?234512345123451...?
?512345123451234   ?
?345123451234512   ?
.       .          .
.       .          .
.       .          .
????????????????...?

Avšak rýchlo zistíme, že v druhom stĺpci a piatom riadku nemôže byť päťposchodová budova, pretože v prvom stĺpci by musela byť štvorka, ktorá by nevedela mať okolo seba \(1\), \(2\) aj \(3\). Preto skutočný plán mesta by vyzeral takto (rozdiel je len v druhom stĺpci):

????????????????...?
?123451234512345   ?
?451234512345123   ?
?234512345123451...?
?412345123451234   ?
?345123451234512   ?
.       .          .
.       .          .
.       .          .
????????????????...?

Alebo sa nám možno oplatí nezačať číslom \(1\) ale spraviť druhý riadok 234512345..., 345123451..., 451234512... či 512345123...

A program by už len mal uhádnuť, aké výšky budov sú schované pod otáznikmi. Pre veľké \(n\) to môže byť stále veľa možností, tak sa môžme obmedziť len na okraje, ktoré sa periodicky opakujú. Teda \(10\)-te číslo v prvom riadku musí byť rovnaké ako \(5\)-te číslo v prvom riadku.

Za týchto podmienok je možností dostatočne málo na to, aby náš program, ktorý skúša všetky možnosti, bežal len chvíľu.

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define REP(i, n) for(int i = 0; i<int(n); ++i)
#define FOR(i, n) for(int i = 1; i<=int(n); ++i)
typedef vector<int> vi;

int n, best, sum;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
vector<vi> M,Naj,V; // Mapa, Najlepsia mapa, Vynimky
int vedla[7] = {0};

// skontrolujeme, ci mapa vyhovuje podmienkam zo zadania
bool spravne(){
    FOR(i, n) FOR(j, n){
        if (M[i][j] <= 0) continue;
        FOR(d, 6) vedla[d] = 0;
        REP(d, 4) vedla[M[i+dx[d]][j+dy[d]]+1]++;
        FOR(d, M[i][j]-1) if (!vedla[d+1]) vedla[1]--;
        if (vedla[1] < 0) return false;
    }
    return true;
}

// kolko mam pripocitat na poziciu x,y 
// (meni to cisla 5 v druhom stlpci na cisla 4)
int vynimka(int x, int y){
    if (y>3) return 0;
    if (y==2 && M[x-1][y] == 2) {
        V[x][y] = 1;
        return -V[x][y];
    }
    return max(V[x][y-1],V[x-1][y]);
}

// toto makro trocha skratilo zdrojovy kod
#define VYGENERUJ(d, p, q) {\
    M[x][y]=d;\
    if (p)\
        vygeneruj(x+y/n, y%n+1);\
    V[x][y] = M[x][y]=0;\
    q\
}

// vygeneruj dalsie policko (na pozicii x,y)
void vygeneruj(int x, int y){
    if (x>n) {
        if (!spravne()) return;
        sum = 0;
        FOR(i, n) FOR(j, n) sum+=M[i][j];
        if (sum>best){
            best = sum;
            Naj = M;
        }
        return;
    }
    // cela mapa je dost periodicka, takze vacsinou vieme
    // urcit hotnotu na zaklade predoslych
    if (x-5>1 && x<n) VYGENERUJ(M[x-5][y], true, return;)
    if (y-5>2 && y<n) VYGENERUJ(M[x][y-5], true, return;)
    if (x>1 && x<n && y>1 && y<n) {
        if (y>2) VYGENERUJ((M[x][y-1]+vynimka(x,y))%5+1, true, return;)
        if (x>2) VYGENERUJ((M[x-1][y]+2+vynimka(x,y))%5+1, true, return;)
    }
    // v opacnom pripade skusime vsetkych 5 moznosti, ale vzdy kontrolujeme,
    // ci ma zmysel pokracovat
    FOR(d, 5) {
        VYGENERUJ(d, spravne(), ;)
    }
}

int main(){
    scanf("%d", &n);
    Naj = M = vector<vi>(n+2, vi(n+2, -1));
    V = vector<vi>(n+2, vi(n+2, 0));
    FOR(i, n) FOR(j, n) M[i][j] = 0;
    
    vygeneruj(1,1);
    FOR(i, n) {
        FOR(j, n) printf("%d", Naj[i][j]);
        printf("\n");
    } 
}

Tento program vstupy s \(n\) do \(5\) rieši optimálne, pri \(n = 8\) a \(n = 13\) sa mu veľmi nedarí, ale pri vyšších \(n\) je veľmi blízky najlepšiemu vedúcovskemu riešeniu. (V najhoršom prípade dosahuje o \(3\) poschodia menej ako najlepšie riešenie.) Nie je úplne najrýchlejší takže na výsledok si budeme musieť počkať asi pol hodinu.

No a ako dostať viac bodov? Naše riešenia skúšalo doplniť len okraj veľkosti jedna a ten okraj navyše musel byť periodický. Keď skúsime okraj veľkosti dva alebo tri a dovolíme robiť aj neperiodické okraje, dosiahneme lepšie výsledky. Aby sme sa dočkali výsledku do konca série, musíme použiť nejaké z väčších kladív, ktoré sme spomínali v prvej časti vzoráku.

My sme použili ILP, pre \(n\) do \(13\) sa stíhal okraj veľkosti \(3\), pre vyššie \(n\) okraj veľkosti \(2\). Počty poschodí najlepších plánov boli postupne \(7\), \(20\), \(63\), \(170\), \(467\), \(1249\), \(3342\), \(8863\), \(23416\) a \(61640\).