Analiza

Prvi podzadatak se rešava trivijalnim razmatranjem slučajeva; za drugi podzadatak se lako uočava (npr. uz par nacrtanih primera) da za ~N > 6~ ne smemo imati (ukupno) više od 4 vrste/kolone koje sadrže senzore (jer mora biti ~M \leq 4N~) pa je broj senzora i njihov raspored prilično ograničen (pokazati da pri svim pomenutim uslovima broj senzora ne sme biti veći od 4!).

Razmatrajući kako položaj senzora utiče na broj sigurnih sektora i koristeći rešenje prvog problema za B kategoriju (obavezno pročitati i taj problem/rešenje!), uočava se da je dovoljno znati broj vrsta i broj kolona sa bar po jednim senzorom: ukoliko imamo tačno ~a~ vrsta i tačno ~b~ kolona sa bar po jednim senzorom tada je ukupan broj sigurnih sektora jednak ~(a+b)N - ab~. Dakle, moguće je dobiti tačno ~M~ sigurnih sektora ako i samo ako postoje prirodni brojevi ~1 \leq a \leq N~ i ~1 \leq b \leq N~ za koje važi \(None\) (a+b)N - ab = M. \(None\) Transformacijom prethodne jednačine za ~a \neq N~ dobijamo ~b = \frac{M - aN}{N - a}~, pa je jedan od načina za rešavanje ove jednačine ispitivanje svih kandidate za ~a~ među brojevima ~1,2,\ldots N~ i provera (za svaki od njih) da li je dobijeni broj ~b~ ceo i iz segmenta ~[1,N]~. Ovo vodi rešenju složenosti ~O(N)~ što je dovoljno za treći podzadatak.

Za kompletno rešenje, potrebno je smanjiti broj kandidata za promeljive ~a~ i ~b~ iz gornje jednačine. Glavna stvar je uočiti da osim trivijalne nejednakosti ~a \leq N~ (broj vrsta je ~N~) važi i ~aN \leq M~ jer ~a~ vrsta sa senzorima znači bar ~aN~ sigurnih polja (ovo smo mogli zaključiti i iz formule ~b = \frac{M - aN}{N - a}~). Množeći nejednakosti ~a \leq N~ i ~a \leq \frac{M}{N}~ dobijamo ~a \cdot a \leq N \cdot \frac{M}{N}~, odnosno ~a \leq \sqrt{M}~ i analogno ~b \leq \sqrt{M}~. Dakle, jedini kandidati za ~a~ su ~1,2,\ldots \sqrt{M}~ pa direktna provera daje rešenje složenosti ~O(\sqrt{M})~ što nosi maksimalan broj poena.

Ipak, rešenje još uvek nije kompletno -- da li za sve prirodne brojeve ~a~ i ~b~ možemo postaviti senzore tako da imamo tačno ~a~ vrsta i tačno ~b~ kolona sa bar po jednim senzorom? Odgovor je potvrdan - npr. ovo možemo odraditi tako što postavimo senzore u svim sektorima ~(i,j)~ za koje je ~1 \leq i \leq a~ i ~1 \leq j \leq b~ (gornja-leva podmatrica dimenzije ~a \times b~) ali je tada složenosti algoritma moramo dodati i složenost ispisa koja je ~O(ab)~ što može biti i ~\Theta(M)~ a ovo je previše sporo. Srećom, moguće je postaviti svega ~\max\{a, b\} = O(\sqrt{M})~ senzora ukoliko ih (uz pretpostavku ~a \leq b~) postavljamo u sektore ~(1, 1)~, ~(2, 2)~, ~\ldots~, ~(a, a)~, ~(a, a + 1)~, ~(a, a + 2)~, ~\ldots~, ~(a, b)~, kao na slici. Ovaj raspored senzora kompletira rešenje.