h2(#tramvai). 'Tramvai':problema/tramvai

Se construieste un graf al punctelor de intersectie dintre oricare $2$ drepte. Acest graf are $O(N^2^)$ noduri, insa fiecare nod are cel mult $4$ vecini (cate $2$ pe fiecare din cele $2$ drepte care il determina). Problema se reduce acum la determinarea drumului minim intre $2$ puncte in acest graf. Algoritmul folosit de solutia oficiala este 'Dijkstra':http://en.wikipedia.org/wiki/Dijkstra's_algorithm cu heap, care are complexitatea $O(N^2^*logN)$, insa se poate folosi cu succes si algoritmul 'Bellman-Ford':http://en.wikipedia.org/wiki/Bellman-Ford_algorithm, implementat folosind o coada. Aceasta varianta, cunoscuta ca algoritmul Bellman-Ford-Moore, are o complexitate teoretica mare, dar, in practica, merge foare bine; este, posibil, insa, ca, in cazul acestei probleme, sa fie necesare unele optimizari pentru a se incadra in limita de timp - de exemplu, folosirea euristicii "parent checking". Aceasta euristica se refera la urmatoarea situatie: Sa presupunem ca am extras din coada nodul $X$ (primul nod din coada) si urmeaza sa incercam sa facem update-uri la distantele tuturor vecinilor nodului $X$, folosind distanta calculata pana acum pentru $X$. De asemenea, sa presupunem ca nodul care i-a facut update la distanta minima nodului $X$ este $T$ ($T$ mai este numit si parintele lui $X$, deoarece este nodul chiar dinaintea lui $X$ de pe drumul minim pana la $X$). Inainte sa incercam sa facem update pentru toti vecinii lui $X$, verificam daca nodul $T$ se afla in coada. Daca se afla in coada, atunci nu mai facem update folosind nodul $X$ si trecem la urmatorul nod din coada. Motivul este urmatorul: Daca nodul $T$ se afla in coada, el a fost introdus acolo dupa ce i-a facut update distantei pana la nodul $X$; noua valoarea a distantei minime pana la $T$ este mai mica decat in momentul cand s-a calculat distanta minima pana la $X$, astfel ca, atunci cand vom extrage din coada nodul $T$, se va micsora in mod sigur si distanta pana la $X$. Prin urmare, nu are rost sa facem acum update-uri folosind nodul $X$, deoarece acesta are calculata o distanta despre care stim sigur ca va fi micsorata in curand.

Se construieste un graf al punctelor de intersectie dintre oricare $2$ drepte. Acest graf are $O(N^2^)$ noduri, insa fiecare nod are cel mult $4$ vecini (cate $2$ pe fiecare din cele $2$ drepte care il determina). Problema se reduce acum la determinarea drumului minim intre $2$ puncte in acest graf. Algoritmul folosit de solutia oficiala este 'Dijkstra':http://en.wikipedia.org/wiki/Dijkstra's_algorithm cu heap, care are complexitatea $O(N^2^*logN)$, insa se poate folosi cu succes si algoritmul 'Bellman-Ford':http://en.wikipedia.org/wiki/Bellman-Ford_algorithm, implementat folosind o coada. Aceasta varianta, cunoscuta ca algoritmul Bellman-Ford-Moore, are o complexitate teoretica mare, dar, in practica, merge foare bine; este, posibil, insa, ca, in cazul acestei probleme, sa fie necesare unele optimizari pentru a se incadra in limita de timp - de exemplu, folosirea euristicii "parent checking". Aceasta euristica se refera la urmatoarea situatie: Sa presupunem ca am extras din coada nodul $X$ (primul nod din coada) si urmeaza sa incercam sa facem update-uri la distantele tuturor vecinilor nodului $X$, folosind distanta calculata pana acum pentru $X$. De asemenea, sa presupunem ca nodul care i-a facut update la distanta minima nodului $X$ este $T$ ({$T$} mai este numit si parintele lui $X$, deoarece este nodul chiar dinaintea lui $X$ de pe drumul minim pana la $X$). Inainte sa incercam sa facem update pentru toti vecinii lui $X$, verificam daca nodul $T$ se afla in coada. Daca se afla in coada, atunci nu mai facem update folosind nodul $X$ si trecem la urmatorul nod din coada. Motivul este urmatorul: Daca nodul $T$ se afla in coada, el a fost introdus acolo dupa ce i-a facut update distantei pana la nodul $X$; noua valoarea a distantei minime pana la $T$ este mai mica decat in momentul cand s-a calculat distanta minima pana la $X$, astfel ca, atunci cand vom extrage din coada nodul $T$, se va micsora in mod sigur si distanta pana la $X$. Prin urmare, nu are rost sa facem acum update-uri folosind nodul $X$, deoarece acesta are calculata o distanta despre care stim sigur ca va fi micsorata in curand.

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:

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

O parte din acesti pointeri pot fi calculati in momentul in care, in faza de constructie a arborelui de intervale 2D, se interclaseaza coordonatele $Y$ corespunzatoare fiului stanga si fiului dreapta. Cealalta parte a pointer-ilor se calculeaza realizand inca $2$ parcurgeri ale coordonatelor $Y$ sortate, una de la stanga la dreapta si alta de la dreapta la stanga (in conditiile in care am memorat pentru fiecare coordonata $Y$ de la care din cei doi fii provine).

Unul dintre concurenti a obtinut $100$ de puncte folosind o structura de date 2D numita 'kd-tree':http://en.wikipedia.org/wiki/Kd-tree, care poate oferi aceleasi operatii ca si un arbore de intervale 2D. Diferenta consta in cantitatea de memorie folosita ($O(N)$, in loc de $O(N*logN)$), dar si in complexitatea cautarii in interiorul unui dreptunghi ($O(sqrt(N))$, in loc de $O(log^2^N)$ sau $O(logN)$ cu optimizarea mentionata).

Unul dintre concurenti a obtinut $100$ de puncte folosind o structura de date 2D numita 'kd-tree':http://en.wikipedia.org/wiki/Kd-tree, care poate oferi aceleasi operatii ca si un arbore de intervale 2D. Diferenta consta in cantitatea de memorie folosita ({$O(N)$}, in loc de $O(N*logN)$), dar si in complexitatea cautarii in interiorul unui dreptunghi ({$O(sqrt(N))$}, in loc de $O(log^2^N)$ sau $O(logN)$ cu optimizarea mentionata).

h3. Link-uri utile