h2. 'Optic':problema/optic

Sa consideram, pe rand, fiecare nod $i$ al arborelui dat (in ordine, de la frunze spre radacina) si subarborele acestuia. Vom rezolva problema considerand ca arborele consta numai din subarborele cu radacina in nodul $i$. In felul acesta, cand vom considera nodul $i=1$, vom avea solutia pentru intreg arborele.
 
Pentru fiecare nod $i$ al arborelui, strategia optima de distribuire a mesajelor la toate nodurile din subarborele sau consta dintr-un numar $X$ de pasi (momente de timp). In primii $Y ≤ X$ dintre acesti pasi, nodul $i$ va trimite mesaje unor noduri din subarborele sau (nu are sens sa existe momente in care nodul $i$ sa nu trimita mesaj, intercalate intre momente in care nodul $i$ trimite mesaj).
 
La fiecare din cei $Y$ pasi, un nod $j$ din subarborele lui $i$ va primi mesajul de la nodul $i$. In continuare, nodul $i$ nu va mai trimite niciodata vreun mesaj unui alt nod din subarborele lui $j$ (daca $i$ ar trimite un mesaj unui nod $j'$ din subarborele lui $j$, $j$ nu ar putea trimite mesaje in acel pas ; de aceea, am putea decide ca nodul $j$ sa fie cel care trimite mesajul nodului $j'$, in timp ce nodul $i$ ar putea trimite mesajul unui alt nod). Dupa ce un nod $j$ a primit mesajul de la nodul $i$, vom considera in continuare ca subarborele lui $i$ a ramas fara subarborele lui $j$ (e ca si cum intreg subarborele lui $j$ ar fi fost taiat din subarborele lui $i$).
 
Vom calcula valorile $Tmin[i][j]$, reprezentand numarul minim de pasi necesari pentru a distribui mesajul tuturor nodurilor din subarborele nodului $i$, considerand ca au fost efectuati primii $j$ pasi din cadrul strategiei optime a nodului $i$ si ca au fost taiate din subarborele lui $i$ toti subarborii primelor $j$ noduri care au primit mesajul direct de la nodul $i$. Evident, cand $i=1$, in $Tmin[ 1 ][ 0 ]$ vom avea numarul minim de pasi necesari pentru distributia mesajului la toate nodurile din arbore.
 
Vom calcula, in ordine (de la $j=0$), toate valorile $Tmin[i][j]$. Sa observam intai (pentru cazul $j=0$), ca $Tmin[i][0]$ trebuie sa fie mai mare sau cel putin egal cu $Tmin[f][ 0 ]$, unde $f$ este fiu al lui $i$. Vom cauta binar aceasta valoare, intre maximul dintre valorile $Tmin[f][0]$ si $N-1$. Sa presupunem ca am fixat, in cadrul cautarii binare, $T$ unitati de timp. Vom initializa fiecare fiu $f$ al lui $i$ ca aflandu-se in starea $s(f)=0$ (adica nu s-a efectuat nici o mutare din cadrul strategiei sale optime). Vom considera fiul $f$ al lui $i$ care are valoarea $Tmin[f][s(f)]$ maxima. Daca $T > Tmin[f][s(f)]$, atunci trimitem mesajul nodului $f$, scadem din T o unitate de timp si mergem mai departe (ignorand nodul $f$ de acum inainte). Daca, la un moment dat, avem $T = Tmin[f][s(f)]$, atunci se demonstreaza (nu foarte usor, dar nici prea greu) ca nodul $i$ trebuie sa trimita mesaj nodului $j$ care este al $s(f)+1$-lea nod la care ar trimite mesaj nodul $f$ in cadrul strategiei sale optime. In felul acesta, taiem subarborele nodului $j$, scadem $T$ cu $1$ unitate si trecem nodul $f$ din starea $s(f)$ in starea $s(f)+1$ (pentru ca deja s-a efectuat o mutare din cadrul strategiei sale optime). Daca, la un moment dat, $T < Tmin[f][s(f)]$, atunci trebuie incercata o valoare mai mare in cadrul cautarii binare.
 
Inainte de a calcula $Tmin[i][j+1]$ dupa ce am calculat $Tmin[i][j]$, memoram in $Mut[i][j]$ nodul la care a trimis mesaj nodul $i$ prima data (adica al $j+1$-lea nod din cadrul strategiei optime a nodului $i$) si in $F[i][j]$ fiul din subarborele caruia face parte nodul $Mut[i][j]$. De asemenea, starile fiiilor nodului $i$ se seteaza la valorile pe care le aveau inainte de a calcula $Tmin[i][j]$, incrementand doar starea fiului $F[i][j]$ cu $1$ (sau eliminand de tot fiul $F[i][j]$, daca $F[i][j] = Mut[i][j]$). Vom termina calculul acestor valori atunci cand $Tmin[i][j]=0$.
 
Partea cea mai grea de demonstrat a algoritmului este data de cazul in care numarul de unitati de timp $T$ este egal cu maximul dintre $Tmin[f][s(f)]$. Intai vom observa ca e clar ca trebuie sa trimitem mesajul unui nod din subarborele lui f, in caz contrar, la momentul de timp urmator vom avea $T < Tmin[f][s(f)]$. Problema consta in alegerea nodului caruia sa trimitem acest mesaj. Observam ca, in acest caz, problema este similara cazului in care nodul $f$, aflat in starea $s(f)$, a primit anterior mesajul de la cineva si trebuie sa il trimita unui nod din subarborele sau; dar aceasta problema am rezolvat-o deja, nodul care trebuie sa primeasca mesajul fiind $Mut[f][s(f)]$.
 
Pentru reconstituirea solutiei, vom initializa toate nodurile ca aflandu-se in starea $0$ si vom tine un vector cu nodurile la care a ajuns deja mesajul. Prima mutare va fi de la nodul $1$ la nodul $j = Mut[ 1 ][ 0 ]$. Pentru toate nodurile de pe calea de la $1$ (inclusiv) la $j$ (exclusiv), vom incrementa starea in care se afla acestea, apoi vom marca ca nodul $j$ a primit mesajul. La urmatorul moment de timp, vom lua fiecare nod care detine mesajul, vom verifica daca mai are de efectuat pasi din strategia sa optima si daca da, vom efectua pasul corespunzator in mod similar mutarii descrise mai sus.
 
Complexitatea solutiei descrise este O(N^3^ * logN).
 
O dificultate suplimentara apare in momentul in care avem mai multi fii $f$ ai unui nod $i$, pentru care $Tmin[f][s(f)]$ are aceeasi valoare maxima. In aceasta situatie, va trebui sa il alegem pe cel pentru care sirul $Tmin[f][s(f)], Tmin[f][s(f)+1], ..$ este maxim din punct de vedere lexicografic. Justificarea este ca vrem sa scapam de acel fiu care ne-ar restrictiona cel mai mult mutarile ulterioare daca nu l-am taia acum. Mai exact, daca la un moment dat ajungem cu $T$-ul egal cu $Tmin[f][s(f)]$ (deoarece am eliminat altii fii si nu pe $f$), vrem ca acest fiu $f$ sa aiba sirul respectiv cat mai mic din punct de vedere lexicografic, pentru a ne restrictiona cat mai putin timpul.
 
h3. Link-uri utile
 
* 'Information Dissemination in Restricted Routing Networks':http://citeseer.ist.psu.edu/186949.html -  in acest articol este prezentata o solutie de complexitate O(N^3^) la aceasta problema
 

h2. 'Zvon':problema/zvon
Solutia "oficiala" are complexitatea $O(N*logN)$ si presupune calculul urmatoarelor valori:

* 'Bits of Trinity / ACM ICPC NWERC 1999':http://www.acm.inf.ethz.ch/ProblemSetArchive/B_EU_NWRC/1999/Problems.pdf'
* Parantezari / Baraj ONI 2000

h2. 'Clear':problema/clear
 
Probleme cere acoperirea cu numar minim de drumuri/cicluri a unui subgraf al grafului-grid $MxN$. Problema este foarte asemanatoare cu problema 'Kcity':problema/kcity , propusa in cadrul 'rundei 3 a concursului Autumn-Warmup 2007':http://infoarena.ro/autumn-warmup-2007/runda-3 si, daca numerotam nodurile grafului incepand de la $1$, parcurgand matricea pe linii, iar pentru fiecare linie, pe coloane, obtinem un graf care are aceeasi proprietate cu cel din Kcity (modulul diferentei dintre numerele asociate a doua noduri conectate printr-o muchie este limitat de o constanta: $7$, respectiv $10$). Totusi, aplicand direct ideea de rezolvare de la Kcity, se obtine un numar prea mare de stari, care nu permite incadrarea solutiei in limita de timp stabilita.
 
h3. Solutia 1 $(O(M * nr_stari(N) * O(4^N^)))$
 
h4. Acoperirea cu numar minim de drumuri
 
Vom calcula valorile $minp[i, S]$, reprezentand numarul minim de drumuri cu care pot fi acoperite toate zonele afectate de pe liniile $1,..,i$, iar pe linia $i$, configuratia drumurilor este data de starea $S$. Starea $S$ contine, pentru fiecare coloana de pe linie, un numar reprezentand starea coloanei respective:
 
* $0$ - zona de pe coloana respectiva are gradul $2$ (este in interiorul unui drum) sau are valoarea $0$ in matrice
* $num > 0$ - zona respectiva este capatul unui drum (avand identificatorul $num$)
 
In cadrul unei stari, identificatorul unui drum se poate repeta de cel mult $2$ ori (deoarece un drum are maxim $2$ capete). Identificatorii din starea $S$ au valori ordonate crescator in functie de prima aparitie in cadrul starii S. Observam ca nu mai trebuie sa identificam explicit un nod avand gradul $0$ (reprezentand un drum format dintr-un nod), deoarece orice nod din starea $S$ mai poate fi conectat doar la cel mult un alt vecin (de pe linia urmatoare). Proprietatea importanta care reduce mult numarul de stari este ca drumurile existente in starea $S$ respecta conditia de "parantezare": mai exact, daca cele $2$ capete ale unui drum $X$ se afla pe coloanele $c1$ si $c2$, iar cele $2$ capete ale unui drum $Y$ se afla pe coloanele $c3$ si $c4$, atunci $[c1, c2]$ este inclus in $[c3, c4]$ (sau invers). Aceasta proprietate se datoreaza faptului ca orice subgraf al grafului-grid este planar.
 
Pentru a calcula starile asociate liniei $i$, vom porni de la fiecare stare $S'$ asociata liniei $i-1$ si vom folosi un algoritm de backtracking pe linia $i$ care va genera starile $S$ ce pot fi obtinute din starea $S'$, alegand, pentru fiecare zona afectata de pe linia $i$, cate o varianta posibila dintre urmatoarele:
 
* incepe drum nou (in cazul functiei de backtracking vom diferentia nodurile ce au grad $0$, de celelalte noduri, insa atunci cand se calculeaza starea corespunzatoare liniei, aceste noduri vor primi un identificatior de drum strict pozitiv) -> numarul de drumuri creste cu 1
* uneste nodul curent de nodul din stanga -> numarul de drumuri ramane constant
* uneste nodul curent de nodul de sus -> numarul de drumuri ramane constant
* uneste nodul curent de nodul de sus, precum si de cel din stanga (numai daca nodul din stanga si cel de sus nu fac parte din acelasi drum si amandoua sunt capete de drumuri) -> numarul de drumuri scade cu 1
 
La final, vom alege valoarea minima dintre valorile $minp[M, S]$. Acest algoritm are, insa, o complexitate de timp prea mare si nu se incadreaza in limita de timp.

h2. Clear

h4. Acoperirea cu numar minim de cicluri
 
Vom calcula valorile $minc[i, S]$, reprezentand numarul minim de cicluri (inchise), astfel incat fiecare nod de pe liniile $1,..,i$ sa se afle pe un ciclu inchis sau deschis. Starea $S$ contine, pentru fiecare coloana de pe linie, un numar reprezentand starea coloanei respective:
 
* 0 - zona de pe coloana respectiva are gradul $2$ (este in interiorul unui ciclu inchis sau deschis) sau are valoarea $0$ in matrice
* $num > 0$ - zona respectiva este capatul unui ciclu deschis (avand identificatorul $num$)
 
In cadrul unei stari, fiecare identificator al unui capat de ciclu deschis apare de exact $2$ ori (nu pot ramane capete de cicluri deschise in spate, caci aceste cicluri nu ar mai putea fi inchise ulterior). La fel ca si in cazul acoperirii cu cicluri, identificatorii ciclurilor sunt numerotati de la $1$, crescator, in functie de prima aparitie in cadrul starii, avand si ei proprietatea de "parantezare".
 
Pentru a calcula starile asociate liniei $i$, vom porni de la fiecare stare $S'$ asociata liniei $i-1$ si vom folosi un algoritm de backtracking pe linia $i$ care va genera starile $S$ ce pot fi obtinute din starea $S'$, alegand, pentru fiecare zona afectata de pe linia $i$, cate o varianta posibila dintre urmatoarele:
 
* incepe ciclu deschis nou (in cazul functiei de backtracking vom diferentia nodurile ce au grad 0, de celelalte noduri, insa atunci cand se calculeaza starea corespunzatoare liniei, aceste noduri vor primi un identificatior de ciclu strict pozitiv) / aceasta varianta este aplicabila numai daca nodul din stanga nu este si el un ciclu deschis nou si daca nodul de deasupra este in starea 0 -> numarul de cicluri inchise ramane constant
* uneste nodul curent de nodul din stanga / aceasta varianta este aplicabile numai daca nodul de deasupra se afla in starea $0$ iar cel din stanga nu se afla in starea $0$ -> numarul de cicluri inchise ramane constant
* uneste nodul curent de nodul de deasupra / aceasta varianta este aplicabila numai daca in nodul de deasupra nu avem starea 0, iar in nodul din stanga nu s-a deschis un ciclu nou -> numarul de cicluri inchise ramane constant
* uneste nodul curent de nodul de sus, precum si de cel din stanga / numai daca atat nodul de sus, cat si cel din stanga nu se afla in starea $0$
** daca nodul din stanga si cel de sus fac parte din acelasi ciclu -> numarul de cicluri inchise creste cu 1
** daca nodul din stanga si cel de sus nu fac parte din acelasi ciclu -> numarul de cicluri inchise ramane constant (cele $2$ cicluri deschise se combina intr-un singur ciclu deschis)
 
La final, rezultatul dorit il gasim in $minp[M, S{~0~}]$, unde $S{~0~}$ este starea in care toate nodurile de pe linia $M$ se afla in starea $0$ (sunt in interiorul unui ciclu). Ca si in cazul acoperirii cu drumuri, nici aceasta solutie nu se incadreaza in limita de timp. Totusi, din cauza restrictiilor suplimentare de generare a starilor (trebuie sa nu se "uite" cicluri deschise in urma), algoritmul de backtracking are, in general, mai putine optiuni de continuare. Din acest motiv, numarul de coloane pentru acest caz este $10$ (fata de $7$ in cazul acoperirii cu drumuri).
 
h3. Solutia 2 $(O(M * N * nr_stari(N)))$
 
h4. Acoperirea cu numar minim de drumuri
 
Vom parcurge matricea pe linii, si pentru fiecare linie, pe coloane. Vom mentine o stare $S$ asemanatoare celei din solutia prezentata mai sus, la care se mai adauga un indice $C$ $(1 ≤ C ≤ N)$, avand semnificatia ca valorile de la $C+1$ la $N$ se refera la pozitiile de pe linia de deasupra, iar valorile de pe pozitiile de la $1$ la $C$ (din cadrul starii) se refera la linia curenta. Mentinand starea in acest fel, cand ajungem la elementul de pe linia $L$ si coloana $C$, vom calcula toate starile pentru care indicele este egal cu $C$. Pentru aceasta, vom parcurge toate starile $S'$ corespunzatoare coloanei anterioare ($C-1$ sau $N$, daca $C$ este prima coloana) si vom genera toate starile $S$ cu indicele egal cu $C$, avand de ales dintre urmatoarele optiuni:
 
* incepe drum nou -> numarul de drumuri creste cu 1
* uneste nodul curent de nodul din stanga -> numarul de drumuri ramane constant
* uneste nodul curent de nodul de sus -> numarul de drumuri ramane constant
* uneste nodul curent de nodul de sus, precum si de cel din stanga (numai daca nodul din stanga si cel de sus nu fac parte din acelasi drum) -> numarul de drumuri scade cu 1
 
Sunt, practic, aceleasi optiuni ca si cele din prima solutie, numai ca acum nu mai facem backtracking pe fiecare linie. Fata de solutia anterioara, care memora starile numai la sfarsitul unei linii, acum avem si stari "partiale", pana la o anumita coloana de pe o linie. Din cauza ca avem stari "partiale", va trebui sa consideram, pentru coloana curenta, si posibilitatea ca elementul respectiv sa fie singurul element de pe un drum (folosind, de exemplu, valoarea $-1$ pentru a codifica acest lucru). Pentru starile ce corespund ultimei coloane, aceasta posibilitate nu este necesar sa fie luata in considerare.
 
h4. Acoperirea cu numar minim de cicluri
 
Solutia pentru acoperirea cu numar minim de cicluri se bazeaza tot pe memorarea unor stari "partiale" (pentru fiecare coloana de pe o linie), spre deosebire de solutia ce memora doar stari pentru cate o linie completa. Prin memorarea acestor stari "partiale", se evita backtracking-ul pe fiecare linie.
 
 
O problema care trebuie luata in considerare in cadrul algoritmului este aceea de a asocia fiecarei stari un numar de la $1$ la numarul total de stari (sau incepand de la $0$), precum si, dat fiind numarul unei stari, sa gasim repede starea ce corespunde acelui numar. Pentru a doua problema, putem tine un vector al tuturor starilor si pur si simplu sa accesam $stare[i]$, unde $i$ este indicele starii care ne intereseaza. Prima problema este ceva mai complicata si pentru rezolvarea ei exista cel putin urmatoarele variante:
 
* memoram starile intr-un vector si le tinem sortate lexicografic, astfel ca putem sa cautam binar o stare $S$ in acest vector
* putem folosi o functie de hash, care sa calculeze pentru fiecare stare o valoare unica (de exemplu. privind-o ca un numar in baza $X$, unde $X$ este numarul total de valori distincte ce ar putea aparea in cadrul unei stari); apoi, mentinem o tabela hash sau un arbore echilibrat (de exemplu, $set$ sau $map$ in STL), care sa asocieze fiecarei valori hash a unei stari, indicele acesteia (un numar intre $1$ si numarul total de stari, sau intre $0$ si numarul total de stari minus $1$).
 
h3. Probleme asemanatoare
 
* 'Kcity / Autumn Warmup 2007':problema/kcity
* 'Pipes / ACM ICPC NWERC 2004':http://acm.pku.edu.cn/JudgeOnline/problem?id=2064

h2. 'H':problema/h

In aceste conditii, pentru fiecare caz, putem privi fiecare segment ca un punct intr-un alt sistem de coordonate 2D, in care coordonata $X$ corespunde lui $Yj$, iar coordonata $Y$ corespunde lui $Ys$. In plus, fiecare punct are asociata o pondere $W$. Pentru fiecare caz construim cu toate cele $N$ puncte un arbore de intervale 2D, care utilizeaza $O(N*logN)$ memorie. Acest arbore de intervale este, de fapt, un arbore de intervale obisnuit pentru coordonatele $X$, insa fiecare nod al arborelui mentine un vector cu coordonatele $Y$ ale punctelor ce corespund intervalului nodului respectiv. In plus, pentru fiecare coordonata $Y$ se mentine si ponderea asociata punctului.

Pentru fiecare caz $C$ si fiecare segment vertical, vom dori sa gasim segmenetul vertical din stanga sa cu care poate forma o litera $H$ de lungime maxima. Acest segment corespunde unui punct ce se afla intr-un dreptunghi ce corespunde constrangerilor pentru coordonatele $Yj$ si $Ys$ corespunzatoare cazului $C$ si care are ponderea $W$ maxima. Pentru fiecare caz, interogarile pot fi astfel puse incat dreptunghiul $[a,b]x[c,d]$ in care cautam punctul sa aiba ori coordonata c egala cu $-infinit$, ori coordonata $d$ egala cu $+infinit$. In aceste conditii, pentru fiecare nod din arborele de intervale in care se ajunge prin "spargerea" segmentului $[a,b]$, va trebui sa determinam ponderea maxima a unui punct care are coordonata $Y$ printre primele $z$ sau printre ultimele $z$ (unde $z$ este determinat folosind cautare binara in fiecare nod al arborelui de intervale al coordonatelor $X$ in care ajungem). Din acest motiv, putem sa mentinem pentru fiecare nod un vector $wmax[z]$ cu ponderea maxima a unui punct dintre primele $z$ puncte ce corespund intervalului nodului, precum si un vector similar ce corespunde ultimelor $z$ puncte ale intervalului; daca unul dintre capetele $c$ sau $d$ nu era egal cu $+/- infinit$, atunci trebuia sa folosim RMQ (Range Minimum Query) pentru fiecare nod din arbore.

Pentru fiecare caz $C$ si fiecare segment vertical, vom dori sa gasim segmenetul vertical din stanga sa cu care poate forma o litera $H$ de lungime maxima. Acest segment corespunde unui punct ce se afla intr-un dreptunghi ce corespunde constrangerilor pentru coordonatele $Yj$ si $Ys$ corespunzatoare cazului $C$ si care are ponderea $W$ maxima. Pentru fiecare caz, interogarile pot fi astfel puse incat dreptunghiul $[a,b]x[c,d]$ in care cautam punctul sa aiba ori coordonata $c$ egala cu $- infinit$, ori coordonata $d$ egala cu $+ infinit$. In aceste conditii, pentru fiecare nod din arborele de intervale in care se ajunge prin "spargerea" segmentului $[a,b]$, va trebui sa determinam ponderea maxima a unui punct care are coordonata $Y$ printre primele $z$ sau printre ultimele $z$ (unde $z$ este determinat folosind cautare binara in fiecare nod al arborelui de intervale al coordonatelor $X$ in care ajungem). Din acest motiv, putem sa mentinem pentru fiecare nod un vector $wmax[z]$ cu ponderea maxima a unui punct dintre primele $z$ puncte ce corespund intervalului nodului, precum si un vector similar ce corespunde ultimelor $z$ puncte ale intervalului; daca unul dintre capetele $c$ sau $d$ nu era egal cu $+/- infinit$, atunci trebuia sa folosim RMQ (Range Minimum Query) pentru fiecare nod din arbore.

Observam ca, in modul in care am pus interogarile, nu am specificat nicaieri ca punctul cu pondere maxima sa corespunda unui segment aflat in stanga segmentului pentru care facem interogarea. Totusi, daca punctul cu pondere maxima obtinut nu corespunde unui segment aflat in stanga segmentului curent, atunci vom obtine in mod sigur o litera H de lungime mai mare in momentul in care vom efectua interogarea pentru segmentul corespunzator punctului obtinut (acest lucru se datoreaza modului in care sunt definite ponderile).

* 'Range Minimum Query and Lowest Common Ancestor':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor , articol scris de catre Daniel Pasaila
* 'Orthogonal Range Queries':http://people.csail.mit.edu/indyk/6.838-old/handouts/lec5.pdf

Probleme asemanatoare

h3. Probleme asemanatoare

* 'Zoo / .campion 2003':problema/zoo
* 'Kth Number / ACM ICPC NEERC Northern Subregion 2004':http://acm.tju.edu.cn/toj/showp2722.html