Analiza

Posmatrajmo slučajeve gde je broj početnih polja (~M~) mali, kao što i sugeriše prvi podzadatak. Jasno je da je za ~M = 1~ rešenje ~2N - 1~ (samo polja u odgovarajućoj vrsti i koloni) bez obzira na to gde se početno polje nalazi. Za ~M = 2~ lako se uočava da je dovoljno posmatrati samo dva slučaja: ~1)~ ukoliko početna polja nisu u istoj vrsti ni koloni, tada je rešenje ~4N - 4~ jer zauzimamo po dve vrste i kolone, ali, u njihovom preseku se nalaze 4 polja koja brojimo 2 puta pa otud oduzimanje; ~2)~ ukoliko su početna polja su u istoj vrsti ili koloni tada imamo vrstu/kolonu manje pa je rešenje ~3N - 2~.

Za drugi podzadatak je dovoljno odraditi direktnu simulaciju -- za svako početno polje ~(x,y)~ markirati sva polja neke matrice ~N \times N~ oblika ~(x, i)~ i ~(y, j)~ i na kraju prebrojati markirana polja u matrici. Vremenska složenost ovog pristupa je ~O(M\cdot N + N^2)~ a memorijska ~O(N^2)~ pa je jasno da će nam za ostale podzadatke trebati bolji algoritam.

Na osnovu prethodne diskusije, prirodno se nameće činjenica da rešenje ne zavisi od tačnih položaja početnih polja već samo od njihovog međusobnog položaja, a prevashodno od toga da li su u istoj vrsti/koloni. Neka je ~a~ broj vrsta u kojima se nalazi bar jedan krompir a ~b~ - broj kolona u kojima se nalazi bar jedan krompir. Jasno, na svakom polju ovih ~a~ vrsta i ~b~ kolona će izrasti krompir dok će ostala polja ostati prazna. Prema tome, ukupno imamo ~a + b~ pokrivenih vrsta/kolona koje međusobno imaju ukupno ~ab~ presečnih polja koja ne smemo da računamo dva puta, pa je ukupan broj polja sa krompirima jednak ~(a + b)N - ab~.

Dakle, dovoljno je odrediti vrednosti ~a~ i ~b~. Broj ~a~ je jednak broju različitih elemenata u nizu ~x_1, x_2, \ldots, x_M~ (analogno za ~b~ i niz ~y~) a ovo je poznat problem koji se može uraditi sortiranjem niza ~x~ i upoređivanjem uzastopnih elemenata. Složenost ovog pristupa je složenost soritranja niza dužine ~M~ a za treći podzadatak je dovoljno koristiti i algoritme sortiranja složenosti ~O(M^2)~.

Za kompletno rešenje zadatka nije neophodno sortiranje; dovoljno je primetiti da su vrednosti niza ~x~ celi brojevi iz segmenta ~[1, N]~ pa možemo koristiti pomoćni logički niz ~row~ dužine ~N~ i za svako ~x_i~ markirati element ~row[x_i]~. Na kraju, broj markiranih elementa je upravo broj ~a~ (slično i za drugi pomoćni niz i broj ~b~). Vremenska složenost ovog pristupa je ~O(N + M)~ uz ~O(N)~ memorije, i nosi maksimalan broj poena.