Zadanie
Za niekoľko desaťročí jeho existencie prišli do Kolosea stovky miliónov divákov. Múry Kolosea tento nápor znášajú veľmi dobre – stoja rovnako pevné a majestátne, ako keď bolo Koloseum nové. Horšie je to s čalúnenými sedačkami. Tie sú už nechutne špinavé a mnohé z nich aj nepríjemne páchnu.
Predavač lístkov Mikix si všimol, že ľudia uprednostňujú miesta, kde je menší smrad. Preto sa Mikix rozhodol, že smrad na jednotlivých miestach zohľadní v cene lístkov.
Úloha
Sektor, v ktorom Mikix predáva lístky, má tvar štvorca s \(n\) radmi po \(n\) sedadiel. Každé sedadlo páchne s nejakou intenzitou, ktorú budeme v tejto úlohe reprezentovať celým číslom (čím väčšie číslo, tým väčší smrad). To, aký silný zápach cítime, keď na sedadle sedíme, však závisí aj od okolitých sedadiel. Konkrétne, vždy cítime najsmradľavejšie sedadlo vo štvorci \(k \times k\) sedadiel so stredom1 v sedadle, na ktorom sedíme.
Mikix chce pre každé sedadlo vo svojom sektore určiť, aký silný smrad je na danom mieste cítiť. Pre každé sedadlo \(S\) teda zistite intenzitu zápachu najsmradľavejšieho sedadla vo štvorci \(k \times k\) okolo sedadla \(S\).
Formát vstupu
Na prvom riadku sa nachádzajú dve kladné celé čísla \(n\) a \(k\) oddelené medzerou, označujúce veľkosť sektora a veľkosť okolia, v ktorom je cítiť zápach. Číslo \(k\) je pritom nepárne. Nasleduje \(n\) riadkov a v nich \(n\) medzerami oddelených celých čísel \(0 \leq a_{i,j} \leq 10^9\) – intenzity zápachu jednotlivých sedadiel.
číslo sady | \(1\) | \(2\) | \(3\) | \(4\) |
---|---|---|---|---|
\(n,k \leq\) | \(40\) | \(100\) | \(400\) | \(1\,000\) |
Formát výstupu
Vypíšte \(n\) riadkov a v každom z nich \(n\) čísel oddelených medzerami. V \(i\)-tom riadku ako \(j\)-te číslo vypíšte intenzitu zápachu najsmradľavejšieho sedadla, ktoré je cítiť zo sedadla \((i,j)\).
Príklady
Input:
3 1
1 2 3
4 5 6
7 8 9
Output:
1 2 3
4 5 6
7 8 9
Cítime iba sedadlo, na ktorom sedíme.
Input:
3 3
1 2 3
4 5 6
7 8 9
Output:
5 6 6
8 9 9
8 9 9
Teraz cítime už aj bezprostredne okolité sedadlá.
číslo \(k\) je nepárne↩
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;
}
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ť.