Piramid
Vom considera doar cazurile in care varful piramidei este in sus. Celelalte cazuri se pot numara identic rotind matricea initiala cu 90 de grade de 3 ori. Inainte de a incerca sa rezolvam problema o sa trebuiasca sa definim si sa precalculam cateva lucruri:
- Fie V[i][j] lungimea celui mai mare /\ cu varful in i, j. (vezi Fig. 1: V = 2)
- Fie L[i][j] lungimea celui mai mare interval de 1-uri consecutive de pe linia i, ce are pozitia i, j ca mijloc (vezi Fig.2: pentru 1-ul inclinat segmentul ingrosat este cel mai mare interval de 1-uri consecutive de pe linia lui, al carui centru este, si L = 2)
- Definim centrul unei piramide ca fiind punctul din mijlocul bazei acelei piramide (vezi Fig. 3)
- Definim inaltimea unei piramide ca fiind distanta intre centrul piramidei si varful acesteia (vezi Fig. 4: inaltimea este egala cu 3 si este marcata de literele H).
| Fig. 1 | Fig. 2 | Fig. 3 | Fig. 4 | Fig. 5 |
|---|---|---|---|---|
| 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 1 1 C 1 1 1 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 0 0 H 0 0 0 0 0 1 H 1 0 0 0 1 0 H 0 1 0 1 1 1 C 1 1 1 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 1 C 1 1 1 1 0 0 0 0 0 0 0 0 0 |
Vom parcurge fiecare coloana din matrice in parte. Pentru o anumita coloana j vom parcurge liniile in ordine crescatoare si pentru fiecare linie i vom incerca sa numaram cate piramide cu centrul in pozitia i, j exista (vezi Fig. 5). Folosindu-ne de informatia din L[i][j] putem sti inaltimea maxima pe care o poate avea o piramida cu centrul in i, j. Asadar observam ca de fapt ne intereseaza sa numaram cate pozitii k, j respecta conditiile j - L[i][j] <= k < j si k + V[i][k] >= j (adica, pentru cate pozitii k, j, /\-ul lor intersecteaza segmentul bazei piramidei determinat de centrul acesteia). Astfel, putem transforma problema intr-una de sume pe un anumit interval. Daca consideram ca un anume "varf" k, j ( /\ ) "este valabil" intre pozitiile k si k + V[k][j], atunci pentru un centru i, j ne intereseaza cate "varfuri valabile" avem intre pozitiile j - L[i][j] si j - 1. Deci se creeaza o serie de evenimente de genul: marcheaza pozitia i, j ca fiind valabila, marcheaza pozitia i, j ca fiind nevalabila si afla numarul pozitiilor valabile intre pozitiile j - L[i][j] si j - 1 ceea ce este echivalent cu urmatorul set de evenimente: aduna 1 in pozitia j, scade 1 din pozitia j si afla suma intre pozitiile k si j care poate fi rezolvat foarte simplu cu un arbore indexat binar sau cu un arbore de intervale. Asadar daca pentru o anumita coloana construim toate aceste evenimente, le sortam, si apoi le parcurgem in ordinea sortarii, putem rezolva problema in N log N cu o complexitate totala (pentru toate cele N coloane) de N2 log N.
