Analiza

Jedna od ključnih stavki u zadatku jeste garancija da bez izbacivanja, odnosno uništenja nekog uzastopnog podniza nije moguće podeliti zadati niz tako da su mu podzbirovi nekog prefiksa i ostatka niza jednaki. Takođe, postavka zadatka uslovljava da su svi članovi ulaznog niza strogo pozitivni, što uz pažljivo rešavanje pojednostavljuje kompleksnost korišćenog algoritma pretrage.

Najpre, neka je zbir svih članova zadatog niza ~z~, a zbir članova nekog njegovog prefiksa (odnosno sufiksa) ~p~. Neophodno je odrediti neki neprazan podniz ulaznog niza koji ne obuhvata prefiks (odnosno sufiks), takav da ako zbir njegovih članova označimo sa ~s~, mora biti zadovoljen uslov ~z = p + s + p = 2p + s~. Drugim rečima, zbir članova podniza koji se uništava ~0 < s < z~, mora biti jednak ukupnoj sumi svih članova izvornog niza umanjenoj za dvostruku vrednost prefiksa, ~s=z-2p~.

Sada je potrebno izvršiti pretragu po svim prefiksima (odnosno sufiksima) i svim uzastopnim podnizovima ulaznog niza i proveriti da li je moguće zadovoljiti malopređašnju jednakost. Ukoliko bi ta pretraga naivno bila izvršena kroz tri nezavisne petlje (prva po prefiksima niza, a druga i treća po levoj i desnoj granici podniza za uništenje), dobila bi se kubna vremenska složenost ~\mathcal{O}(N^3)~ po dužini niza. Međutim, uz nešto veštiju pretragu po levoj i desnoj granici uzastopnog podniza tu složenost moguće je i umanjiti.

Smernice za algoritam

Naime, na početku iteracije po prefiksima (odnosno sufiksima) inicijalizovati levu i desnu granicu na prvi susedni član prefiksa (odnosno sufiksa). U svakoj iteraciji neophodno je ispitati da li je vrednost izraza ~z - 2p - s~ veća, manja ili jednaka nuli, te ako je veća, pomerati desnu granicu, a ukoliko je manja, pomerati levu. Pretraga se završava ili kada izraz poprimi vrednost nula nakon čega sledi ispis utvrđenih granica podniza, ili kada leva i desna granica dođu do kraja izvornog niza, kada se prelazi na sledeći prefiks (odnosno sufiks). Pošto prilikom napredovanja granica mora biti zadovoljen i uslov da indeks leve granice nije viši od indeksa desne, to je ukupna složenost ove unutrašnje petlje linearna ~\mathcal{O}(N)~ po dužini niza. Kako je neophodno pretragu uraditi za sve prefikse i sufikse izvornog niza (zbog asimetrije pretrage), to je ukupna složenost ovog algoritma kvadratna ~\mathcal{O}(N^2)~, što se i zahtevalo za maksimalan broj poena u ovom zadatku.