Analiza

Potrebno je u kvadratnoj matrici ~A~ pronaći element koji je strogo najveći u svojoj vrsti i strogo najmanji u svojoj koloni -- nazovimo takav element (ukoliko postoji) sedlo (to je, inače, standarni termin). Za početak primetimo da ukoliko sedlo postoji, onda je jedinstveno; zaista, pretpostavimo da su ~A_{i,j}~ i ~A_{k,l}~ sedla. Očigledno, ~i \neq k~ i ~j \neq l~. Ukoliko je ~A_{i,j} \leq A_{k,l}~, tada, zbog definicije sedla, ~A_{i,j} > A_{i,l} > A_{k,l}~ što je kontradikcija; za ~A_{i,j} > A_{k,l}~ ponovo dobijamo kontradikciju preko ~A_{i,j} < A_{k,j} < A_{k,l}~ pa je nemoguće da postoje dva ili više sedla.

Iz prethodnog razmatranja sledi: ukoliko su nam poznate vrednosti neka dva polja (npr. ~A_{i,j}~ i ~A_{k,l}~), možemo eliminasti bar jedno od njih kao potencijalnog kandidata za sedlo upitom nad najviše jednim dodatnim poljem (~A_{i,l}~ ili ~A_{k,j}~). Dakle, proizvoljnih ~M~ potencijalnih kandidata za sedlo (za koje znamo vrednosti) možemo svesti na samo ~1~ uz ne više od ~M-1~ pitanja koriteći ovaj metod koji ćemo jednostavno zvati Eliminacija.

Podzadaci 1 i 2: Ovde je ~K = N^2~ pa jednostavno možemo pitati za vrednosti svih polja i naći sedlo u poznatoj matrici u složenosti ~O(N^3)~ ukoliko za svako polje prolazimo celu njegovu vrstu i kolonu ili u složenosti ~O(N^2)~ ukoliko prekalkulišemo maksimume po vrstama i minimume po kolonama.

Podzadatak 3: Kako su vrednosti iz skupa ~\{1,2,3\}~, jasno je da element ~A_{i,j}~ može biti sedlo ako i samo ako je ~A_{i,j} = 2~, svi ostali elementi u njegovoj vrsti su ~1~ i svi ostali elementi u njegovoj koloni su ~3~. Prema tome, ukoliko upitamo za vrednost ~A_{i,j}~ i dobijemo vrednost ~1~, eliminisali smo celu ~j~-tu kolonu (tamo ne može biti sedlo), ako dobijemo vrednost ~3~ -- eliminisali smo celu ~i~-tu vrstu, a ako dobijemo vrednost ~2~ - eliminisali smo celu ~i~-tu vrstu i ~j~-tu kolonu osim potencijalno baš elementa ~A_{i,j}~. Upite možemo postavljati tako da u svakom upitu eliminišemo bar jednu vrstu ili kolonu pa ćemo nakon najviše ~2N~ upita eliminisati sve vrste i kolone i ostaće nam najviše ~N~ polja koja mogu biti potencijalna sedla. Sada primenimo Eliminaciju (najviše još ~N~ upita) i još najviše ~2N~ upita za proveru da li je preostali element zaista sedlo (može se pokazati da je za ovaj metod gornja granica za broj upita zapravo ~4N~ umesto ~5N~).

Podzadatak 4: Postavimo upite za sve elemente sa glavne dijagonale i permutujmo vrste i kolone tako da važi ~A_{1,1} \leq A_{2,2} \leq \ldots \leq A_{N,N}~ (ovo nije problem, dovoljno je samo zapamtiti te permutacije i za svako naredno ~Pitaj(i,j)~ zapravo postavljati ~Pitaj(row[i], col[j])~). U novodobijenoj matrici, nijedan element ispod glavne dijagonale ne može biti sedlo (nemoguće da za ~i > j~ važi ~A_{i,j} > A_{i,i}~ i ~A_{i,j} < A_{j,j}~ jer ~A_{j,j} \leq A_{i,i}~) pa sedlo možemo tražiti samo na glavnoj dijagonali i iznad, pitajući za vrednosti sve kandidate (njih ~\frac{N(N+1)}{2}~) i primenjujući Eliminaciju (pokazati da nam prilikom Eliminacije nikada neće trebati vrednosti elemenata ispod glavne dijagonale jer možemo koristiti poredak na njoj!). Ovaj deo možemo i jednostavnije, nalazeći sedlo kao u Podzadatku 2 ne koristeći elemente ispod glavne dijagonale (pokazati da ćemo i u slučaju "polu-matrice" sa soritranom dijagonalom dobiti najviše jednog kandidata!). Kada dobijemo jedinstvenog kandidata, dovoljno je još ~N-1~ upita za proveru jer je najviše toliko polja iz njegove vrste i kolone (od njih ~2N-1~) ispod glavne dijagonale. Dakle, treba nam ~\frac{N(N+1)}{2} + N - 1~ upita, što se uklapa u ograničenja.

Podzadatak 5: U prethodnom podzadatku, umesto da pitamo za sva polja iznad glavne dijagonale, možemo npr. rekurzivno primeniti logiku za gornji-desni kvadrat (i opet pitati samo oko polovinu svih elemenata u njemu). Preciznije, radimo sledeće

• Ukoliko je trenutni kvadrat dimenzija ~1 \times 1~ pitamo i vratimo to polje kao potencijalnog kandidata; inače
• Pitamo za sve elemente glavne dijagonale trenutnog kvadrata i permutujemo vrste/kolone tako da važi poredak kao u prethodnom podzadatku
• Rekurzivno ponovimo postupak za gornji-levi, donji-desni i gornji-desni podkvadrat (za prva dva postavimo marker da ne moramo pitati/sortirati dijagonalu jer je već sortirana kao deo originalne) i od 3 dobijena kandidata Eliminacijom vratimo samo jedan.

Ako je ~T(N)~ broj poziva ~Pitaj~ ovog algoritma za kvadrat dimenzije ~N \times N~, nije teško zaključiti da važi ~T(1) = 1~ i ~T(N) = 3T(\lceil \frac{N}{2} \rceil)~ za ~N > 1~ (kako ima puno "preklapanja" dijagonala, možemo zamisliti da zapravo ne pitamo za polja osim ako je kvadrat ~1 \times 1~) pa je ~T(N) = 3^{\log_2 N} = N^{\log_2 3}~ (polja koja pitamo obrazuju neku vrstu fraktala a implementacija je blago zgodnija jer je ~N~ stepen dvojke). Za Eliminaciju nam u najgorem slučaju treba još toliko upita (a u praksi mnogo manje zbog preklapanja) i računajući konačnu proveru to je najviše ~2\cdot N^{\log_2 3} + 2N~ upita, što se uklapa u ograničenja.

Podzadaci 6 i 7: Nazovimo skup polja ~S~ (matrice) dobrim ukoliko nikoja dva polja iz ~S~ nisu u istoj vrsti ili koloni i ukoliko se sedlo (ukoliko postoji) cele matrice nalazi u preseku vrste u kojoj je neki element iz ~S~ i kolone u kojoj je neki element iz ~S~. Npr. jedan dobar skup je ~D = \{(1,1), (2,2), \ldots, (N,N)\}~.

~(*)~ Primetimo da ako je ~S~ dobar skup, tada sedlo ne sme biti veće od najvećeg elementa iz ~S~ i ne sme biti manje od najmanjeg elementa iz ~S~. Zaista, kako sedlo pripada nekoj koloni iz ~S~, ono je manje ili jednako od bar jednog elementa iz ~S~ pa i od maksimuma; slično i za minimum.

Neka je ~S~ proizvoljan dobar skup i neka je ~(i, j) \in S~ takvo da je ~A_{i,j}~ najmanja vrednost od svih vrednosti iz ~S~ a ~(k, l) \in S~ takvo da je ~A_{k,l}~ najveća vrednost od svih vrednosti iz ~S~. Od dobrog skupa ~S~ možemo dobiti dobar skup sa jednim elementom manje na sledeći način: pitamo za vrednost elementa ~A_{i,l}~ i razlikujemo 3 slučaja:

• ~A_{i,l} \leq A_{i,j}~: Ako je sedlo u koloni ~l~ onda je ono manje od ~A_{i,l}~ a samim tim i od ~A_{i,j}~ tj. od svih elemenata skupa ~S~ što je nemoguće zbog ~(*)~ . Dakle, u koloni ~l~ nema sedla. Sa druge strane, u vrsti ~k~ je jedini kandidat za sedlo ~A_{k,l}~ (inače bi sedlo moralo biti veće od svih elemenata iz ~S~ što je nemoguće zbog ~(*)~ ) ali već smo zaključili da u koloni ~l~ nema sedla pa sedlo nije ni u vrsti ~k~. Dakle, izbacivanjem elementa ~(k, l)~ iz ~S~ opet dobijamo dobar skup.
• ~A_{k,l} \leq A_{i,l}~: Analognim razmatranjem kao u prethodnom slučaju, dobijamo da se izbacivanjem elementa ~(i, j)~ iz ~S~ opet dobija dobar skup.
• ~A_{i,j} < A_{i,l} < A_{k,l}~: Koristeći ~(*)~ kao u prethodnim slučajevima, dobijamo da je ~A_{i,j}~ jedini kandidat za sedlo u koloni ~j~ i da je ~A_{k,l}~ jedini kandidat za sedlo u vrsti ~k~. Međutim, ~A_{i,j}~ i ~A_{k,l}~ ne mogu biti sedla zbog, redom, ~A_{i,j} < A_{i,l}~ i ~A_{i,l} < A_{k,l}~ pa sledi da sedlo nije ni u vrsti ~k~ ni u koloni ~j~. Ovu vrstu i kolonu možemo izbaciti tako što iz skupa ~S~ izbacimo elemente ~(i, j)~ i ~(k, l)~ ali ubacimo element ~(i, l)~ (jer moramo zadržati ~i~-tu vrstu i ~l~-tu kolonu). Novodobijeni skup je dobar i sadrži element manje.

Kada dobijemo dobar skup sa jednim elementom, on je jedini kandidat za sedlo. Dakle, algoritam je sledeći: krenemo od npr. dobrog skupa sa dijagonalnim elementima ~D~ (N upita), svedemo ga na dobar skup sa jednim elementom pomoću dodatnih ~N-1~ upita i na kraju potrošimo još najviše ~2N~ upita za proveru. U zavisnosti da li minimum/maksimum u svakom koraku tražimo u ~O(N)~ (trivijalno) ili u ~O(\log N)~ (uz pomoć neke strukture), ovo prolazi za prvih 6 ili za svih 7 podzadataka.

Rešenje sa očekivanim brojem upita reda ~O(N)~: Primetimo da ukoliko znamo vrednosti neka dva polja (npr. ~A_{i,j}~ i ~A_{k,l}~) možemo eliminisati bar jedno od polja ~A_{i,j}, A_{k,l}, A_{i, l}, A_{k,j}~ kao potencijalnog kandidata za sedlo bez ikakvih dodatnih upita (npr. ako je ~A_{i,j} \leq A_{k,l}~, možemo zaključiti da ~A_{j,k}~ ne može biti sedlo iako mu možda ne znamo vrednost). Prema tome, ukoliko smo postavili ~X~ upita, teoretski možemo eliminisati ~\frac{X(X-1)}{2}~ polja gledajući svaki par upita. Naravno, ovde može doći do puno preklapanja (različiti parovi upita eliminišu isto polje) ali se može pokazati (a i intuitivno je jasno) da je očekivani broj upita (ako ih postavljamo random) potreban za eliminaciju svih ~N^2~ polja (osim eventualno jednog) reda veličine ~O(N)~. Dodatno, upiti ne moraju biti postavljani bilo kako već u svakom koraku pitati samo neko trenutno ne-eliminisano polje (i pomoću njega i prethodnih upita raditi pomenutu elminaciju); ukoliko ostane ~O(N)~ ne-eliminisanih polja u nekom trenutku, možda je bolje prebaciti se na standardnu Eliminaciju itd.

Ovaj pristup, uz eventualnu randomizaciju ili bolje odabrani redosled upita, prolazi za Podzadatke 1, 2, 4 i 5 a često i za 3 (zbog specifičnih vrednosti i malo veće konstante za dozvoljeni broj upita u odnosu na Podzadatke 6 i 7). Sa druge strane ovo (verovatno) ne može rešiti Podzadatak 6 (zbog strožeg ograničenja u broju upita i eventualno memorijskog ograničenja) kao ni Podzadatak 7 (jer je složenost ~O(N^2)~).