Analiza

Prvo napravima dva geometrijska zaključka.

• Ukoliko bismo rekli da grb treba da bude konveksan četvorougao koji ima kao tri temena tačke jedne a kao preostalo teme tačku druge boje broj načina za iscrtavanje grbova ne bi se razlikovao od onog traženog u zadatku.

• Ukoliko bi se početne crne i bele tačke nalazile u temenima proizvoljnog konveksnog mnogougla broj načina za iscrtavanje grbova ne bi se razlikovao od onog traženog u zadatku.

Dakle kada odaberemo četiri tačke koje ćemo povezati tokom crtanja jednog grba one dele preostale tačke na četiri grupe (neke od kojih su potencijalno prazne) naime na četiri ciklična segmenta početnog niza tačaka.

Kako sada ne mogu postojati duži koje spajaju tačke iz različitih grupa svaki novi grb koji nacrtamo (odnosno njegova temena) nalaziće se tačno u jednoj od grupa, a kako tačke svake grupe opet čine konveksan mnogougao vidimo da je problem nalaženja broja načina da se nacrtaju grbovi koristeći temena neke grupe u stvari analogan početnom problemu.

Rešimo sada problem dinamičkim programiranjem, definišimo:

• ~d[i][j][0]~ - broj načina da se na cikličnom segmentu ~[i, j)~ (uključuje ~i~, ne uključuje ~j~) nađe tačka ~s~ boje ~0~ i da se tačke segmenata ~[i,s)~ i ~[s + 1, j)~ spoje u grbove (svaki grb (odnosno njegova temena) da se nalaze tačno u jednom od segmenata, u ~[i,s)~ ili u ~[s + 1, j)~)

• ~d[i][j][1]~ - analogno samo za ~s~ boje ~1~

• ~d[i][j][2]~ - broj načina da se tačke segmenata ~[i, j)~ spoje u grbove.

Pre nego što počnemo primetimo da ~d[i][j][0]~ i ~d[i][j][1]~ mogu biti ne nula samo ukoliko je dužina (broj tačaka) u cikličnom intervalu ~[i, j)~ oblika ~4k + 1~, dok ~d[i][j][2]~ može biti ne nula samo ukoliko je udžina tog intervala oblika ~4k~.

Naši početni uslovi su

• Za svako ~1 \leq i \leq n~, ~d[i][i][2] = 1~
• Za svako ~1 \leq i \leq n~, ~d[i][i + 1][a[i]] = 1~
• Za svake ~i, j, k~, ~d[i][j][k] = 0~ sem za gore pomenute

Ostaje još da prođemo kroz sve intervale, sortirane po dužini (broju tačaka u njima).

Sada kada računamo ~d[i][j][0]~ jasno je da za svaki ~s~ iz intervala ~[i, j)~ takav da ~A[s] = 0~, trebamo ~d[i][j][0]~ da uvećamo za ~d[i][s][2] * d[s + 1][j][2]~, po definiciji.

Analogno za ~d[i][j][1]~.

U slučaju računanja ~d[i][j][2]~ znamo da je tačka ~i~ u grbu sa još tri tačke nazovimo onu koja se u smislu cikličnog poretka nalazi između druge dve, odnosno "srednju" tačku, ~s~. Ukoliko je ona iste boje kao tačka ~i~ broj načina da se tačke intervala ~[i, j)~ spoje u grbove na takav način je po definiciji ~d[i + 1][s][0] * d[s + 1][j][1] + d[i + 1][s][1] * d[s + 1][j][0]~ (tačke koje su nesparene u popunjavanju manjih segmenata sada uzimamo u isti grb sa tačkama ~i~ i ~s~, i vodimo računa o tome da su različitih boja), dok analogno ukoliko su ~i~ i ~s~ istih boja broj načina je ~d[i + 1][s][0] * d[s + 1][j][0] + d[i + 1][s][1] * d[s + 1][j][1]~.

Sve prethodno rečeno daje nam ukupnu složenost ~O(n^3)~.

Dodatak

Rešenje se može dodatno ubrzati ukoliko se primeti da ao na segmentu ~[i, j)~ ima ~a~ tačaka boje ~0~ i ~b~ tačaka boje ~1~, sistem jednačina ~3A + B = a~, ~A + 3B = b~, mora imati nenegativna rešenja (ukoliko posmatramo da je ~A~ broj grbova kojima je teme obojeno bojom ~1~, a ~B~ broj grbova kojima je teme obojeno bojom ~0~ jednačine direktno slede). Ovime i analognim uslovom za slučajeve kada računamo segment kom ostavljamo jednu tačku negrupisanu možemo izbeći bespotrebne prolaske kroz unutrašnju petlju algoritma.

Takođe implementacija algoritma postaje značajno pojednostavljena ukoliko umesto cikličnih segmenata datog niza posmatramo obične segmente dvostruko dužeg niza koji bismo dobili ukoliko bismo na kraj našeg niza nalepili još jedan identičan, uz gotovo identične jednačine.