Analiza

Dokazaćemo da optimalno rešenje sigurno ima sledeći oblik: broj belih polja u koloni opada do neke tačke, a zatim raste do kraja, ili raste do neke tačke pa opada do kraja. Ovo znači da, ako sortiramo redove po poziciji gde im se menja boja, prvih ~K~ redova bojimo belo-crno, a ostale crno-belo.

Da bi dokaz bio jednostavniji, umesto da biramo boje za redove, biraćemo funkciju ~f~, gde je ~f(i)~ broj belih polja u koloni između "promena" ~i-1~ i ~i~. Za validna bojenja zida važe sledeće osobine ~f~, i obrnuto, ako osobine važe možemo napraviti bojenje:

• ~f(0) + f(n) = n~ (svi redovi promene boju)
• Za svako ~i~, ~|f(i) - f(i-1)| = 1~ (svaki put se menja tačno jedan red)

Dokaz ovoga ostavljamo čitaocu.

Prvo, sigurno postoji tačno jedan "trenutak" (deo zida između dve promene) kada imamo po ~\frac{N}{2}~ crnih i belih polja (za neparno ~N~, sličnim argumentom dokazujemo da se tačno jednom broj menja sa "više belih" na "više crnih"), tj. postoji tačno jedno ~x~ za koje ~f(x) = \frac{n}{2}~. Kada ovo ne bi bilo tačno, mogli bismo da poboljšamo rešenje:

• Nađemo ~x~ takvo da je ~f(x) = \frac{n}{2}~ i ~f(x-1) = f(x+1) = \frac{n}{2} + 1~ (ili slično za ~-1~) -- ako ne postoji, možemo odabrati neki interval između dve tačke gde ~f(i) = \frac{n}{2}~ i "obrnuti" ih (postaviti ~f(i) = n - f(i)~) tako da se ne promeni vrednost rešenja.
• Postavimo ~f(x) = \frac{n}{2} - 2~.

Bez gubitka opštosti pretpostavićemo da ~f(0) < \frac{n}{2}~ (počinjemo sa manje belih nego crnih polja). Na sličan način možemo dokazati da na intervalu od ~0~ to tačke gde imamo isti broj crnih i belih polja funkcija ~f~ opada do neke tačke pa raste, a od te tačke raste pa opada.

Dakle, optimalno ~f~ mora imati oblik "opada, pa raste, pa opada". Sada ćemo dokazati da ne možemo imati oba opadajuća dela: ako postoje, možemo smanjiti ~f(0)~ za ~2~ i povećati ~f(n)~ za ~2~ i dobiti bolje rešenje.

Sada smo dokazali da je optimalno rešenje ili da broj belih polja raste do neke tačke pa opada do kraja, ili obrnuto. Kako za svaki izbor broja belih polja na početku postoji tačno jedna tačka gde možemo preći sa rastućeg na opadajuće, ili sa opadajućeg na rastuće (kada su sva polja iste boje), imamo ~\mathcal{O}(n)~ opcija koje treba proveriti.

Sada još ostaje da nađemo način da izračunamo koliko bojenje vredi, ako je dat broj belih polja ~K~ na početku, i znamo da taj broj opada prvih ~x~ kolona a zatim raste do ~N-K~.

Smernice za algoritam

Izračunaćemo samo vrednost bojenja od početka do kolone ~x~. Od te kolone do kraja metod je identičan.

Vrednost koju treba izračunati je:

~\sum_{i = 0}^{x} (A_i - A_{i-1}) \cdot (K - i) = K \sum_{i=0}^x (A_i - A_{i-1}) - \sum_{i=0}^x i \cdot (A_i - A_{i-1})~

Da bismo ovo računali u konstantnom vremenu, na početku programa je dovoljno da izračunamo nizove prefiksnih suma koje nam daju ove dve "male" sume za svako ~x~.