Zadanie

Nie je tomu tak dávno, čo sa lokálny magnát (volajme ho M) rozhodol odkúpiť od mesta nejaké paneláky a zrekonštruovať byty v nich. Samozrejme, najlepší spôsob, ako s takýmto biznisom začať, je podať si grant. Ako to už však chodí, na získanie grantu potrebujete splniť absurdné požiadavky. Ani tentoraz nedošlo k výnimke a magnát M sa musel popasovať hneď s niekoľkými:

  • Počet kúpených panelákov musí byť práve \(k\).

  • Paneláky sa musia nachádzať v štvrti, kde sú budovy usporiadané do štvorčekovej siete, teda všetky majú rovnako veľký, štvorcový pôdorys.

  • Všetky kúpené paneláky spolu musia susediť stenami.

  • Čím je stavba nižšia, tým viac je ekologická a teda vhodnejšie vyvažuje charakter mesta.

  • Mačka musí mať štyri nohy a nestrká sa do mikrovlnky.

Aj magnátovi M chvíľu trvalo, kým pochopil, o čo sa tu jedná. Zistil, že úradníci si od neho vyúčtujú ekologický poplatok, na základe toho, akú najvyššiu budovu bude rekonštruovať.

Jeho cieľom je teda splniť všetky podmienky a zároveň spraviť čo najvýhodnejší biznis – vybrať si takých \(k\) bytoviek, že vytvoria súvislú oblasť a najvyššia budova medzi nimi je čo najnižšia (medzi všetkými takýmito oblasťami).

Úloha

Dostanete číslo \(k\) a mriežku čísel s \(r\) riadkami a \(s\) stĺpcami.

Hovoríme, že oblasť mriežky je súvislá, ak sa vieme z každého jej políčka dostať na každé iné políčko oblasti len prechodmi smermi hore, dole, vpravo, vľavo, bez opustenia danej oblasti.

Nájdite takú súvislú oblasť, ktorá obsahuje \(k\) čísel a najväčšie číslo, ktoré obsahuje, je najmenšie možné.

Formát vstupu

Na prvom riadku sa nachádza číslo \(k\). Na druhom riadku sú medzerou oddelené čísla \(r, s\). Pre všetky vstupy platí \(1 \le k \le r \cdot s \le 10^6\).

Na každom z nasledujúcich \(r\) riadkov sa nachádza \(s\) medzerou oddelených kladných celých čísel, ktoré udávajú výšky jednotlivých budov v meste. Výška žiadnej budovy nepresiahne \(10^9\).

Formát výstupu

Na prvý riadok výstupu vypíšte celé číslo určujúce najmenšiu možnú výšku najvyššej odkúpenej budovy. Následne vypíšte \(r\) riadkov a na každom z nich \(s\) znakov. Každý znak musí byť bodka ("."), alebo hviezdička ("*"), pričom hviezdičkami označené políčka musia vyznačovať ľubovoľné zo správnych riešení.

Príklady

Input:

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

Output:

3
...
..*
.**
***

Input:

4
3 3
1 1 2
1 2 1
2 1 1

Output:

2
***
.*.
...

V úlohe hľadáme dva výsledky, ktoré aj vypisujeme – súvislú oblasť veľkosti \(k\) a najmenšiu možnú výšku najvyššej budovy v takejto oblasti – označme ju \(H\). Ak ale poznáme jeden z týchto dvoch výsledkov, tak ten druhý sa k nemu dá dopočítať celkom ľahko.

Ak poznáme “ideálnu výšku”, stačí postupne skúšať prehľadávať mesto do šírky alebo do hĺbky1. Zo všetkých (ešte nenavštívených) políčok postupne spúšťame prehľadávania, kým nenájdeme oblasť veľkosti aspoň \(k\). Prehľadávanie navyše navštevuje len také susedné políčka, ktorých budovy sú nanajvýš tak vysoké ako “ideálna výška” \(H\).

Naopak, keď poznáme tú správnu oblasť, poľahky vyrátame, aká je v nej tá najväčšia výška. Stačí prejsť všetky políčka danej oblasti a zapamätať si výšku toho najvyššieho z nich.

Toto umožňuje dva prístupy k príkladu: prvý, v ktorom sa snažíme nájsť tú “ideálnu” výšku a druhý, kedy sa pokúšame skonštruovať nejakú správnu oblasť. V tomto vzoráku sa budeme zaoberať tým prvým prístupom a na konci si len krátko spomenieme, ako by sa dalo na riešenie prísť z druhej strany.

Jednoduché hľadanie najmenšej výšky

Postupne budeme skúšať pre všetky možné výšky \(h\) (od najmenšej po najväčšiu) nasledovný postup:

  1. Vieme nájsť oblasť veľkosti aspoň \(k\), kde je najvyššia budova vysoká nanajvýš \(h\)? (Toto vieme zistiť práve spomínanými prehľadávaniami.)

  2. Ak nie, skúsme to isté, pre výšku o jedna väčšiu.

Takýmto spôsobom po chvíli prídeme k tej najmenšej vyhovujúcej výške – k výške \(H\). Na záver len vypíšeme jej prislúchajúcu oblasť a máme vyhrané.

Akú má toto riešenie časovú zložitosť? Robíme prehľadávanie na mriežke rozmerov \(r \times s\) pre výšky, až kým nenájdeme tú správnu. V najhoršom prípade bude riešenie potrebovať \(O(r \cdot s \cdot h_{max})\) operácií, čo je podľa zadania najviac \(10^6 \cdot 10^9 = 10^{15}\). Je to síce oveľa viac, než si v bežnom programe môžeme dovoliť, no riešenie zvládne vyriešiť menšie vstupy a aj vstupy, kde je \(h_{max}\) malé.

Pamäťová zložitosť algoritmu je \(O(r \cdot s)\), keďže si musíme pamätať výšku každej budovy a aj to, ktoré políčka sme pri prehľadávaní navštívili.

Ako toto riešenie zlepšiť? Naša úloha má príjemnú vlastnosť, ktorú sme zatiaľ nepoužili: Pre všetky výšky menšie ako ideálna výška \(H\) dostatočne veľkú oblasť nájsť nevieme, a naopak, pre všetky výšky väčšie ako \(H\) takú oblasť určite nájsť vieme.

Toto nám tvorí ideálne podmienky pre použitie binárneho vyhľadávania.

Binárne hľadanie najmenšej výšky \(H\)

Myšlienka binárneho vyhľadávania je veľmi jednoduchá. Pre nejakú hodnotu výšky \(h\) sa pýtame otázku: Vieme nájsť súvislú oblasť veľkosti aspoň \(k\), kde je najväčšia budova vysoká nanajvýš \(h\)?

  • Ak áno, hľadaná výška je \(\leq h\).

  • Ak nie, hľadaná výška je \(> h\).

Na začiatku si teda zvolíme interval, v ktorom budeme vyhľadávať: (left, right] = (-1, max_h]. Jeho ľavá hranica bude označovať najväčšiu výšku, o ktorej vieme, že sa pre ňu nedá nájsť dostatočne veľká oblasť. Opačne, pravá hranica intervalu bude označovať najnižšiu výšku, o ktorej vieme, že sa pre ňu dá nájsť dostatočne veľká oblasť. Následne sa opakovane pýtame danú otázku pre výšku \(h = (right + left) / 2\) – výšku presne uprostred intervalu.

  • Ak sa dá nájsť dostatočne veľká oblasť, posunieme pravú hranicu intervalu na \(h\).

  • Ak sa nedá nájsť dostatočne veľká oblasť, posunieme ľavú hranicu intervalu na \(h\).

Prehľadávanie skončíme, ak zostane v intervale len jediná hodnota – jeho pravá hranica – výška \(H\).

To, že sme si zvolili práve polootvorený interval (jeden z jeho hraničných prvkov v ňom nie je) nie je náhoda. Vďaka takejto voľbe sa vieme ľahko rozhodnúť, kedy kam posunúť ktorú hranicu – predsa tak aby zostali zachované definície left a right. Tiež sa vyhneme rôznym chybám, keďže pivot (prostredný prvok – \(h\)) nám rozdelí interval opäť na dva polootvorené – (left, h] a (h, right] – také, že ich prienik je prázdny a ich zjednotením dostaneme práve (left, right]. Vďaka tomu žiadnu možnosť nikdy nebudeme uvažovať dvakrát a žiadnu tiež nikdy nevynecháme. Ako bonus dostávame, že dĺžka intervalu (left, right] je práve right-left.

#include <iostream>
#include <vector>
#include <queue>

#define INF 1000000000

using namespace std;

int zmena_riadku[4] = {-1, 0, 1, 0};
int zmena_stlpca[4] = {0, -1, 0, 1};

int cislo_pokusu = 0;

vector<vector<int> > vysky;
vector<vector<int> > naposledy_navstivene;

// pokusime sa zafarbit oblast z policka (zacni_r, zacni_s), pricom navstivene
// policka musia mat vysku najviac `vyska` a oblast bude mat najviac plochu `max_plocha`
int skus_bfs(int vyska, int zacni_r, int zacni_s, int max_plocha = INF) {
    cislo_pokusu++;
    queue<int> q;
    q.push(zacni_r); q.push(zacni_s);
    naposledy_navstivene[zacni_r][zacni_s] = cislo_pokusu;
    int najdena_velkost = 1;

    while (!q.empty()) {
        int riadok = q.front(); q.pop(); 
        int stlpec = q.front(); q.pop();                

        for (int smer = 0; smer < 4; smer++) {
            int vedla_r = riadok + zmena_riadku[smer]; 
            int vedla_s = stlpec + zmena_stlpca[smer];
            
            bool prilis_vysoko = (vysky[vedla_r][vedla_s] > vyska);
            bool uz_navstivene = (naposledy_navstivene[vedla_r][vedla_s] == cislo_pokusu);
            if (prilis_vysoko || uz_navstivene)
                continue;

            q.push(vedla_r); q.push(vedla_s);
            naposledy_navstivene[vedla_r][vedla_s] = cislo_pokusu;
            najdena_velkost++;
            
            if (najdena_velkost == max_plocha)
                return najdena_velkost;
        }
    }
    return najdena_velkost;
}

bool da_sa_vyska(int vyska, int velkost_riesenia, bool presna_velkost = false) {
    int prvy_pokus_tejto_vysky = cislo_pokusu + 1;
    
    for (int r = 0; r < vysky.size(); r++) {
        for (int s = 0; s < vysky[r].size(); s++) {
            bool prilis_vysoko = (vysky[r][s] > vyska);
            bool uz_navstivene = (naposledy_navstivene[r][s] >= prvy_pokus_tejto_vysky);
            if(prilis_vysoko || uz_navstivene)
                continue;
            
            int zafarbena_plocha = skus_bfs(vyska, r, s, ((presna_velkost) ? velkost_riesenia : INF));

            if (zafarbena_plocha >= velkost_riesenia)
                return true;
        }
    }
    return false;    
}

int main() {
    int velkost_riesenia, velkost_r, velkost_s;
    cin >> velkost_riesenia >> velkost_r >> velkost_s;
    vysky.resize(velkost_r+2, vector<int>(velkost_s+2, INF));
    naposledy_navstivene.resize(velkost_r+2, vector<int>(velkost_s+2, 0));

    for (int r = 1; r < velkost_r+1; r++) {
        for (int s = 1; s < velkost_s+1; s++) {
            cin >> vysky[r][s];
        }
    }

    // Riesenie sa nachadza v intervale (left, right> 
    // left - navyssia vyska o ktorej isto vieme, ze nie je riesenim
    // right - najnizsia vyska o ktorej vieme, ze je riesenim
    int left = -1, right = INF;

    // Binarne vyhladavame najnizsiu vysku
    while (right - left > 1) {
        int piv = (left + right) / 2;
        if (da_sa_vyska(piv, velkost_riesenia)) {
            right = piv;
        } else {
            left = piv;
        }
    }
    int min_vyska = right;

    // Oznacime si oblast presne s velkostou velkost_riesenia
    da_sa_vyska(min_vyska, velkost_riesenia, true);
    
    // Vypisujeme najdene riesenie
    cout << min_vyska << endl;
    for (int r = 1; r < velkost_r+1; r++) {
        for (int s = 1; s < velkost_s+1; s++) {
            if (naposledy_navstivene[r][s] == cislo_pokusu) {
                cout << "*";
            } else {
                cout << ".";
            }
        }
        cout << endl;
    }

    return 0;
}

Časová zložitosť nám klesla na \(O(r \cdot s \cdot \log(h_{max}))\), lebo pri vyhľadávaní sa vždy spýtame najviac \(\log_2(dlzka~intervalu)\) otázok. Pamäťová zložitosť ostáva \(O(r \cdot s)\), lebo si pamätáme tie isté údaje ako v jednoduchšom riešení.

Pohľad z opačnej strany

Bez väčších omáčok si vysvetlime, ako sa na to dalo dívať inak. Predstavíme si, že v meste ešte nie je postavená žiadna budova. Preto ich tam začneme postupne pridávať od najmenšej budovy po najvyššiu. Popri tom budeme sledovať, či po pridaní budovy nevznikla súvislá oblasť budov veľkosti aspoň \(k\). Ak vznikla, tvrdíme, že táto oblasť je samotným riešením problému.

Dokážme si to sporom. Ak by existovala nejaká iná dostatočne veľká súvislá oblasť, ale najvyššia budova v nej by bola nižšia, tak to znamená, že túto oblasť sme museli nájsť už skôr. Keďže sme ale pridávali budovy od najnižšej, tak sme museli pridať už všetky budovy tvoriace túto oblasť. Takúto oblasť by sme teda už objavili skôr, čo je v spor s tvrdením, že pridaním poslednej budovy vznikla dostatočne veľká oblasť prvýkrát.

Potrebujeme ešte vyriešiť, ako zisťovať, či už existuje súvislá oblasť veľkosti aspoň \(k\). Na také niečo je ako stavaný algoritmus Union-find, pri ktorom si udržujeme súvislé oblasti budov. Vždy keď pridávame novú budovu, zistíme, do ktorej oblasti ju máme pridať a či prípadne nespojila nejaké skupiny dokopy. Pre jednotlivé oblasti si pamätáme ich veľkosti a ak má nejaká z nich veľkosť aspoň \(k\), môžeme náš algoritmus zastaviť.

Takéto riešenie je rovnako dobré ako binárne vyhľadávanie najmenšej výšky, keďže musíme usporiadať všetkých \(r\cdot s\) budov podľa veľkosti. Samotný algoritmus union-find už nespotrebuje viac času ako toto triedenie a preto je výsledná časová zložitosť \(O(r\cdot s \cdot log(r\cdot s))\) a pamäťová zložitosť ostáva \(O(r \cdot s)\).

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

int r, c, k;
    
int id_podla_pozicie(int y, int x){return y*c + x;}

void pozicia_podla_id(int id, int &y, int &x){y = id / c; x = id % c;}

vector<vector<int> > mapa_vysok;
vector<pair<int, pair<int,int> > > policka_od_najnizsieho;

vector<int> otec, hlbka_komponentu, velkost;

void nacitaj_vstup(){
    scanf(" %d %d %d",&k, &r, &c);
    mapa_vysok.resize(r, vector<int>(c, 0));
    otec.resize(r*c, 0);
    velkost.resize(r*c, 1);

    for(int y=0; y<r; y++){
        for(int x=0; x<c; x++){
            int vyska;
            scanf(" %d", &vyska);
            mapa_vysok[y][x] = vyska;
            policka_od_najnizsieho.push_back({vyska, {y, x}});
            int id = id_podla_pozicie(y, x);
            otec[id] = id;
        }
    }
}

int sef(int a){
    if (otec[a] == a) return a;
    return otec[a] = sef(otec[a]);
}

int spoj(int a, int b){
    int vacsi = sef(a), mensi = sef(b);
    if (vacsi == mensi) return velkost[vacsi];
    
    if (velkost[vacsi] < velkost[mensi]) swap(vacsi, mensi);

    otec[mensi] = vacsi;
    velkost[vacsi] += velkost[mensi];
    return velkost[vacsi];
}

void najnizsi_komponent_velkosti_k(int &id_komponentu, int &vyska){
    for(int i=0; i<r*c; i++){
        vyska = policka_od_najnizsieho[i].first;
        int y = policka_od_najnizsieho[i].second.first;
        int x = policka_od_najnizsieho[i].second.second;
        int id1 = id_podla_pozicie(y, x);

        for(int j=0; j<4; j++){
            int nx = x + dx[j];
            int ny = y + dy[j];
            if (nx < 0 || nx >= c || ny < 0 || ny >= r) continue;
            if (mapa_vysok[ny][nx] > vyska) continue;

            int id2 = id_podla_pozicie(ny, nx);
            
            int velkost = spoj(id1, id2);
            if (velkost >= k){
                id_komponentu = sef(id1);
                return;
            }
        }
    }
}

vector< vector< char > > riesenie;

void BFS_presne_velkosti_k(int id_zaciatku){
    int zaciatok_x, zaciatok_y;
    pozicia_podla_id(id_zaciatku, zaciatok_y, zaciatok_x);
    queue<int> q;
    
    int pocet_vyfarbenych = 1;
    riesenie[zaciatok_y][zaciatok_x] = '*';
    q.push(zaciatok_x); q.push(zaciatok_y);

    while(!q.empty() && pocet_vyfarbenych < k){
        int x = q.front(); q.pop();
        int y = q.front(); q.pop();

        for(int j=0; j<4; j++){
            int nx = x + dx[j];
            int ny = y + dy[j];
            
            if (pocet_vyfarbenych == k) break;
            if (nx < 0 || nx >= c || ny < 0 || ny >= r) continue;
            if (sef(id_podla_pozicie(ny, nx)) != id_zaciatku) continue;
            if (riesenie[ny][nx] == '*') continue;

            pocet_vyfarbenych++;
            riesenie[ny][nx] = '*';
            q.push(nx); q.push(ny);
        }
    }
}

int main(){
    nacitaj_vstup();

    sort(policka_od_najnizsieho.begin(), policka_od_najnizsieho.end());

    int komponent, vyska;
    najnizsi_komponent_velkosti_k(komponent, vyska);

    riesenie.resize(r, vector<char>(c, '.'));
    BFS_presne_velkosti_k(komponent);

    printf("%d\n", vyska);
    for(int y=0; y<r; y++){
        for(int x=0; x<c; x++){
            printf("%c", riesenie[y][x]);
        }
        printf("\n");
    }
}

  1. Ak sú vám tieto pojmy cudzie, na internete nájdete množstvo materiálov na témy breadth-first-search a depth-first-search. V češtine/slovenčine si môžete pozrieť napríklad časť kuchárky českého KSP alebo poznámky k prednáške zo sústredenia Prask (od str. 20).↩

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ť.