Analiza

Opišimo ključne korake u rešavanju svakog podzadatka.

Podzadatak ~1~

U prvom podzadatku, dovoljno dobro je i bruteforce rešenje. Prolaskom kroz svaki mogući podniz uzastopnih Marsovaca određujemo maksimalnu i minimalnu visinu u njemu, njihovu razliku, i brojimo podnizove gde je ta razlika maksimalna. Ovaj pristup ima vremensku složenost ~O(N^3)~.

Podzadatak ~2~

Mala modifikacija prethodnog pristupa može dovesti do vremenske složenosti ~O(N^2)~. Ako prolazak kroz sve podnizove vršimo tako što fiksiramo levu granicu ~L~, a zatim pomeramo desnu granicu ~R~, možemo u ~O(1)~ naći maksimum i minimum u svakom podnizu na osnovu prethodno izračunatih rešenja. Konkretno, imamo da je ~max(H_L, H_{L+1}, \dots, H_{R+1}) = max(max(H_{L}, H_{L+1}, \dots, H_{R}), H_{R+1})~. Slično važi i za minimum.

Podzadatak ~3~

U ovom momentu, neophodno je napraviti par bitnih opservacija koje predstavljaju prvi korak ka kompletnom rešenju zadatka.

Označimo sa ~H_{min}~ i ~H_{max}~ visinu najnižeg, odnosno najvišeg Marsovca. Sada primećujemo da je najveća moguća razlika najvišeg i najnižeg Marsovca u nekom podnizu uzastopnih Marsovaca jednaka ~H_{max} - H_{min}~. Veću razliku nije moguće dobiti, a upravo ova razlika se dobija u bilo kom podnizu u kom je ~H_{max}~ maksimum a ~H_{min}~ minimum - npr. ceo niz. Takođe, važi da je maksimum u nekom podnizu jednak ~H_{max}~ ako i samo ako se u njemu nalazi bar jedna vrednost ~H_{max}~ (slično važi i za minimum). Sada se zadatak može svesti na brojanje podnizova koji sadrže barem jednog Marsovca visine ~H_{max}~ i barem jednog Marsovca visine ~H_{min}~.

Dodatni uslov koji ovaj podzadatak unosi je da se vrednosti ~H_{min}~ i ~H_{max}~ pojavljuju tačno jednom u nizu visina. Označimo indeks (jedinstvenog) najvišeg Marsovca sa ~i_{max}~ a najnižeg sa ~i_{min}~ i uzmimo da je (ne umanjujući opštost) ~i_{max} < i_{min}~. Sada do rešenja dolazimo u konstantnom vremenu, uz malo računa. Kako leva granica podniza ne sme biti veća od ~i_{max}~ (inače se ~H_{max}~ ne nalazi u tom podnizu), a desna manja od ~i_{min}~ (inače se ~H_{min}~ ne nalazi u tom podnizu) broj podnizova koji sadrže i ~H_{min}~ i ~H_{max}~ je jednak ~(i_{max} + 1) * (N - i_{min})~. Vremenska složenost ovog pristupa je ~O(n)~.

Podzadatak ~4~

Ovde je potrebno malo komplikovanije rešenje, budući da dodatni uslov iz prethodnog podzadatka ne važi, pa najviši (tj. najniži) Marsovac ne mora biti jedinstven. Brojanju podnizova pristupamo tako što pomeramo brojač ~L~ od početka do kraja niza i u svakom koraku računamo koliko ima podnizova čija je leva granica ~L~ a da sadrže barem jednog Marsovca visine ~H_{max}~ i barem jednog Marsovca visine ~H_{min}~. Kako bismo ovo efikasno izračunali u toku cele procedure održavamo dva pokazivača ~firstMax~ i ~firstMin~ koji, za trenutno ~L~, pokazuju na prvo pojavljivanje Marsovca visine ~H_{max}~ (odnosno ~H_{min}~) od pozicije ~L~ pa do kraja niza (uključujući i ~L~). Kako je leva granica podniza fiksirana na ~L~, a desna granica ne sme biti manja od ~max(firstMax, firstMin)~, u svakom koraky na konačno rešenje dodajemo ~N - max(firstMax, firstMin)~.

Ostalo je još da prodiskutujemo kako se ovi pokazivači efikasno održavaju: ako nakon inkrementovanja ~L~ važi ~firstMax>=L~ nije potrebna korekcija, a u suprotnom uvećavamo ~firstMax~ za jedan sve do prvog narednog pojavljivanja ~H_{max}~ (ako naredno pojavljivanje ne postoji, možemo odmah prestati sa brojanjem i ispisati trenutno rešenje). Analogno održavamo i drugi pokazivač.

Iako se u jednom koraku uvećanje pomenutih pokazivača može dogoditi i do ~N~ puta, u toku cele procedure će oni, kao i ~L~, preći put od početka do kraja niza, pa je ukupna vremenska složenost rešenja ~O(n)~.