6. Extrémny smrad vzorové riešenie

3 1
1 2 3
4 5 6
7 8 9

1 2 3
4 5 6
7 8 9

3 3
1 2 3
4 5 6
7 8 9

5 6 6
8 9 9
8 9 9

Našou úlohou bolo pre každú stoličku určiť silu zápachu aký je cítiť, keď si na ňu sadneme. Matematicky preložené: pre každé políčko v štvorci zo vstupu sme mali nájsť najväčšie číslo nachádzajúce sa v štvorci \(k\times k\) so stredom v danom políčku

Priamočiare riešenie

Urobíme presne to, čo sa od nás žiada. Pre každé políčko prejdeme všetky políčka v okolí \(k\times k\). A vyberieme to najväčšie a to si zapamätáme. Takéto riešenie bude mať časovú zložitosť \(O(n^2 k^2)\), keďže pre každé z \(n^2\) políčok sme museli skontrolovať celé okolie \(k\times k\).

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int n,k;
vector<vector<int> > mapa,vsledok;
int main() {
  ios::sync_with_stdio(false);
  cin>>n>>k;
  mapa.resize(n,vector<int>(n));
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++)cin>>mapa[i][j];
  }
  vsledok=mapa;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      for(int ii=max(0,i-k/2);ii<min(n,i+k/2+1);ii++){
        for(int jj=max(0,j-k/2);jj<min(n,j+k/2+1);jj++)vsledok[i][j]=max(vsledok[i][j], mapa[ii][jj]);
      }
    }
  }
  for(int i=0;i<n;i++){
    cout<<vsledok[i][0];
    for(int j=1;j<n;j++)cout<<" "<<vsledok[i][j];
    cout <<endl;
  }
  return 0;
}

Toto riešenie nie je optimálne, keďže sa na rovnaké políčka zo vstupu pozeráme strašne veľa ráz, poďme sa ale najprv pozrieť na jednoduchšiu verziu úlohy.

Jednorozmerná verzia

Čo ak by sme na vstupe dostali len jeden dlhý riadok a hľadali by sme najväčšie číslo v okolí \(k\) políčok?

Jedným z riešení je postupne prechádzať pole zľava doprava, pričom vo vhodnej dátovej štruktúre si budeme stále pamätať posledných \(k\) prvkov, ktoré sme videli. V každom kroku do štruktúry pridáme ďalší prvok, vyhodíme najstarší prvok (ktorý je už mimo okolia) a zapíšeme maximum z prvkov, ktoré máme v štruktúre.

Potrebujeme teda nejakú dátovú štruktúru, kde si budeme uchovávať posledných \(k\) prvkov a budeme vedieť povedať maximum z nej a robiť operáciu pridania prvku a odobratia najstaršieho prvku. Taká dátová štruktúra, ktorá vie odoberať najstarší prvok a pridávať nový prvok je napríklad fronta. Vo fronte máme prvky vždy zoradené podľa času, kedy prišli. Problém je ale s nájdením maxima.

Všimnime si však, že si nemusíme vždy pamätať všetky z posledných \(k\) prvkov. Zaujíma nás totiž iba maximum z ukladaných prvkov, teda ak vieme, že niektorý prvok už určite nebude maximum v žiadnej \(k\)-tici, môžeme ho z fronty vymazať. Napríklad keď pridávame prvok do fronty, tak môžeme všetky menšie prvky z fronty vymazať, keďže ich z fronty vyhodíme skôr (sú staršie) a sú menšie, teda nikdy nebudú maximom.

Čo nám to pomôže? Ak budeme dôsledne vyhadzovať z fronty všetky prvky, ktoré sú menšie, než ten práve pridávaný, bude mať naša fronta zaujímavú vlastnosť: jej prvky budú zoradené podľa veľkosti zostupne. Ak je totiž prvok \(A\) vo fronte pred prvkom \(B\), znamená to, že \(A\) je vo fronte dlhšie. To ale znamená, že \(A\) ,,prežil’’ pridávanie prvku \(B\), teda určite nie je menší ako \(B\).

Keďže prvky sú zoradené zostupne, vieme ľahko nájsť maximum (je to prvý prvok). Keď pridávame nový prvok, potrebujeme nájsť (a vyhodiť) všetky prvky, ktoré sú menšie. Tieto prvky budú na konci fronty (lebo čísla vo fronte sú zoradené zostupne), teda ich ľahko nájdeme a budú sa aj ľahko vyhadzovať.

Okrem toho ešte potrebujeme v každom kroku vyhodiť prvok, ktorý sme pridali pred \(k\) krokmi (ak tam ešte stále je). Ak je tento prvok stále vo fronte, musí to byť najstarší prvok fronty, a teda je určite na začiatku fronty.

S našou frontou teda budeme robiť nasledovné operácie:

• Čítanie z konca fronty a vyhadzovanie prvkov z konca fronty (keď vyhadzujeme z fronty všetky čísla menšie než prvok, ktorý sa chystáme pridať).
• Pridávanie prvkov na koniec fronty (keď pridávame nový prvok z poľa do fronty).
• Čítanie prvkov zo začiatku fronty (keď zisťujeme maximum prvkov vo fronte).
• Kontrolovanie a mazanie prvkov zo začiatku fronty (keď vyhadzujeme príliš staré prvky).

Obyčajná fronta ale nepodporuje mazanie z konca fronty, preto budeme musieť použiť obojsmernú frontu (v C++ deque). Tá dokáže robiť všetky spomínané operácie v konštantnom čase.

Zložitosť

Môže sa nám stať, že ak chceme pridať nejaký prvok, musíme zmazať celú frontu (lebo všetky prvky vo fronte sú menšie), čo môže byť až \(k\) prvkov. Jeden krok algoritmu teda môže trvať až \(\Theta(k)\) času a takýchto krokov robíme \(O(n)\), teda celý algoritmus má časovú zložitosť \(O(n k)\).

Časová zložitosť nášho algoritmu sa však dá odhadnúť aj tesnejšie. Ak sa pozrieme na algoritmus ako celok, vidíme, že každý prvok pridáme do fronty maximálne raz a maximálne raz ho odtiaľ aj vyhodíme. Všetky vyhadzovania dokopy nám teda zaberú iba \(O(n)\) času (aj keď niektoré z nich môžu byť pomalé), teda časová zložitosť celého algoritmu je \(O(n)\).

Dvojrozmerná verzia

Teraz sme už iba krok od riešenia. Predstavme si, že pre každý riadok vyriešime 1D verziu. Teraz máme na každom políčko najväčšie číslo v okolí \(1\times k\). Predstavme si, že teraz na tomto upravenom poli budeme zase riešiť 1D úlohu ale tentokrát po stĺpcoch. Takto nájdeme vlastne maximum z \(k\) obdĺžnikov veľkosti \(1\times k\) pod sebou, čo je vlastne maximum zo štvorca \(k\times k\), presne ako sme chceli. Teda celková časová zložitosť je \(O(n^2)\) keďže sme vyriešili 1D úlohu na všetkých \(n\) riadkoch a potom \(n\) stĺpcoch. Pamäťová zložitosť bude tiež \(O(n^2)\) keďže si musíme pamätať celý pôvodný sektor s hodnotami smradu.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int n,k;
vector<vector<int> > mapa,vsledok,riadky;
deque<pair<int,int> > Q;
void pridaj(pair<int,int> co){
  while(!Q.empty() && Q.back().first>=co.first)Q.pop_back();
  Q.push_back(co);
}

int main() {
  ios::sync_with_stdio(false);
  cin>>n>>k;
  mapa.resize(n,vector<int>(n));
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin>>mapa[i][j];
      //hladame minimum namiesto maxima
      mapa[i][j]*=-1;
    }
  }
  riadky=mapa;
  //po riadkoch
  for(int i=0;i<n;i++){
    Q.clear();
    for(int j=0;j<min(k/2,n);j++)pridaj({mapa[i][j],j});
    for(int j=0;j<n;j++){
      if(j+k/2<n)pridaj({mapa[i][j+k/2],j+k/2});
      if(Q.front().second<j-k/2)Q.pop_front();
      riadky[i][j]=Q.front().first;
    }
  }
  vsledok=riadky;
  // po stlpcoch
  for(int j=0;j<n;j++){
    Q.clear();
    for(int i=0;i<min(k/2,n);i++)pridaj({riadky[i][j],i});
    for(int i=0;i<n;i++){
      if(i+k/2<n)pridaj({riadky[i+k/2][j],i+k/2});
      if(Q.front().second<i-k/2)Q.pop_front();
      vsledok[i][j]=-Q.front().first;
    }
  }
  for(int i=0;i<n;i++){
    cout<<vsledok[i][0];
    for(int j=1;j<n;j++)cout<<" "<<vsledok[i][j];
    cout <<endl;
  }
  return 0;
}